Connectivity and Other Graph Properties
The same group on the Doxygen site.
- group Connectivity and Other Graph Properties
Algorithms for discovering the graph properties.
This group contains the algorithms for discovering the graph properties like connectivity, bipartiteness, euler property, simplicity etc.

Classes
Class |
Description |
|---|---|
Euler tour iterator for digraphs. |
|
Euler tour iterator for graphs. |
Other classes of its headers
Class |
Description |
|---|---|
Auxiliary class for the function-type interface of VF2 algorithm. |
|
Auxiliary class for the function-type interface of VF2 Plus Plus algorithm. |
Functions and other members
-
template< typename Graph >
bool connected( const Graph & graph ) Check whether an undirected graph is connected.
This function checks whether the given undirected graph is connected, i.e. there is a path between any two nodes in the graph.
See also
Note
By definition, the empty graph is connected.
- Returns:
trueif the graph is connected.
-
template< typename Graph >
int countConnectedComponents( const Graph & graph ) Count the number of connected components of an undirected graph.
This function counts the number of connected components of the given undirected graph.
The connected components are the classes of an equivalence relation on the nodes of an undirected graph. Two nodes are in the same class if they are connected with a path.
See also
Note
By definition, the empty graph consists of zero connected components.
- Returns:
The number of connected components.
-
template< class Graph , class NodeMap >
int connectedComponents(
) Find the connected components of an undirected graph.
This function finds the connected components of the given undirected graph.
The connected components are the classes of an equivalence relation on the nodes of an undirected graph. Two nodes are in the same class if they are connected with a path.

See also
Note
By definition, the empty graph consists of zero connected components.
- Parameters:
graph – The undirected graph.
compMap – [out] A writable node map. The values will be set from 0 to the number of the connected components minus one. Each value of the map will be set exactly once, and the values of a certain component will be set continuously.
- Returns:
The number of connected components.
-
template< typename Digraph >
bool stronglyConnected( const Digraph & digraph ) Check whether a directed graph is strongly connected.
This function checks whether the given directed graph is strongly connected, i.e. any two nodes of the digraph are connected with directed paths in both direction.
See also
Note
By definition, the empty digraph is strongly connected.
- Returns:
trueif the digraph is strongly connected.
-
template< typename Digraph >
int countStronglyConnectedComponents( const Digraph & digraph ) Count the number of strongly connected components of a directed graph.
This function counts the number of strongly connected components of the given directed graph.
The strongly connected components are the classes of an equivalence relation on the nodes of a digraph. Two nodes are in the same class if they are connected with directed paths in both direction.
Note
By definition, the empty digraph has zero strongly connected components.
- Returns:
The number of strongly connected components.
-
template< typename Digraph , typename NodeMap >
int stronglyConnectedComponents(
) Find the strongly connected components of a directed graph.
This function finds the strongly connected components of the given directed graph. In addition, the numbering of the components will satisfy that there is no arc going from a higher numbered component to a lower one (i.e. it provides a topological order of the components).
The strongly connected components are the classes of an equivalence relation on the nodes of a digraph. Two nodes are in the same class if they are connected with directed paths in both direction.

