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 cconnected. More...  
void  ogdf::makeCConnected (ClusterGraph &C, Graph &G, List< edge > &addedEdges, bool simple=true) 
Makes a cluster graph cconnected 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 2edgeconnected. 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 2edgeconnected. More...  
Methods for directed graphs  
int  ogdf::strongComponents (const Graph &G, NodeArray< int > &component) 
Computes the strongly connected components of the digraph G . More...  
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 578 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. 
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 504 of file simple_graph_alg.h.

inline 
Returns true iff G
is biconnected.
G  is the input graph. 
Definition at line 528 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.
bool ogdf::isConnected  (  const Graph &  G  ) 
Returns true iff G
is connected.
G  is the input graph. 
G
is connected, false otherwise.

inline 
Returns true iff G
is triconnected.
G  is the input graph. 
G
is triconnected, false otherwise. Definition at line 634 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.

inline 
Returns true iff G
is triconnected (using a quadratic time algorithm!).
G  is the input graph. 
G
is triconnected, false otherwise. Definition at line 670 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.

inline 
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 604 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 

inline 
Makes G
biconnected by adding edges.
G  is the input graph. 
Definition at line 550 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. 

inline 
makes G
connected by adding a minimum number of edges.
G  is the input graph. 
Definition at line 474 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, ...). 
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.
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. 