Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::ConnectivityTester Class Reference

Naive implementation for testing the connectivity of a graph. More...

#include <ogdf/graphalg/ConnectivityTester.h>

Public Member Functions

 ConnectivityTester (bool nodeConnectivity=true, bool directed=false)
 Initializes a new connectivity tester using ogdf::MaxFlowGoldbergTarjan. More...
 
 ConnectivityTester (MaxFlowModule< int > *flowAlgo, bool nodeConnectivity=true, bool directed=false)
 Initializes a new onnectivity tester using a custom ogdf::MaxFlowModule. More...
 
 ~ConnectivityTester ()
 Destroys the connectivity tester and frees allocated memory. More...
 
int computeConnectivity (const Graph &graph, node v, node u)
 Computes the connectivity of two nodes. More...
 
int computeConnectivity (const Graph &graph, NodeArray< NodeArray< int >> &result)
 Computes the connectivity of all nodes of the provided graph. More...
 

Private Member Functions

int computeConnectivity (node v, node u)
 Computes the connectivity of two nodes of the transformed graph. More...
 
int computeConnectivity (NodeArray< NodeArray< int >> &result)
 Computes the connectivity of all nodes of the transformed graph. More...
 
node copyOf (node v, bool isSource=false) const
 Retuns the node of the transformed graph corresponding to node v. More...
 
void duplicateEdges (Graph &graph)
 Makes the graph bi-directed. More...
 
void prepareGraph (const Graph &graph)
 Prepares the graph. More...
 
void restrictNodes (Graph &graph)
 Restricts the flow through each node to 1. More...
 

Private Attributes

bool m_directed
 
MaxFlowModule< int > * m_flowAlgo
 
const Graphm_graph
 
bool m_graphCopied
 
bool m_nodeConnectivity
 
NodeArray< node > * m_source
 
bool m_usingDefaultMaxFlow
 

Detailed Description

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.

Constructor & Destructor Documentation

◆ ConnectivityTester() [1/2]

ogdf::ConnectivityTester::ConnectivityTester ( bool  nodeConnectivity = true,
bool  directed = false 
)
inlineexplicit

Initializes a new connectivity tester using ogdf::MaxFlowGoldbergTarjan.

Parameters
nodeConnectivityWhether to compute node connectivity instead of edge connectivity
directedWhether 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
flowAlgoThe maximum flow algorithm to be used.
nodeConnectivityWhether to compute node connectivity instead of edge connectivity
directedWhether to consider edges to be directed

Definition at line 129 of file ConnectivityTester.h.

◆ ~ConnectivityTester()

ogdf::ConnectivityTester::~ConnectivityTester ( )
inline

Destroys the connectivity tester and frees allocated memory.

Definition at line 142 of file ConnectivityTester.h.

Member Function Documentation

◆ computeConnectivity() [1/4]

int ogdf::ConnectivityTester::computeConnectivity ( const Graph graph,
node  v,
node  u 
)
inline

Computes the connectivity of two nodes.

To reduce duplicate graph transformations, computeConnectivity(const Graph &graph, NodeArray<NodeArray<int>> &result) should be used to compute the connectivity of all nodes.

Parameters
graphThe graph to be investigated
vThe source node
uThe target node

Definition at line 163 of file ConnectivityTester.h.

◆ computeConnectivity() [2/4]

int ogdf::ConnectivityTester::computeConnectivity ( const Graph graph,
NodeArray< NodeArray< int >> &  result 
)
inline

Computes the connectivity of all nodes of the provided graph.

Parameters
graphThe graph to be investigated
resultThe 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
vThe source node
uThe 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
resultThe 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
vthe original node
isSourceWhether 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
graphThe 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
graphThe original graph

◆ restrictNodes()

void ogdf::ConnectivityTester::restrictNodes ( Graph graph)
private

Restricts the flow through each node to 1.

Must be called after duplicateEdges().

Parameters
graphThe graph to be altered.

Member Data Documentation

◆ m_directed

bool ogdf::ConnectivityTester::m_directed
private

Definition at line 56 of file ConnectivityTester.h.

◆ m_flowAlgo

MaxFlowModule<int>* ogdf::ConnectivityTester::m_flowAlgo
private

Definition at line 51 of file ConnectivityTester.h.

◆ m_graph

const Graph* ogdf::ConnectivityTester::m_graph
private

Definition at line 57 of file ConnectivityTester.h.

◆ m_graphCopied

bool ogdf::ConnectivityTester::m_graphCopied
private

Definition at line 54 of file ConnectivityTester.h.

◆ m_nodeConnectivity

bool ogdf::ConnectivityTester::m_nodeConnectivity
private

Definition at line 55 of file ConnectivityTester.h.

◆ m_source

NodeArray<node>* ogdf::ConnectivityTester::m_source
private

Definition at line 52 of file ConnectivityTester.h.

◆ m_usingDefaultMaxFlow

bool ogdf::ConnectivityTester::m_usingDefaultMaxFlow
private

Definition at line 53 of file ConnectivityTester.h.


The documentation for this class was generated from the following file: