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

#include <lean_graph.h>

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

Public Member Functions
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.
virtual auto	singular_shortest_path (CounterType start, CounterType end) const -> std::pair< std::unordered_map< CounterType, Cost >, std::unordered_map< CounterType, CounterType > >
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)

Protected Member Functions
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
std::unordered_map< CounterType, std::set< CounterHalfEdge< CounterType, Cost > > >	graph
Counter< NodeType, CounterType, H >	node_counter {0}
CounterType	num_node
CounterType	num_edge

Friends
template<class CT, class Cst>
class	EdgeIte

Detailed Description

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

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

Member Function Documentation

bellman_ford()

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

auto lean_graph::DiGraph< NodeType, Cost, CounterType, H >::bellman_ford ( CounterType start ) const -> std::pair<std::unordered_map<CounterType, Cost>, std::unordered_map<CounterType, CounterType>> const

inlinenodiscard

INFO: Single source, multi paths bellman ford algorithm User discretion required, user might input negative cost cycles.

Successful bellman ford will contain pair of non empty maps. If you're not a nerd, please be careful

bfs()

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

template<VisitOrder v>

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

inlinenodiscard

INFO: Performs full dfs of all nodes connected to a node with either pre or post order from a single node

cycles()

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

virtual auto lean_graph::DiGraph< NodeType, Cost, CounterType, H >::cycles ( ) const -> std::vector<std::vector<CounterType>>

inlinenodiscardvirtual

INFO: Johnson algorithm.

Reimplemented in lean_graph::UniGraph< NodeType, Cost, CounterType, H >.

dfs()

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

template<VisitOrder v>

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

inlinenodiscard

INFO: Performs full dfs of all nodes connected to a node with either pre or post order from a single node

edges()

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

virtual auto lean_graph::DiGraph< NodeType, Cost, CounterType, H >::edges ( ) const -> std::vector<CounterEdge<CounterType, Cost>>

inlinevirtual

Reimplemented in lean_graph::UniGraph< NodeType, Cost, CounterType, H >.

existBlankEdge() [1/2]

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

auto lean_graph::DiGraph< NodeType, Cost, CounterType, H >::existBlankEdge ( CounterBlankEdge< CounterType > edge ) const -> bool

inline

NOTE: To bypass unused var warning in structured bindings

existBlankEdge() [2/2]

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

auto lean_graph::DiGraph< NodeType, Cost, CounterType, H >::existBlankEdge ( CounterEdge< CounterType, Cost > edge ) const -> bool

inline

existCounterNode()

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

auto lean_graph::DiGraph< NodeType, Cost, CounterType, H >::existCounterNode ( CounterType node ) const -> bool

inline

existEdge()

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

auto lean_graph::DiGraph< NodeType, Cost, CounterType, H >::existEdge ( CounterEdge< CounterType, Cost > edge ) const -> bool

inline

explore_bfs()

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

template<VisitOrder v>

auto lean_graph::DiGraph< NodeType, Cost, CounterType, H >::explore_bfs ( CounterType from ) const -> std::vector<CounterType>

inlinenodiscard

INFO: Performs exploration of all nodes connected to a node in bfs fashion with either pre or post order as template from a single node

explore_bfs_protected()

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

template<VisitOrder v>

auto lean_graph::DiGraph< NodeType, Cost, CounterType, H >::explore_bfs_protected ( CounterType from, std::optional< std::reference_wrapper< std::unordered_set< CounterType > > > pre_visited = std::nullopt ) const -> std::vector<CounterType>

inlineprotected

explore_dfs()

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

template<VisitOrder v>

auto lean_graph::DiGraph< NodeType, Cost, CounterType, H >::explore_dfs ( CounterType from ) const -> std::vector<CounterType>

inlinenodiscard

INFO: Performs exploration of all nodes connected to a node in dfs fashion with either pre or post order from a single node

explore_dfs_protected()

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

template<VisitOrder v>

auto lean_graph::DiGraph< NodeType, Cost, CounterType, H >::explore_dfs_protected ( CounterType from, std::optional< std::reference_wrapper< std::unordered_set< CounterType > > > pre_visited = std::nullopt ) const -> std::vector<CounterType>

inlineprotected

modifyEdge()

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

virtual auto lean_graph::DiGraph< NodeType, Cost, CounterType, H >::modifyEdge ( CounterEdge< CounterType, Cost > edge, Cost new_cost ) -> std::optional<edge_error>

inlinevirtual

Reimplemented in lean_graph::UniGraph< NodeType, Cost, CounterType, H >.

registerEdge()

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

virtual auto lean_graph::DiGraph< NodeType, Cost, CounterType, H >::registerEdge ( CounterEdge< CounterType, Cost > edge ) -> void

inlinevirtual

Reimplemented in lean_graph::UniGraph< NodeType, Cost, CounterType, H >.

registerNode()

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

auto lean_graph::DiGraph< NodeType, Cost, CounterType, H >::registerNode ( const NodeType & node ) -> CounterType

inline

scc()

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

auto lean_graph::DiGraph< NodeType, Cost, CounterType, H >::scc

(

)

-> std::vector< DiGraph > const

INFO: Strongly connected components (SCC)

singular_shortest_path()

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

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

inlinenodiscardvirtual

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 in lean_graph::DAG< NodeType, Cost, CounterType, H >.

Friends And Related Symbol Documentation

EdgeIte

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

template<class CT, class Cst>

friend class EdgeIte

friend

Member Data Documentation

graph

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

std::unordered_map<CounterType, std::set<CounterHalfEdge<CounterType, Cost> > > lean_graph::DiGraph< NodeType, Cost, CounterType, H >::graph

protected

node_counter

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

Counter<NodeType, CounterType, H> lean_graph::DiGraph< NodeType, Cost, CounterType, H >::node_counter {0}

protected

num_edge

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

CounterType lean_graph::DiGraph< NodeType, Cost, CounterType, H >::num_edge

protected

num_node

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

CounterType lean_graph::DiGraph< NodeType, Cost, CounterType, H >::num_node

protected

---

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

• core/include/lean_graph.h