Open
Graph Drawing
Framework

 v. snapshot-2018-03-28
 

Connectivity in Graphs and Digraphs

Provides functions dealing with connectivity in graphs and clustered. More...

Methods for clustered graphs

bool ogdf::isCConnected (const ClusterGraph &C)
 Returns true iff cluster graph C is c-connected. More...
 
void ogdf::makeCConnected (ClusterGraph &C, Graph &G, List< edge > &addedEdges, bool simple=true)
 Makes a cluster graph c-connected by adding edges. More...
 

Methods for connectivity

bool ogdf::isConnected (const Graph &G)
 Returns true iff G is connected. More...
 
void ogdf::makeConnected (Graph &G, List< edge > &added)
 Makes G connected by adding a minimum number of edges. More...
 
void ogdf::makeConnected (Graph &G)
 makes G connected by adding a minimum number of edges. More...
 
int ogdf::connectedComponents (const Graph &G, NodeArray< int > &component, List< node > *isolated=nullptr)
 Computes the connected components of G and optionally generates a list of isolated nodes. More...
 
int ogdf::connectedIsolatedComponents (const Graph &G, List< node > &isolated, NodeArray< int > &component)
 Computes the connected components of G and optionally generates a list of isolated nodes. More...
 
bool ogdf::isBiconnected (const Graph &G, node &cutVertex)
 Returns true iff G is biconnected. More...
 
bool ogdf::isBiconnected (const Graph &G)
 Returns true iff G is biconnected. More...
 
void ogdf::makeBiconnected (Graph &G, List< edge > &added)
 Makes G biconnected by adding edges. More...
 
void ogdf::makeBiconnected (Graph &G)
 Makes G biconnected by adding edges. More...
 
int ogdf::biconnectedComponents (const Graph &G, EdgeArray< int > &component, int &nonEmptyComponents)
 Computes the biconnected components of G. More...
 
int ogdf::biconnectedComponents (const Graph &G, EdgeArray< int > &component)
 Computes the biconnected components of G. More...
 
bool ogdf::isTwoEdgeConnected (const Graph &graph)
 Returns true iff graph is 2-edge-connected. More...
 
bool ogdf::isTriconnected (const Graph &G, node &s1, node &s2)
 Returns true iff G is triconnected. More...
 
bool ogdf::isTriconnected (const Graph &G)
 Returns true iff G is triconnected. More...
 
bool ogdf::isTriconnectedPrimitive (const Graph &G, node &s1, node &s2)
 Returns true iff G is triconnected (using a quadratic time algorithm!). More...
 
bool ogdf::isTriconnectedPrimitive (const Graph &G)
 Returns true iff G is triconnected (using a quadratic time algorithm!). More...
 
void ogdf::triangulate (Graph &G)
 Triangulates a planarly embedded graph G by adding edges. More...
 
bool ogdf::isTwoEdgeConnected (const Graph &graph, edge &bridge)
 Returns true iff graph is 2-edge-connected. More...
 

Methods for directed graphs

int ogdf::strongComponents (const Graph &G, NodeArray< int > &component)
 Computes the strongly connected components of the digraph G. More...
 

Detailed Description

Provides functions dealing with connectivity in graphs and clustered.

Function Documentation

◆ biconnectedComponents() [1/2]

int ogdf::biconnectedComponents ( const Graph G,
EdgeArray< int > &  component,
int &  nonEmptyComponents 
)

Computes the biconnected components of G.

Assigns component numbers (0, 1, ...) to the edges of G. The component number of each edge is stored in the edge array component. Each self-loop is counted as one biconnected component and has its own component number.

Parameters
Gis the input graph.
componentis assigned a mapping from edges to component numbers.
Returns
the number of biconnected components (including self-loops) + the number of nodes without neighbours (that is, the number of nodes who have no incident edges or whose incident edges are all self-loops).
Parameters
nonEmptyComponentsis the number of non-empty components. The indices of component range from 0 to nonEmptyComponents - 1.

◆ biconnectedComponents() [2/2]

