Provides functions dealing with connectivity in graphs and clustered. More...
Classes  
class  ogdf::ConnectivityTester 
Naive implementation for testing the connectivity of a graph. More...  
class  ogdf::MaxAdjOrdering 
Calculate one or all Maximum Adjacency Ordering(s) of a given simple undirected graph. More...  
class  ogdf::Triconnectivity 
realizes Hopcroft/Tarjan algorithm for finding the triconnected components of a biconnected multigraph More...  
Methods for clustered graphs  
bool  ogdf::isCConnected (const ClusterGraph &C) 
Returns true iff cluster graph C is cconnected.  
void  ogdf::makeCConnected (ClusterGraph &C, Graph &G, List< edge > &addedEdges, bool simple=true) 
Makes a cluster graph cconnected by adding edges.  
Methods for connectivity  
bool  ogdf::isConnected (const Graph &G) 
Returns true iff G is connected.  
void  ogdf::makeConnected (Graph &G, List< edge > &added) 
Makes G connected by adding a minimum number of edges.  
void  ogdf::makeConnected (Graph &G) 
makes G connected by adding a minimum number of edges.  
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.  
int  ogdf::connectedComponents (const Graph &G) 
Computes the amount of connected components of G .  
bool  ogdf::findCutVertices (const Graph &G, ArrayBuffer< node > &cutVertices, bool onlyOne=false) 
Finds cut vertices and potential edges that could be added to turn the cut vertices into noncut vertices.  
bool  ogdf::isBiconnected (const Graph &G, node &cutVertex) 
Returns true iff G is biconnected.  
bool  ogdf::isBiconnected (const Graph &G) 
Returns true iff G is biconnected.  
void  ogdf::makeBiconnected (Graph &G, List< edge > &added) 
Makes G biconnected by adding edges.  
void  ogdf::makeBiconnected (Graph &G) 
Makes G biconnected by adding edges.  
int  ogdf::biconnectedComponents (const Graph &G, EdgeArray< int > &component, int &nonEmptyComponents) 
Computes the biconnected components of G .  
int  ogdf::biconnectedComponents (const Graph &G, EdgeArray< int > &component) 
Computes the biconnected components of G .  
bool  ogdf::isTwoEdgeConnected (const Graph &graph) 
Returns true iff graph is 2edgeconnected.  
bool  ogdf::isTriconnected (const Graph &G, node &s1, node &s2) 
Returns true iff G is triconnected.  
bool  ogdf::isTriconnected (const Graph &G) 
Returns true iff G is triconnected.  
bool  ogdf::isTriconnectedPrimitive (const Graph &G, node &s1, node &s2) 
Returns true iff G is triconnected (using a quadratic time algorithm!).  
bool  ogdf::isTriconnectedPrimitive (const Graph &G) 
Returns true iff G is triconnected (using a quadratic time algorithm!).  
void  ogdf::triangulate (Graph &G) 
Triangulates a planarly embedded graph G by adding edges.  
int  ogdf::connectedIsolatedComponents (const Graph &G, List< node > &isolated, NodeArray< int > &component) 
bool  ogdf::findCutVertices (const Graph &G, ArrayBuffer< node > &cutVertices, ArrayBuffer< Tuple2< node, node > > &addEdges, bool onlyOne=false) 
Finds cut vertices and potential edges that could be added to turn the cut vertices into noncut vertices.  
bool  ogdf::isTwoEdgeConnected (const Graph &graph, edge &bridge) 
Returns true iff graph is 2edgeconnected.  
Methods for directed graphs  
int  ogdf::strongComponents (const Graph &G, NodeArray< int > &component) 
Computes the strongly connected components of the digraph G .  
Provides functions dealing with connectivity in graphs and clustered.
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 selfloop is counted as one biconnected component and has its own component number.
G  is the input graph. 
component  is assigned a mapping from edges to component numbers. 
Definition at line 594 of file simple_graph_alg.h.
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 selfloop is counted as one biconnected component and has its own component number.
G  is the input graph. 
component  is assigned a mapping from edges to component numbers. 
nonEmptyComponents  is the number of nonempty components. The indices of component range from 0 to nonEmptyComponents  1. 
Computes the amount of connected components of G
.
G  is the input graph. 
Definition at line 488 of file simple_graph_alg.h.
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
.
G  is the input graph. 
component  is assigned a mapping from nodes to component numbers. 
isolated  is assigned the list of isolated nodes. An isolated node is a node without incident edges. 