Note
By definition, the empty digraph has zero strongly connected components.
- Parameters:
digraph – The digraph.
compMap – [out] 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, and the values of a certain component will be set continuously.
- Returns:
The number of strongly connected components.
-
template< typename Digraph , typename ArcMap >
int stronglyConnectedCutArcs(
) Find the cut arcs of the strongly connected components.
This function finds the cut arcs of the strongly connected components of the given digraph.
The strongly connected components are the classes of an equivalence relation on the nodes of a digraph. Two nodes are in the same class if they are connected with directed paths in both direction. The strongly connected components are separated by the cut arcs.
- Parameters:
digraph – The digraph.
cutMap – [out] A writable arc map. The values will be set to
truefor the cut arcs (exactly once for each cut arc), and will not be changed for other arcs.
- Returns:
The number of cut arcs.
-
template< typename Graph >
bool biNodeConnected( const Graph & graph ) Check whether an undirected graph is bi-node-connected.
This function checks whether the given undirected graph is bi-node-connected, i.e. a connected graph without articulation node.
Note
By definition,
a graph consisting of zero or one node is bi-node-connected,
a graph consisting of two isolated nodes is not bi-node-connected and
a graph consisting of two nodes connected by an edge is bi-node-connected.
- Returns:
trueif the graph bi-node-connected.
-
template< typename Graph >
int countBiNodeConnectedComponents( const Graph & graph ) Count the number of bi-node-connected components of an undirected graph.
This function counts the number of bi-node-connected components of the given undirected graph.
The bi-node-connected components are the classes of an equivalence relation on the edges of a undirected graph. Two edges are in the same class if they are on same circle.
See also
- Returns:
The number of bi-node-connected components.
-
template< typename Graph , typename EdgeMap >
int biNodeConnectedComponents(
) Find the bi-node-connected components of an undirected graph.
This function finds the bi-node-connected components of the given undirected graph.
The bi-node-connected components are the classes of an equivalence relation on the edges of a undirected graph. Two edges are in the same class if they are on same circle.

- Parameters:
graph – The undirected graph.
compMap – [out] A writable edge map. The values will be set from 0 to the number of the bi-node-connected components minus one. Each value of the map will be set exactly once, and the values of a certain component will be set continuously.
- Returns:
The number of bi-node-connected components.
-
template< typename Graph , typename NodeMap >
int biNodeConnectedCutNodes(
) Find the bi-node-connected cut nodes in an undirected graph.
This function finds the bi-node-connected cut nodes in the given undirected graph.
The bi-node-connected components are the classes of an equivalence relation on the edges of a undirected graph. Two edges are in the same class if they are on same circle. The bi-node-connected components are separted by the cut nodes of the components.
See also
- Parameters:
graph – The undirected graph.
cutMap – [out] A writable node map. The values will be set to
truefor the nodes that separate two or more components, i.e., whose removal increases the number of the connected components (exactly once for each cut node), and will not be changed for other nodes. A loop forms a component of its own, but it makes no node a cut node.
- Returns:
The number of the cut nodes.
-
template< typename Graph >
bool biEdgeConnected( const Graph & graph ) Check whether an undirected graph is bi-edge-connected.
This function checks whether the given undirected graph is bi-edge-connected, i.e. any two nodes are connected with at least two edge-disjoint paths.
Note
By definition, the empty graph is bi-edge-connected.
- Returns:
trueif the graph is bi-edge-connected.
-
template< typename Graph >
int countBiEdgeConnectedComponents( const Graph & graph ) Count the number of bi-edge-connected components of an undirected graph.
This function counts the number of bi-edge-connected components of the given undirected graph.
The bi-edge-connected components are the classes of an equivalence relation on the nodes of an undirected graph. Two nodes are in the same class if they are connected with at least two edge-disjoint paths.
See also
- Returns:
The number of bi-edge-connected components.
-
template< typename Graph , typename NodeMap >
int biEdgeConnectedComponents(
) Find the bi-edge-connected components of an undirected graph.
This function finds the bi-edge-connected components of the given undirected graph.
The bi-edge-connected components are the classes of an equivalence relation on the nodes of an undirected graph. Two nodes are in the same class if they are connected with at least two edge-disjoint paths.

