Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
ConnectivityTester.h
Go to the documentation of this file.
1
32#pragma once
33
34#include <ogdf/basic/Graph.h>
35#include <ogdf/basic/basic.h>
38
39namespace ogdf {
40
51private:
58 const Graph* m_graph;
59
67 void prepareGraph(const Graph& graph);
68
76
86
92 void duplicateEdges(Graph& graph);
93
100 void restrictNodes(Graph& graph);
101
109 node copyOf(node v, bool isSource = false) const;
110
111public:
118 explicit ConnectivityTester(bool nodeConnectivity = true, bool directed = false)
119 : ConnectivityTester(new MaxFlowGoldbergTarjan<int>(), nodeConnectivity, directed) {
120 m_usingDefaultMaxFlow = true;
121 }
122
130 ConnectivityTester(MaxFlowModule<int>* flowAlgo, bool nodeConnectivity = true,
131 bool directed = false)
132 : m_flowAlgo(flowAlgo)
133 , m_source(nullptr)
134 , m_usingDefaultMaxFlow(false)
135 , m_graphCopied(false)
136 , m_nodeConnectivity(nodeConnectivity)
137 , m_directed(directed)
138 , m_graph(nullptr) { }
139
144 if (m_usingDefaultMaxFlow) {
145 delete m_flowAlgo;
146 }
147
148 if (m_graphCopied) {
149 delete m_graph;
150 }
151
152 delete m_source;
153 }
154
164 int computeConnectivity(const Graph& graph, node v, node u) {
165 prepareGraph(graph);
166
167 return computeConnectivity(copyOf(v, true), copyOf(u));
168 }
169
179 int computeConnectivity(const Graph& graph, NodeArray<NodeArray<int>>& result) {
180 prepareGraph(graph);
181
182 return computeConnectivity(result);
183 }
184};
185
186}
Includes declaration of graph class.
Declaration and implementation of Goldberg-Tarjan max-flow algorithm with global relabeling and gap r...
Interface for Max Flow Algorithms.
Basic declarations, included by all source files.
Naive implementation for testing the connectivity of a graph.
int computeConnectivity(const Graph &graph, node v, node u)
Computes the connectivity of two nodes.
int computeConnectivity(NodeArray< NodeArray< int > > &result)
Computes the connectivity of all nodes of the transformed graph.
~ConnectivityTester()
Destroys the connectivity tester and frees allocated memory.
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.
void restrictNodes(Graph &graph)
Restricts the flow through each node to 1.
MaxFlowModule< int > * m_flowAlgo
void prepareGraph(const Graph &graph)
Prepares the graph.
void duplicateEdges(Graph &graph)
Makes the graph bi-directed.
node copyOf(node v, bool isSource=false) const
Retuns the node of the transformed graph corresponding to node v.
int computeConnectivity(const Graph &graph, NodeArray< NodeArray< int > > &result)
Computes the connectivity of all nodes of the provided graph.
NodeArray< node > * m_source
int computeConnectivity(node v, node u)
Computes the connectivity of two nodes of the transformed graph.
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:866
Computes a max flow via Preflow-Push (global relabeling and gap relabeling heuristic).
Class for the representation of nodes.
Definition Graph_d.h:241
RegisteredArray for nodes, edges and adjEntries of a graph.
Definition Graph_d.h:659
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF dynamic library (shared object / DLL),...
Definition config.h:117
The namespace for all OGDF objects.