Topology related algorithms
[Graph Algorithms]


Detailed Description


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.


Function Documentation

bool lemon::euler const Graph g  ) 
 

Checks if the graph is Euler. It works for both directed and undirected graphs.

Note:
By definition, a directed graph is called Euler if and only if connected and the number of it is incoming and outgoing edges are the same for each node. Similarly, an undirected graph is called Euler if and only if it is connected and the number of incident edges is even for each node. Therefore, there are graphs which are not Euler, but still have an Euler tour.
Todo:
Test required

bool lemon::connected const UGraph &  graph  ) 
 

Check that the given undirected graph connected.

Parameters:
graph The undirected graph.
Returns:
True when there is path between any two nodes in the graph.
Note:
By definition, the empty graph is connected.

int lemon::countConnectedComponents const UGraph &  graph  ) 
 

Count the number of connected components of an undirected graph

Parameters:
graph The graph. It should be undirected.
Returns:
The number of components
Note:
By definition, the empty graph consists of zero connected components.

int lemon::connectedComponents const UGraph &  graph,
NodeMap &  compMap
 

Find the connected components of an undirected graph.

connected_components.png

Parameters:
graph The graph. It should be undirected.
Return values:
compMap A writable node map. The values will be set from 0 to the number of the connected components minus one. Each values of the map will be set exactly once, the values of a certain component will be set continuously.
Returns:
The number of components

bool lemon::stronglyConnected const Graph 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.

Returns:
False when the graph is not strongly connected.
See also:
connected
Note:
By definition, the empty graph is strongly connected.

int lemon::countStronglyConnectedComponents const Graph graph  ) 
 

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.

Parameters:
graph The graph.
Returns:
The number of components
Note:
By definition, the empty graph has zero strongly connected components.

int lemon::stronglyConnectedComponents const Graph graph,
NodeMap &  compMap
 

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.

strongly_connected_components.png

Parameters:
graph The graph.
Return values:
compMap A writable node map. The values will be set from 0 to the number of the strongly connected components minus one. Each values of the map will be set exactly once, the values of a certain component will be set continuously.
Returns:
The number of components

int lemon::stronglyConnectedCutEdges const Graph graph,
EdgeMap &  cutMap
 

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.

Parameters:
graph The graph.
Return values:
cutMap A writable node map. The values will be set true when the edge is a cut edge.
Returns:
The number of cut edges

bool lemon::biNodeConnected const UGraph &  graph  ) 
 

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.

Parameters:
graph The graph.
Returns:
True when the graph bi-node-connected.
Todo:
Make it faster.

int countBiNodeConnectedComponents const UGraph &  graph  ) 
 

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.

Parameters:
graph The graph.
Returns:
The number of components.

int lemon::biNodeConnectedComponents const UGraph &  graph,
UEdgeMap &  compMap
 

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.

node_biconnected_components.png

Parameters:
graph The graph.
Return values:
compMap A writable uedge map. The values will be set from 0 to the number of the biconnected components minus one. Each values of the map will be set exactly once, the values of a certain component will be set continuously.
Returns:
The number of components.

int lemon::biNodeConnectedCutNodes const UGraph &  graph,
NodeMap &  cutMap
 

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.

Parameters:
graph The graph.
Return values:
cutMap A writable edge map. The values will be set true when the node separate two or more components.
Returns:
The number of the cut nodes.

bool lemon::biEdgeConnected const UGraph &  graph  ) 
 

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.

Parameters:
graph The undirected graph.
Returns:
The number of components.
Todo:
Make it faster.

int lemon::countBiEdgeConnectedComponents const UGraph &  graph  ) 
 

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.

Parameters:
graph The undirected graph.
Returns:
The number of components.

int lemon::biEdgeConnectedComponents const UGraph &  graph,
NodeMap &  compMap
 

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.

edge_biconnected_components.png

Parameters:
graph The graph.
Return values:
compMap A writable node map. The values will be set from 0 to the number of the biconnected components minus one. Each values of the map will be set exactly once, the values of a certain component will be set continuously.
Returns:
The number of components.

int lemon::biEdgeConnectedCutEdges const UGraph &  graph,
UEdgeMap &  cutMap
 

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.

Parameters:
graph The graph.
Return values:
cutMap A writable node map. The values will be set true when the edge is a cut edge.
Returns:
The number of cut edges.

void lemon::topologicalSort const Graph graph,
NodeMap &  order
 

Sort the nodes of a DAG into topolgical order.

Parameters:
graph The graph. It should be directed and acyclic.
Return values:
order A writable node map. The values will be set from 0 to the number of the nodes in the graph minus one. Each values of the map will be set exactly once, the values will be set descending order.
See also:
checkedTopologicalSort

dag

bool lemon::checkedTopologicalSort const Graph graph,
NodeMap &  order
 

Sort the nodes of a DAG into topolgical order. It also checks that the given graph is DAG.

Parameters:
graph The graph. It should be directed and acyclic.
Return values:
order A readable - writable node map. The values will be set from 0 to the number of the nodes in the graph minus one. Each values of the map will be set exactly once, the values will be set descending order.
Returns:
False when the graph is not DAG.
See also:
topologicalSort

dag

bool lemon::dag const Graph graph  ) 
 

Check that the given directed graph is a DAG. The DAG is an Directed Acyclic Graph.

Returns:
False when the graph is not DAG.
See also:
acyclic

bool lemon::acyclic const UGraph &  graph  ) 
 

Check that the given undirected graph acyclic.

Parameters:
graph The undirected graph.
Returns:
True when there is no circle in the graph.
See also:
dag

bool lemon::tree const UGraph &  graph  ) 
 

Check that the given undirected graph is tree.

Parameters:
graph The undirected graph.
Returns:
True when the graph is acyclic and connected.

bool lemon::bipartite const UGraph &  graph  )  [inline]
 

The function checks if the given undirected graph graph is bipartite or not. The Bfs algorithm is used to calculate the result.

Parameters:
graph The undirected graph.
Returns:
True if graph is bipartite, false otherwise.
See also:
bipartitePartitions
Author:
Balazs Attila Mihaly

bool lemon::bipartitePartitions const UGraph &  graph,
NodeMap &  partMap
[inline]
 

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 partMap will be set as the two partitions of the graph.

Parameters:
graph The undirected graph.
Return values:
partMap A writable bool map of nodes. It will be set as the two partitions of the graph.
Returns:
True if graph is bipartite, false otherwise.
Author:
Balazs Attila Mihaly
bipartite_partitions.png


Generated on Fri Feb 3 18:40:01 2006 for LEMON by  doxygen 1.4.6