int ogdf::biconnectedComponents ( const Graph G,
EdgeArray< int > &  component 
)
inline

Computes the biconnected components of G.

Assigns component numbers (0, 1, ...) to the edges of G. The component number of each edge is stored in the edge array component. Each self-loop is counted as one biconnected component and has its own component number.

Parameters
Gis the input graph.
componentis assigned a mapping from edges to component numbers.
Returns
the number of biconnected components (including self-loops) + the number of nodes without neighbours (that is, the number of nodes who have no incident edges or whose incident edges are all self-loops).

Definition at line 524 of file simple_graph_alg.h.

◆ connectedComponents()

int ogdf::connectedComponents ( const Graph G,
NodeArray< int > &  component,
List< node > *  isolated = nullptr 
)

Computes the connected components of G and optionally generates a list of isolated nodes.

Assigns component numbers (0, 1, ...) to the nodes of G. The component number of each node is stored in the node array component.

Parameters
Gis the input graph.
componentis assigned a mapping from nodes to component numbers.
isolatedis assigned the list of isolated nodes. An isolated node is a node without incident edges.
Returns
the number of connected components.

◆ connectedIsolatedComponents()

int ogdf::connectedIsolatedComponents ( const Graph G,
List< node > &  isolated,
NodeArray< int > &  component 
)
inline

Computes the connected components of G and optionally generates a list of isolated nodes.

Deprecated:
"connectedComponents() should be used instead."

Assigns component numbers (0, 1, ...) to the nodes of G. The component number of each node is stored in the node array component.

Parameters
Gis the input graph.
componentis assigned a mapping from nodes to component numbers.
isolatedis assigned the list of isolated nodes. An isolated node is a node without incident edges.
Returns
the number of connected components.

Definition at line 450 of file simple_graph_alg.h.

◆ isBiconnected() [1/2]

bool ogdf::isBiconnected ( const Graph G,
node cutVertex 
)

Returns true iff G is biconnected.

Parameters
Gis the input graph.
cutVertexIf false is returned and G is connected, cutVertex is assigned a cut vertex in G, else it is assigned nullptr.

◆ isBiconnected() [2/2]

bool ogdf::isBiconnected ( const Graph G)
inline

Returns true iff G is biconnected.

Parameters
Gis the input graph.

Definition at line 474 of file simple_graph_alg.h.

◆ isCConnected()

bool ogdf::isCConnected ( const ClusterGraph C)

Returns true iff cluster graph C is c-connected.

◆ isConnected()

bool ogdf::isConnected ( const Graph G)

Returns true iff G is connected.

Parameters
Gis the input graph.
Returns
true if G is connected, false otherwise.

◆ isTriconnected() [1/2]

bool ogdf::isTriconnected ( const Graph G,
node s1,
node s2 
)

Returns true iff G is triconnected.

If G is not triconnected then

  • s1 and s2 are both nullptr if G is not connected.
  • s1 is a cut vertex and s2 is nullptr if G is connected but not biconnected.
  • s1 and s2 are a separation pair if G is bi- but not triconnected.
Parameters
Gis the input graph.
s1is assigned a cut vertex or one node of a separation pair, if G is not triconnected (see above).
s2is assigned one node of a separation pair, if G is not triconnected (see above).
Returns
true if G is triconnected, false otherwise.

◆ isTriconnected() [2/2]

bool ogdf::isTriconnected ( const Graph G)
inline

Returns true iff G is triconnected.

Parameters
Gis the input graph.
Returns
true if G is triconnected, false otherwise.

Definition at line 580 of file simple_graph_alg.h.

◆ isTriconnectedPrimitive() [1/2]

bool ogdf::isTriconnectedPrimitive ( const Graph G,
node s1,
node s2 
)

Returns true iff G is triconnected (using a quadratic time algorithm!).

If G is not triconnected then

  • s1 and s2 are both nullptr if G is not connected.
  • s1 is a cut vertex and s2 is nullptr if G is connected but not biconnected.
  • s1 and s2 are a separation pair if G is bi- but not triconnected.
