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 multi-graph 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, ArrayBuffer< node > *reprs=nullptr) |
Computes the connected components of G and optionally generates a list of isolated nodes. More... | |
int | ogdf::connectedComponents (const Graph &G) |
Computes the amount of connected components of G . More... | |
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 non-cut vertices. 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... | |
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 non-cut vertices. 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... | |
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 self-loop 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 595 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 self-loop 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 non-empty components. The indices of component range from 0 to nonEmptyComponents - 1. |
|
inline |
Computes the amount of connected components of G
.
G | is the input graph. |
Definition at line 489 of file simple_graph_alg.h.
int ogdf::connectedComponents | ( | const Graph & | G, |
NodeArray< int > & | component, | ||
List< node > * | isolated = nullptr , |
||
ArrayBuffer< node > * | reprs = 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 | if non-null, will contain the list of isolated nodes afterwards. An isolated node is a node without incident edges. |
reprs | if non-null, will contain a node from component c at index c afterwards. |
|
inline |
Definition at line 500 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 non-cut 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 non-cut vertex. |
|
inline |
Finds cut vertices and potential edges that could be added to turn the cut vertices into non-cut 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 526 of file simple_graph_alg.h.
|
inline |
Returns true iff G
is biconnected.
G | is the input graph. |
Definition at line 547 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 c-connected.
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 648 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 682 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 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.
graph | is the input graph. |
Definition at line 620 of file simple_graph_alg.h.
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.
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 567 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 c-connected 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 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, ...). |
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. |