lean_graph::DAG< NodeType, Cost, CounterType, H > Class Template Reference

#include <lean_graph.h>

Inheritance diagram for lean_graph::DAG< NodeType, Cost, CounterType, H >:

Public Member Functions
auto	topo_sort () const -> std::vector< CounterType >
virtual auto	singular_shortest_path (CounterType start, CounterType end) const -> std::pair< std::unordered_map< CounterType, Cost >, std::unordered_map< CounterType, CounterType > > override
Public Member Functions inherited from lean_graph::DiGraph< NodeType, Cost, CounterType, H >
auto	registerNode (const NodeType &node) -> CounterType
virtual auto	registerEdge (CounterEdge< CounterType, Cost > edge) -> void
virtual auto	modifyEdge (CounterEdge< CounterType, Cost > edge, Cost new_cost) -> std::optional< edge_error >
auto	existEdge (CounterEdge< CounterType, Cost > edge) const -> bool
auto	existBlankEdge (CounterBlankEdge< CounterType > edge) const -> bool
auto	existBlankEdge (CounterEdge< CounterType, Cost > edge) const -> bool
auto	existCounterNode (CounterType node) const -> bool
virtual auto	edges () const -> std::vector< CounterEdge< CounterType, Cost > >
template<VisitOrder v>
auto	dfs () const -> std::vector< CounterType >
template<VisitOrder v>
auto	bfs () const -> std::vector< CounterType >
template<VisitOrder v>
auto	explore_dfs (CounterType from) const -> std::vector< CounterType >
template<VisitOrder v>
auto	explore_bfs (CounterType from) const -> std::vector< CounterType >
virtual auto	cycles () const -> std::vector< std::vector< CounterType > >
	INFO: Johnson algorithm.
auto	bellman_ford (CounterType start) const -> std::pair< std::unordered_map< CounterType, Cost >, std::unordered_map< CounterType, CounterType > > const
auto	scc () -> std::vector< DiGraph > const
	INFO: Strongly connected components (SCC)

Additional Inherited Members
Protected Member Functions inherited from lean_graph::DiGraph< NodeType, Cost, CounterType, H >
template<VisitOrder v>
auto	explore_dfs_protected (CounterType from, std::optional< std::reference_wrapper< std::unordered_set< CounterType > > > pre_visited=std::nullopt) const -> std::vector< CounterType >
template<VisitOrder v>
auto	explore_bfs_protected (CounterType from, std::optional< std::reference_wrapper< std::unordered_set< CounterType > > > pre_visited=std::nullopt) const -> std::vector< CounterType >
Protected Attributes inherited from lean_graph::DiGraph< NodeType, Cost, CounterType, H >
std::unordered_map< CounterType, std::set< CounterHalfEdge< CounterType, Cost > > >	graph
Counter< NodeType, CounterType, H >	node_counter {0}
CounterType	num_node
CounterType	num_edge

Detailed Description

template<class NodeType, class Cost, class CounterType, class H>
requires Hashable<NodeType> and std::is_arithmetic_v<Cost>
class lean_graph::DAG< NodeType, Cost, CounterType, H >

INFO: A BasicGraph is just a DiGraph that can be multi-edges, with edge-cost being different.

INFO: A DAG is a Directed Acyclic Graph that can be multi-edges, with edge-cost being different.

Member Function Documentation

singular_shortest_path()

template<class NodeType, class Cost, class CounterType, class H>

virtual auto lean_graph::DAG< NodeType, Cost, CounterType, H >::singular_shortest_path ( CounterType start, CounterType end ) const -> std::pair<std::unordered_map<CounterType, Cost>, std::unordered_map<CounterType, CounterType>>

inlineoverridevirtual

INFO: Single source, single path dijkstra algorithm User discretion required, user might input negative cost.

Successful djikstra will contain at least a vector of two nodes. If you're not a nerd, please be careful

Reimplemented from lean_graph::DiGraph< NodeType, Cost, CounterType, H >.

topo_sort()

template<class NodeType, class Cost, class CounterType, class H>

auto lean_graph::DAG< NodeType, Cost, CounterType, H >::topo_sort ( ) const -> std::vector<CounterType>

inline

---

The documentation for this class was generated from the following file:

• core/include/lean_graph.h