Warning
This method has quadratic running time. An efficient linear time version is provided by isTriconnected().
Parameters
Gis the input graph.
s1is assigned a cut vertex of one node of a separation pair, if G is not triconnected (see above).
s2is assigned one node of a separation pair, if G is not triconnected (see above).
Returns
true if G is triconnected, false otherwise.

◆ isTriconnectedPrimitive() [2/2]

bool ogdf::isTriconnectedPrimitive ( const Graph G)
inline

Returns true iff G is triconnected (using a quadratic time algorithm!).

Warning
This method has quadratic running time. An efficient linear time version is provided by isTriconnected().
Parameters
Gis the input graph.
Returns
true if G is triconnected, false otherwise.

Definition at line 616 of file simple_graph_alg.h.

◆ isTwoEdgeConnected() [1/2]

bool ogdf::isTwoEdgeConnected ( const Graph graph,
edge bridge 
)

Returns true iff graph is 2-edge-connected.

Implementation of the algorithm to determine 2-edge-connectivity from the following publication:

Jens M. Schmidt: A Simple Test on 2-Vertex- and 2-Edge-Connectivity. Information Processing Letters (2013)

It runs in O(|E|+|V|) as it relies on two DFS.

Parameters
graphis the input graph.
bridgeIf false is returned and graph is connected, bridge is assigned a bridge in graph, else it is assigned nullptr

◆ isTwoEdgeConnected() [2/2]

bool ogdf::isTwoEdgeConnected ( const Graph graph)
inline

Returns true iff graph is 2-edge-connected.

Implementation of the algorithm to determine 2-edge-connectivity from the following publication:

Jens M. Schmidt: A Simple Test on 2-Vertex- and 2-Edge-Connectivity. Information Processing Letters (2013)

It runs in O(|E|+|V|) as it relies on two DFS.

Parameters
graphis the input graph.

Definition at line 550 of file simple_graph_alg.h.

◆ makeBiconnected() [1/2]

void ogdf::makeBiconnected ( Graph G,
List< edge > &  added 
)

Makes G biconnected by adding edges.

Parameters
Gis the input graph.
addedis assigned the list of inserted edges.

◆ makeBiconnected() [2/2]

void ogdf::makeBiconnected ( Graph G)
inline

Makes G biconnected by adding edges.

Parameters
Gis the input graph.

Definition at line 496 of file simple_graph_alg.h.

◆ makeCConnected()

void ogdf::makeCConnected ( ClusterGraph C,
Graph G,
List< edge > &  addedEdges,
bool  simple = true 
)

Makes a cluster graph c-connected by adding edges.

Parameters
Cis the input cluster graph.
Gis the graph associated with the cluster graph C; the function adds new edges to this graph.
addedEdgesis assigned the list of newly created edges.
simpleselects the method used: If set to true, a simple variant that does not guarantee to preserve planarity is used.

◆ makeConnected() [1/2]

void ogdf::makeConnected ( Graph G,
List< edge > &  added 
)

Makes G connected by adding a minimum number of edges.

Parameters
Gis the input graph.
addedis assigned the added edges.

◆ makeConnected() [2/2]

void ogdf::makeConnected ( Graph G)
inline

makes G connected by adding a minimum number of edges.

Parameters
Gis the input graph.

Definition at line 420 of file simple_graph_alg.h.

◆ strongComponents()

int ogdf::strongComponents ( const Graph G,
NodeArray< int > &  component 
)

Computes the strongly connected components of the digraph G.

The function implements the algorithm by Tarjan.

Parameters
Gis the input graph.
componentis assigned a mapping from nodes to component numbers (0, 1, ...).
Returns
the number of strongly connected components.

◆ triangulate()

void ogdf::triangulate ( Graph G)

Triangulates a planarly embedded graph G by adding edges.

The result of this function is that G is made maximally planar by adding new edges. G will also be planarly embedded such that each face is a triangle.

Precondition
G is planar, simple and represents a combinatorial embedding (i.e. G is planarly embedded).
Parameters
Gis the input graph to which edges will be added.