Files | |
file | euler.h |
Euler tour. | |
file | topology.h |
Topology related algorithms. | |
Classes | |
class | EulerIt |
Euler iterator for directed graphs. More... | |
class | UEulerIt |
Euler iterator for undirected graphs. More... | |
Functions | |
template<class Graph> | |
bool | lemon::euler (const Graph &g) |
Checks if the graph is Euler. | |
template<typename UGraph> | |
bool | lemon::connected (const UGraph &graph) |
Check that the given undirected graph is connected. | |
template<typename UGraph> | |
int | lemon::countConnectedComponents (const UGraph &graph) |
Count the number of connected components of an undirected graph. | |
template<class UGraph, class NodeMap> | |
int | lemon::connectedComponents (const UGraph &graph, NodeMap &compMap) |
Find the connected components of an undirected graph. | |
template<typename Graph> | |
bool | lemon::stronglyConnected (const Graph &graph) |
Check that the given directed graph is strongly connected. | |
template<typename Graph> | |
int | lemon::countStronglyConnectedComponents (const Graph &graph) |
Count the strongly connected components of a directed graph. | |
template<typename Graph, typename NodeMap> | |
int | lemon::stronglyConnectedComponents (const Graph &graph, NodeMap &compMap) |
Find the strongly connected components of a directed graph. | |
template<typename Graph, typename EdgeMap> | |
int | lemon::stronglyConnectedCutEdges (const Graph &graph, EdgeMap &cutMap) |
Find the cut edges of the strongly connected components. | |
template<typename UGraph> | |
bool | lemon::biNodeConnected (const UGraph &graph) |
Checks the graph is bi-node-connected. | |
template<typename UGraph> | |
int | lemon::countBiNodeConnectedComponents (const UGraph &graph) |
Count the biconnected components. | |
template<typename UGraph, typename UEdgeMap> | |
int | lemon::biNodeConnectedComponents (const UGraph &graph, UEdgeMap &compMap) |
Find the bi-node-connected components. | |
template<typename UGraph, typename NodeMap> | |
int | lemon::biNodeConnectedCutNodes (const UGraph &graph, NodeMap &cutMap) |
Find the bi-node-connected cut nodes. | |
template<typename UGraph> | |
bool | lemon::biEdgeConnected (const UGraph &graph) |
Checks that the graph is bi-edge-connected. | |
template<typename UGraph> | |
int | lemon::countBiEdgeConnectedComponents (const UGraph &graph) |
Count the bi-edge-connected components. | |
template<typename UGraph, typename NodeMap> | |
int | lemon::biEdgeConnectedComponents (const UGraph &graph, NodeMap &compMap) |
Find the bi-edge-connected components. | |
template<typename UGraph, typename UEdgeMap> | |
int | lemon::biEdgeConnectedCutEdges (const UGraph &graph, UEdgeMap &cutMap) |
Find the bi-edge-connected cut edges. | |
template<typename Graph, typename NodeMap> | |
void | lemon::topologicalSort (const Graph &graph, NodeMap &order) |
Sort the nodes of a DAG into topolgical order. | |
template<typename Graph, typename NodeMap> | |
bool | lemon::checkedTopologicalSort (const Graph &graph, NodeMap &order) |
Sort the nodes of a DAG into topolgical order. | |
template<typename Graph> | |
bool | lemon::dag (const Graph &graph) |
Check that the given directed graph is a DAG. | |
template<typename UGraph> | |
bool | lemon::acyclic (const UGraph &graph) |
Check that the given undirected graph is acyclic. | |
template<typename UGraph> | |
bool | lemon::tree (const UGraph &graph) |
Check that the given undirected graph is tree. | |
template<typename UGraph> | |
bool | lemon::bipartite (const UGraph &graph) |
Check if the given undirected graph is bipartite or not. | |
template<typename UGraph, typename NodeMap> | |
bool | lemon::bipartitePartitions (const UGraph &graph, NodeMap &partMap) |
Check if the given undirected graph is bipartite or not. |
|
Checks if the graph is Euler. It works for both directed and undirected graphs.
|
|
Check that the given undirected graph connected.
|
|
Count the number of connected components of an undirected graph
|
|
Find the connected components of an undirected graph.
![]()
|
|
Check that the given directed graph is strongly connected. The graph is strongly connected when any two nodes of the graph are connected with directed paths in both direction.
|
|
Count the strongly connected components of a directed graph. The strongly connected components are the classes of an equivalence relation on the nodes of the graph. Two nodes are connected with directed paths in both direction.
|
|
Find the strongly connected components of a directed graph. The strongly connected components are the classes of an equivalence relation on the nodes of the graph. Two nodes are in relationship when there are directed paths between them in both direction.
![]()
|
|
Find the cut edges of the strongly connected components. The strongly connected components are the classes of an equivalence relation on the nodes of the graph. Two nodes are in relationship when there are directed paths between them in both direction. The strongly connected components are separated by the cut edges.
|
|
This function checks that the undirected graph is bi-node-connected graph. The graph is bi-node-connected if any two undirected edge is on same circle.
|
|
This function finds the bi-node-connected components in an undirected graph. The biconnected components are the classes of an equivalence relation on the undirected edges. Two undirected edge is in relationship when they are on same circle.
|
|
This function finds the bi-node-connected components in an undirected graph. The bi-node-connected components are the classes of an equivalence relation on the undirected edges. Two undirected edge are in relationship when they are on same circle.
![]()
|
|
This function finds the bi-node-connected cut nodes in an undirected graph. The bi-node-connected components are the classes of an equivalence relation on the undirected edges. Two undirected edges are in relationship when they are on same circle. The biconnected components are separted by nodes which are the cut nodes of the components.
|
|
This function checks that the graph is bi-edge-connected. The undirected graph is bi-edge-connected when any two nodes are connected with two edge-disjoint paths.
|
|
This function count the bi-edge-connected components in an undirected graph. The bi-edge-connected components are the classes of an equivalence relation on the nodes. Two nodes are in relationship when they are connected with at least two edge-disjoint paths.
|
|
This function finds the bi-edge-connected components in an undirected graph. The bi-edge-connected components are the classes of an equivalence relation on the nodes. Two nodes are in relationship when they are connected at least two edge-disjoint paths.
![]()
|
|
This function finds the bi-edge-connected components in an undirected graph. The bi-edge-connected components are the classes of an equivalence relation on the nodes. Two nodes are in relationship when they are connected with at least two edge-disjoint paths. The bi-edge-connected components are separted by edges which are the cut edges of the components.
|
|
Sort the nodes of a DAG into topolgical order.
|
|
Sort the nodes of a DAG into topolgical order. It also checks that the given graph is DAG.
|
|
Check that the given directed graph is a DAG. The DAG is an Directed Acyclic Graph.
|
|
Check that the given undirected graph acyclic.
|
|
Check that the given undirected graph is tree.
|
|
The function checks if the given undirected
|
|
The function checks if the given undirected graph is bipartite or not. The Bfs algorithm is used to calculate the result. During the execution, the
![]() |