Naive implementation for testing the connectivity of a graph.
More...
#include <ogdf/graphalg/ConnectivityTester.h>
Naive implementation for testing the connectivity of a graph.
The connectivity is computed utilizing ogdf::MaxFlowModule.
Note that the runtime might be improved by implementing a Gomory-Hu Tree.
Definition at line 49 of file ConnectivityTester.h.
◆ ConnectivityTester() [1/2]
ogdf::ConnectivityTester::ConnectivityTester |
( |
bool |
nodeConnectivity = true , |
|
|
bool |
directed = false |
|
) |
| |
|
inlineexplicit |
Initializes a new connectivity tester using ogdf::MaxFlowGoldbergTarjan.
- Parameters
-
nodeConnectivity | Whether to compute node connectivity instead of edge connectivity |
directed | Whether to consider edges to be directed |
Definition at line 117 of file ConnectivityTester.h.
◆ ConnectivityTester() [2/2]
ogdf::ConnectivityTester::ConnectivityTester |
( |
MaxFlowModule< int > * |
flowAlgo, |
|
|
bool |
nodeConnectivity = true , |
|
|
bool |
directed = false |
|
) |
| |
|
inline |
Initializes a new onnectivity tester using a custom ogdf::MaxFlowModule.
- Parameters
-
flowAlgo | The maximum flow algorithm to be used. |
nodeConnectivity | Whether to compute node connectivity instead of edge connectivity |
directed | Whether to consider edges to be directed |
Definition at line 129 of file ConnectivityTester.h.
◆ ~ConnectivityTester()
ogdf::ConnectivityTester::~ConnectivityTester |
( |
| ) |
|
|
inline |
◆ computeConnectivity() [1/4]
int ogdf::ConnectivityTester::computeConnectivity |
( |
const Graph & |
graph, |
|
|
node |
v, |
|
|
node |
u |
|
) |
| |
|
inline |
◆ computeConnectivity() [2/4]
Computes the connectivity of all nodes of the provided graph.
- Parameters
-
graph | The graph to be investigated |
result | The connectivity of two nodes each. For directed graphs, the first index denotes the source node. The connectivity of a node with itself is returned as 0. |
- Returns
- The minimal connectivity of any two nodes in the graph.
Definition at line 178 of file ConnectivityTester.h.
◆ computeConnectivity() [3/4]
int ogdf::ConnectivityTester::computeConnectivity |
( |
node |
v, |
|
|
node |
u |
|
) |
| |
|
private |
Computes the connectivity of two nodes of the transformed graph.
- Parameters
-
v | The source node |
u | The target node |
◆ computeConnectivity() [4/4]
int ogdf::ConnectivityTester::computeConnectivity |
( |
NodeArray< NodeArray< int >> & |
result | ) |
|
|
private |
Computes the connectivity of all nodes of the transformed graph.
- Parameters
-
result | The connectivity of two nodes each. For directed graphs, the first index denotes the source node. The connectivity of a node with itself is returned as 0. |
- Returns
- The minimal connectivity of any two nodes in the graph.
◆ copyOf()
node ogdf::ConnectivityTester::copyOf |
( |
node |
v, |
|
|
bool |
isSource = false |
|
) |
| const |
|
private |
Retuns the node of the transformed graph corresponding to node v
.
- Parameters
-
v | the original node |
isSource | Whether to return the corresponding source node. If node connectivity is to be computed, for each original node, two copies exist. |
◆ duplicateEdges()
void ogdf::ConnectivityTester::duplicateEdges |
( |
Graph & |
graph | ) |
|
|
private |
Makes the graph bi-directed.
- Parameters
-
graph | The graph to be altered. |
◆ prepareGraph()
void ogdf::ConnectivityTester::prepareGraph |
( |
const Graph & |
graph | ) |
|
|
private |
Prepares the graph.
Might create a copy of the actual graph to apply transformations. This is necessary to compute node connectivity and for undirected graphs.
- Parameters
-
◆ restrictNodes()
void ogdf::ConnectivityTester::restrictNodes |
( |
Graph & |
graph | ) |
|
|
private |
Restricts the flow through each node to 1.
Must be called after duplicateEdges().
- Parameters
-
graph | The graph to be altered. |
◆ m_directed
bool ogdf::ConnectivityTester::m_directed |
|
private |
◆ m_flowAlgo
◆ m_graph
const Graph* ogdf::ConnectivityTester::m_graph |
|
private |
◆ m_graphCopied
bool ogdf::ConnectivityTester::m_graphCopied |
|
private |
◆ m_nodeConnectivity
bool ogdf::ConnectivityTester::m_nodeConnectivity |
|
private |
◆ m_source
◆ m_usingDefaultMaxFlow
bool ogdf::ConnectivityTester::m_usingDefaultMaxFlow |
|
private |
The documentation for this class was generated from the following file: