ConnectivityTester.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/graphalg/MaxFlowGoldbergTarjan.h>
#include <ogdf/graphalg/MaxFlowModule.h>
 
namespace ogdf {
 
class OGDF_EXPORT ConnectivityTester {
private:
    MaxFlowModule<int>* m_flowAlgo;
    NodeArray<node>* m_source;
    bool m_usingDefaultMaxFlow;
    bool m_graphCopied;
    bool m_nodeConnectivity;
    bool m_directed;
    const Graph* m_graph;
 
    void prepareGraph(const Graph& graph);
 
    int computeConnectivity(node v, node u);
 
    int computeConnectivity(NodeArray<NodeArray<int>>& result);
 
    void duplicateEdges(Graph& graph);
 
    void restrictNodes(Graph& graph);
 
    node copyOf(node v, bool isSource = false) const;
 
public:
    explicit ConnectivityTester(bool nodeConnectivity = true, bool directed = false)
        : ConnectivityTester(new MaxFlowGoldbergTarjan<int>(), nodeConnectivity, directed) {
        m_usingDefaultMaxFlow = true;
    }
 
    ConnectivityTester(MaxFlowModule<int>* flowAlgo, bool nodeConnectivity = true,
            bool directed = false)
        : m_flowAlgo(flowAlgo)
        , m_source(nullptr)
        , m_usingDefaultMaxFlow(false)
        , m_graphCopied(false)
        , m_nodeConnectivity(nodeConnectivity)
        , m_directed(directed)
        , m_graph(nullptr) { }
 
    ~ConnectivityTester() {
        if (m_usingDefaultMaxFlow) {
            delete m_flowAlgo;
        }
 
        if (m_graphCopied) {
            delete m_graph;
        }
 
        delete m_source;
    }
 
    int computeConnectivity(const Graph& graph, node v, node u) {
        prepareGraph(graph);
 
        return computeConnectivity(copyOf(v, true), copyOf(u));
    }
 
    int computeConnectivity(const Graph& graph, NodeArray<NodeArray<int>>& result) {
        prepareGraph(graph);
 
        return computeConnectivity(result);
    }
};
 
}