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

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

Private Attributes
bool	m_directed
MaxFlowModule< int > *	m_flowAlgo
const Graph *	m_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

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

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

graph	The graph to be investigated
v	The source node
u	The 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

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

graph

The original graph

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.

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:

• include/ogdf/graphalg/ConnectivityTester.h