- Parameters:
graph – The undirected graph.
compMap – [out] A writable node map. The values will be set from 0 to the number of the bi-edge-connected components minus one. Each value of the map will be set exactly once, and the values of a certain component will be set continuously.
- Returns:
The number of bi-edge-connected components.
-
template< typename Graph , typename EdgeMap >
int biEdgeConnectedCutEdges(
) Find the bi-edge-connected cut edges in an undirected graph.
This function finds the bi-edge-connected cut edges in the given undirected graph.
The bi-edge-connected components are the classes of an equivalence relation on the nodes of an undirected graph. Two nodes are in the same class if they are connected with at least two edge-disjoint paths. The bi-edge-connected components are separted by the cut edges of the components.
See also
- Parameters:
graph – The undirected graph.
cutMap – [out] A writable edge map. The values will be set to
truefor the cut edges (exactly once for each cut edge), and will not be changed for other edges.
- Returns:
The number of cut edges.
-
template< typename Digraph >
bool dag( const Digraph & digraph ) Check whether a digraph is DAG.
This function checks whether the given digraph is DAG, i.e. Directed Acyclic Graph.
See also
- Returns:
trueif there is no directed cycle in the digraph.
-
template< typename Digraph , typename NodeMap >
void topologicalSort(
) Sort the nodes of a DAG into topolgical order.
This function sorts the nodes of the given acyclic digraph (DAG) into topolgical order.
See also
- Parameters:
digraph – The digraph, which must be DAG.
order – [out] A writable node map. The values will be set from 0 to the number of the nodes in the digraph minus one. Each value of the map will be set exactly once, and the values will be set descending order.
-
template< typename Digraph , typename NodeMap >
bool checkedTopologicalSort(
) Sort the nodes of a DAG into topolgical order.
This function sorts the nodes of the given acyclic digraph (DAG) into topolgical order and also checks whether the given digraph is DAG.
See also
- Parameters:
digraph – The digraph.
order – [out] A readable and writable node map. The values will be set from 0 to the number of the nodes in the digraph minus one. Each value of the map will be set exactly once, and the values will be set descending order.
- Returns:
falseif the digraph is not DAG.
-
template< typename Graph >
bool acyclic( const Graph & graph ) Check whether an undirected graph is acyclic.
This function checks whether the given undirected graph is acyclic.
See also
- Returns:
trueif there is no cycle in the graph.
-
template< typename Graph >
bool tree( const Graph & graph ) Check whether an undirected graph is tree.
This function checks whether the given undirected graph is tree.
See also
- Returns:
trueif the graph is acyclic and connected.
-
template< typename Graph >
bool bipartite( const Graph & graph ) Check whether an undirected graph is bipartite.
The function checks whether the given undirected graph is bipartite.
See also
- Returns:
trueif the graph is bipartite.
-
template< typename Graph , typename NodeMap >
bool bipartitePartitions(
) Find the bipartite partitions of an undirected graph.
This function checks whether the given undirected graph is bipartite and gives back the bipartite partitions.

See also
- Parameters:
graph – The undirected graph.
partMap – [out] A writable node map of
bool(or convertible) value type. The values will be set totruefor one component andfalsefor the other one.
- Returns:
trueif the graph is bipartite,falseotherwise.
-
template< typename Graph >
bool loopFree( const Graph & graph ) Check whether the given graph contains no loop arcs/edges.
This function returns
trueif there are no loop arcs/edges in the given graph. It works for both directed and undirected graphs.
-
template< typename Graph >
bool parallelFree( const Graph & graph ) Check whether the given graph contains no parallel arcs/edges.
This function returns
trueif there are no parallel arcs/edges in the given graph. It works for both directed and undirected graphs; in the latter, a single loop at a node is not parallel to itself, although both of its arcs leave the node and enter it.
-
template< typename Graph >
bool simpleGraph( const Graph & graph ) Check whether the given graph is simple.
This function returns
trueif the given graph is simple, i.e. it contains no loop arcs/edges and no parallel arcs/edges. The function works for both directed and undirected graphs.See also
-
template< typename GR >
bool eulerian( const GR & g ) Check if the given graph is Eulerian.
This function checks if the given graph is Eulerian. It works for both directed and undirected graphs.
By definition, a digraph is called Eulerian if and only if it is connected and the number of incoming and outgoing arcs are the same for each node. Similarly, an undirected graph is called Eulerian if and only if it is connected and the number of incident edges is even for each node.
Note
There are (di)graphs that are not Eulerian, but still have an Euler tour, since they may contain isolated nodes.