inline 
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
.
G  is the input graph. 
component  is assigned a mapping from nodes to component numbers. 
isolated  is assigned the list of isolated nodes. An isolated node is a node without incident edges. 
Definition at line 499 of file simple_graph_alg.h.
bool ogdf::findCutVertices  (  const Graph &  G, 
ArrayBuffer< node > &  cutVertices,  
ArrayBuffer< Tuple2< node, node > > &  addEdges,  
bool  onlyOne = false 

) 
Finds cut vertices and potential edges that could be added to turn the cut vertices into noncut vertices.
G
must be connected.G  is the graph whose cut vertices should be found. 
cutVertices  is assigned the cut vertices of the graph. 
onlyOne  should be set to true if the search should stop after finding one cut vertex, to false if all cut vertices should be found. 
addEdges  is assigned the tuples of nodes which have to be connected in order to turn each cut vertex into a noncut vertex. 

inline 
Finds cut vertices and potential edges that could be added to turn the cut vertices into noncut vertices.
G
must be connected.G  is the graph whose cut vertices should be found. 
cutVertices  is assigned the cut vertices of the graph. 
onlyOne  should be set to true if the search should stop after finding one cut vertex, to false if all cut vertices should be found. 
Definition at line 525 of file simple_graph_alg.h.
Returns true iff G
is biconnected.
G  is the input graph. 
Definition at line 546 of file simple_graph_alg.h.
Returns true iff G
is biconnected.
G  is the input graph. 
cutVertex  If false is returned and G is connected, cutVertex is assigned a cut vertex in G , else it is assigned nullptr. 
bool ogdf::isCConnected  (  const ClusterGraph &  C  ) 
Returns true iff cluster graph C
is cconnected.
Returns true iff G
is connected.
G  is the input graph. 
G
is connected, false otherwise. Returns true iff G
is triconnected.
G  is the input graph. 
G
is triconnected, false otherwise. Definition at line 647 of file simple_graph_alg.h.
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.G  is the input graph. 
s1  is assigned a cut vertex or one node of a separation pair, if G is not triconnected (see above). 
s2  is assigned one node of a separation pair, if G is not triconnected (see above). 
G
is triconnected, false otherwise. Returns true iff G
is triconnected (using a quadratic time algorithm!).
G  is the input graph. 
G
is triconnected, false otherwise. Definition at line 681 of file simple_graph_alg.h.
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.G  is the input graph. 
s1  is assigned a cut vertex of one node of a separation pair, if G is not triconnected (see above). 
s2  is assigned one node of a separation pair, if G is not triconnected (see above). 
G
is triconnected, false otherwise. Returns true iff graph
is 2edgeconnected.
Implementation of the algorithm to determine 2edgeconnectivity from the following publication:
Jens M. Schmidt: A Simple Test on 2Vertex and 2EdgeConnectivity. Information Processing Letters (2013)
It runs in O(E+V) as it relies on two DFS.
graph  is the input graph. 
Definition at line 619 of file simple_graph_alg.h.
Returns true iff graph
is 2edgeconnected.
Implementation of the algorithm to determine 2edgeconnectivity from the following publication:
Jens M. Schmidt: A Simple Test on 2Vertex and 2EdgeConnectivity. Information Processing Letters (2013)
It runs in O(E+V) as it relies on two DFS.
graph  is the input graph. 
bridge  If false is returned and graph is connected, bridge is assigned a bridge in graph , else it is assigned nullptr 
Makes G
biconnected by adding edges.
G  is the input graph. 
Definition at line 566 of file simple_graph_alg.h.
Makes G
biconnected by adding edges.
G  is the input graph. 
added  is assigned the list of inserted edges. 
void ogdf::makeCConnected  (  ClusterGraph &  C, 
Graph &  G,  
List< edge > &  addedEdges,  
bool  simple = true 

) 
Makes a cluster graph cconnected by adding edges.
C  is the input cluster graph. 
G  is the graph associated with the cluster graph C ; the function adds new edges to this graph. 
addedEdges  is assigned the list of newly created edges. 
simple  selects the method used: If set to true, a simple variant that does not guarantee to preserve planarity is used. 
makes G
connected by adding a minimum number of edges.
G  is the input graph. 
Definition at line 459 of file simple_graph_alg.h.
Makes G
connected by adding a minimum number of edges.
G  is the input graph. 
added  is assigned the added edges. 
Computes the strongly connected components of the digraph G
.
The function implements the algorithm by Tarjan.
G  is the input graph. 
component  is assigned a mapping from nodes to component numbers (0, 1, ...). 
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.
G
is planar, simple and represents a combinatorial embedding (i.e. G
is planarly embedded).G  is the input graph to which edges will be added. 