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.

../_images/connected_components.png

Classes

Class

Description

DiEulerIt

Euler tour iterator for digraphs.

EulerIt

Euler tour iterator for graphs.

Other classes of its headers

Class

Description

Vf2WizardBase

Vf2Wizard

Auxiliary class for the function-type interface of VF2 algorithm.

Vf2ppWizardBase

Vf2ppWizard

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.

Note

By definition, the empty graph is connected.

Returns:

true if 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.

Note

By definition, the empty graph consists of zero connected components.

Returns:

The number of connected components.

template< class Graph , class NodeMap >
int connectedComponents(
const Graph & graph,
NodeMap & compMap
)

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.

../_images/connected_components.png

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

connected()

Note

By definition, the empty digraph is strongly connected.

Returns:

true if 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(
const Digraph & digraph,
NodeMap & compMap
)

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.

../_images/strongly_connected_components.png

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(
const Digraph & digraph,
ArcMap & cutMap
)

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 true for 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:

true if 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.

Returns:

The number of bi-node-connected components.

template< typename Graph , typename EdgeMap >
int biNodeConnectedComponents(
const Graph & graph,
EdgeMap & compMap
)

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.

../_images/node_biconnected_components.png

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(
const Graph & graph,
NodeMap & cutMap
)

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.

Parameters:
  • graph – The undirected graph.

  • cutMap – [out] A writable node map. The values will be set to true for 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:

true if 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.

Returns:

The number of bi-edge-connected components.

template< typename Graph , typename NodeMap >
int biEdgeConnectedComponents(
const Graph & graph,
NodeMap & compMap
)

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.

../_images/edge_biconnected_components.png

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(
const Graph & graph,
EdgeMap & cutMap
)

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.

Parameters:
  • graph – The undirected graph.

  • cutMap – [out] A writable edge map. The values will be set to true for 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

acyclic()

Returns:

true if there is no directed cycle in the digraph.

template< typename Digraph , typename NodeMap >
void topologicalSort(
const Digraph & digraph,
NodeMap & order
)

Sort the nodes of a DAG into topolgical order.

This function sorts the nodes of the given acyclic digraph (DAG) into topolgical order.

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(
const Digraph & digraph,
NodeMap & order
)

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.

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:

false if 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

dag()

Returns:

true if 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.

Returns:

true if 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.

Returns:

true if the graph is bipartite.

template< typename Graph , typename NodeMap >
bool bipartitePartitions(
const Graph & graph,
NodeMap & partMap
)

Find the bipartite partitions of an undirected graph.

This function checks whether the given undirected graph is bipartite and gives back the bipartite partitions.

../_images/bipartite_partitions.png

See also

bipartite()

Parameters:
  • graph – The undirected graph.

  • partMap – [out] A writable node map of bool (or convertible) value type. The values will be set to true for one component and false for the other one.

Returns:

true if the graph is bipartite, false otherwise.

template< typename Graph >
bool loopFree( const Graph & graph )

Check whether the given graph contains no loop arcs/edges.

This function returns true if 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 true if 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 true if 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.

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.

See also

DiEulerIt, EulerIt

Note

There are (di)graphs that are not Eulerian, but still have an Euler tour, since they may contain isolated nodes.