Connectivity and other graph properties
[Algorithms]

---

Detailed Description

This group describes the algorithms for discovering the graph properties like connectivity, bipartiteness, euler property, simplicity etc.

Classes
class	EulerIt< Graph >
	Euler iterator for directed graphs. More...
class	UEulerIt< Graph >
	Euler iterator for undirected graphs. More...
Files
file	euler.h
	Euler tour.
file	topology.h
	Topology related algorithms.
Functions
template<class Graph >
bool	euler (const Graph &g)
	Checks if the graph is Euler.
template<typename UGraph >
bool	connected (const UGraph &graph)
	Check that the given undirected graph is connected.
template<typename UGraph >
int	countConnectedComponents (const UGraph &graph)
	Count the number of connected components of an undirected graph.
template<class UGraph , class NodeMap >
int	connectedComponents (const UGraph &graph, NodeMap &compMap)
	Find the connected components of an undirected graph.
template<typename Graph >
bool	stronglyConnected (const Graph &graph)
	Check that the given directed graph is strongly connected.
template<typename Graph >
int	countStronglyConnectedComponents (const Graph &graph)
	Count the strongly connected components of a directed graph.
template<typename Graph , typename NodeMap >
int	stronglyConnectedComponents (const Graph &graph, NodeMap &compMap)
	Find the strongly connected components of a directed graph.
template<typename Graph , typename EdgeMap >
int	stronglyConnectedCutEdges (const Graph &graph, EdgeMap &cutMap)
	Find the cut edges of the strongly connected components.
template<typename UGraph >
bool	biNodeConnected (const UGraph &graph)
	Checks the graph is bi-node-connected.
template<typename UGraph >
int	countBiNodeConnectedComponents (const UGraph &graph)
	Count the biconnected components.
template<typename UGraph , typename UEdgeMap >
int	biNodeConnectedComponents (const UGraph &graph, UEdgeMap &compMap)
	Find the bi-node-connected components.
template<typename UGraph , typename NodeMap >
int	biNodeConnectedCutNodes (const UGraph &graph, NodeMap &cutMap)
	Find the bi-node-connected cut nodes.
template<typename UGraph >
bool	biEdgeConnected (const UGraph &graph)
	Checks that the graph is bi-edge-connected.
template<typename UGraph >
int	countBiEdgeConnectedComponents (const UGraph &graph)
	Count the bi-edge-connected components.
template<typename UGraph , typename NodeMap >
int	biEdgeConnectedComponents (const UGraph &graph, NodeMap &compMap)
	Find the bi-edge-connected components.
template<typename UGraph , typename UEdgeMap >
int	biEdgeConnectedCutEdges (const UGraph &graph, UEdgeMap &cutMap)
	Find the bi-edge-connected cut edges.
template<typename Graph , typename NodeMap >
void	topologicalSort (const Graph &graph, NodeMap &order)
	Sort the nodes of a DAG into topolgical order.
template<typename Graph , typename NodeMap >
bool	checkedTopologicalSort (const Graph &graph, NodeMap &order)
	Sort the nodes of a DAG into topolgical order.
template<typename Graph >
bool	dag (const Graph &graph)
	Check that the given directed graph is a DAG.
template<typename UGraph >
bool	acyclic (const UGraph &graph)
	Check that the given undirected graph is acyclic.
template<typename UGraph >
bool	tree (const UGraph &graph)
	Check that the given undirected graph is tree.
template<typename UGraph >
bool	bipartite (const UGraph &graph)
	Check if the given undirected graph is bipartite or not.
template<typename UGraph , typename NodeMap >
bool	bipartitePartitions (const UGraph &graph, NodeMap &partMap)
	Check if the given undirected graph is bipartite or not.

---

Function Documentation

bool lemon::euler

(

const Graph &

g

)

[inline]

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

)

[inline]

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

)

[inline]

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
	)			[inline]

Find the connected components of an undirected graph.

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

)

[inline]

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

)

[inline]

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 in the same class if they 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
	)			[inline]

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. In addition, the numbering of components will satisfy that there is no edge going from a higher numbered component to a lower.

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 value 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
	)			[inline]

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

)

[inline]

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.

int countBiNodeConnectedComponents

(

const UGraph &

graph

)

[inline]

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
	)			[inline]

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.

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
	)			[inline]

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

)

[inline]

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.

int countBiEdgeConnectedComponents

(

const UGraph &

graph

)

[inline]

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
	)			[inline]

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.

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
	)			[inline]

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
	)			[inline]

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
	)			[inline]

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

)

[inline]

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

)

[inline]

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

)

[inline]

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