MinSTCutMaxFlow.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/ArrayBuffer.h>
#include <ogdf/basic/EpsilonTest.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/basic.h>
#include <ogdf/graphalg/MaxFlowGoldbergTarjan.h>
#include <ogdf/graphalg/MinSTCutModule.h>
 
#include <cstddef>
#include <functional>
#include <memory>
 
namespace ogdf {
template<typename T>
class MaxFlowModule;
 
template<typename TCost>
class MinSTCutMaxFlow : public MinSTCutModule<TCost> {
    using MinSTCutModule<TCost>::m_gc;
 
public:
    explicit MinSTCutMaxFlow(bool treatAsUndirected = true,
            MaxFlowModule<TCost>* mfModule = new MaxFlowGoldbergTarjan<TCost>(),
            bool primaryCut = true, bool calculateOtherCut = true,
            EpsilonTest* epsilonTest = new EpsilonTest())
        : m_mfModule(mfModule)
        , m_treatAsUndirected(treatAsUndirected)
        , m_primaryCut(primaryCut)
        , m_calculateOtherCut(calculateOtherCut)
        , m_et(epsilonTest) { }
 
    virtual bool call(const Graph& graph, const EdgeArray<TCost>& weight, node s, node t,
            List<edge>& edgeList, edge e_st = nullptr) override;
 
    virtual bool call(const Graph& graph, node s, node t, List<edge>& edgeList,
            edge e_st = nullptr) override {
        EdgeArray<TCost> weight(graph, 1);
        return call(graph, weight, s, t, edgeList, e_st);
    }
 
    void call(const Graph& graph, const EdgeArray<TCost>& weights, const EdgeArray<TCost>& flow,
            const node source, const node target);
 
    enum class cutType {
        FRONT_CUT, 
        BACK_CUT, 
        NO_CUT 
    };
 
    void setEpsilonTest(EpsilonTest* et) { m_et.reset(et); }
 
    bool frontCutIsComplementOfBackCut() const {
        OGDF_ASSERT(m_calculateOtherCut);
        return m_backCutCount + m_frontCutCount == m_totalCount;
    }
 
    bool isFrontCutEdge(const edge e) const {
        OGDF_ASSERT(m_calculateOtherCut || m_primaryCut);
        return m_nodeSet[e->source()] == cutType::FRONT_CUT
                && m_nodeSet[e->target()] != cutType::FRONT_CUT;
    }
 
    bool isBackCutEdge(const edge e) const {
        OGDF_ASSERT(m_calculateOtherCut || !m_primaryCut);
        return m_nodeSet[e->target()] == cutType::BACK_CUT
                && m_nodeSet[e->source()] != cutType::BACK_CUT;
    }
 
    bool isInFrontCut(const node v) const {
        OGDF_ASSERT(m_calculateOtherCut || m_primaryCut);
        return m_nodeSet[v] == cutType::FRONT_CUT;
    }
 
    bool isInBackCut(const node v) const {
        OGDF_ASSERT(m_calculateOtherCut || !m_primaryCut);
        return m_nodeSet[v] == cutType::BACK_CUT;
    }
 
    bool isOfType(const node v, cutType type) const { return m_nodeSet[v] == type; }
 
private:
    std::unique_ptr<MaxFlowModule<TCost>> m_mfModule;
    bool m_treatAsUndirected = false;
    bool m_primaryCut = true;
    bool m_calculateOtherCut = true;
 
 
    std::unique_ptr<EpsilonTest> m_et; 
    NodeArray<cutType> m_nodeSet; 
    EdgeArray<TCost> m_flow;
    EdgeArray<TCost> m_weight;
    int m_frontCutCount; 
    int m_backCutCount; 
    int m_totalCount; 
 
    void markCut(node startNode, bool frontCut, std::function<node(node)> origNode) {
        List<node> queue;
        queue.pushBack(startNode);
        m_nodeSet[origNode(startNode)] = (frontCut ? cutType::FRONT_CUT : cutType::BACK_CUT);
        frontCut ? m_frontCutCount++ : m_backCutCount++;
 
        while (!queue.empty()) {
            const node v = queue.popFrontRet();
            for (adjEntry adj : v->adjEntries) {
                const node w = adj->twinNode();
                const edge e = adj->theEdge();
                if (m_nodeSet[origNode(w)] == cutType::NO_CUT
                        && (((frontCut ? e->source() : e->target()) == v
                                    && m_et->less(m_flow[e], m_weight[e]))
                                || ((frontCut ? e->target() : e->source()) == v
                                        && m_et->greater(m_flow[e], TCost(0))))) {
                    queue.pushBack(w);
                    m_nodeSet[origNode(w)] = (frontCut ? cutType::FRONT_CUT : cutType::BACK_CUT);
                    frontCut ? m_frontCutCount++ : m_backCutCount++;
                }
            }
        }
    }
 
    void computeCut(const Graph& graph, std::function<edge(edge)> origEdge,
            std::function<node(node)> origNode, const node source, const node target,
            List<edge>& edgeList) {
        m_frontCutCount = 0;
        m_backCutCount = 0;
        m_totalCount = graph.numberOfNodes();
 
 
        List<node> queue;
        m_nodeSet.init(graph, cutType::NO_CUT);
 
        if (m_primaryCut || m_calculateOtherCut) {
            // front cut
            markCut(source, true, origNode);
        }
 
        if (!m_primaryCut || m_calculateOtherCut) {
            // back cut
            markCut(target, false, origNode);
        }
 
        ArrayBuffer<edge, size_t> stack;
        EdgeArray<bool> visited(graph, false);
        node startNode = (m_primaryCut ? source : target);
        adjEntry startAdj = startNode->firstAdj();
        if (startAdj == nullptr) {
            return;
        }
        if (startAdj->theEdge()->adjTarget() != startAdj) {
            stack.push(startAdj->theEdge());
        }
        for (adjEntry adj = (m_primaryCut ? startAdj->cyclicSucc() : startAdj->cyclicPred());
                adj != startAdj; adj = (m_primaryCut ? adj->cyclicSucc() : adj->cyclicPred())) {
            if (adj->theEdge()->adjTarget() != adj) {
                stack.push(adj->theEdge());
            }
        }
        while (!stack.empty()) {
            edge e = stack.popRet();
            if (visited[origEdge(e)]) {
                continue;
            }
            visited[origEdge(e)] = true;
            if (m_nodeSet[origNode(e->source())] == cutType::FRONT_CUT
                    && m_nodeSet[origNode(e->target())] != cutType::FRONT_CUT) {
                edgeList.pushBack(origEdge(e));
 
                if (m_gc->numberOfEdges() != 0) {
                    MinSTCutModule<TCost>::m_direction[origEdge(e)] = m_gc->copy(origEdge(e)) == e;
                }
            } else {
                startAdj = e->adjTarget();
                for (adjEntry adj = (m_primaryCut ? startAdj->cyclicSucc() : startAdj->cyclicPred());
                        adj != startAdj;
                        adj = (m_primaryCut ? adj->cyclicSucc() : adj->cyclicPred())) {
                    if (adj->theEdge()->adjTarget() != adj) {
                        stack.push(adj->theEdge());
                    }
                }
            }
        }
    }
};
 
template<typename TCost>
bool MinSTCutMaxFlow<TCost>::call(const Graph& graph, const EdgeArray<TCost>& weight, node source,
        node target, List<edge>& edgeList, edge e_st) {
    MinSTCutModule<TCost>::m_direction.init(graph, -1);
    delete m_gc;
    m_gc = new GraphCopy(graph);
 
    if (e_st != nullptr) {
        m_gc->delEdge(m_gc->copy(e_st));
    }
    node s = m_gc->copy(source);
    node t = m_gc->copy(target);
    List<edge> edges;
    m_gc->allEdges(edges);
    EdgeArray<edge> originalEdge(*m_gc, nullptr);
    for (edge e : edges) {
        if (m_treatAsUndirected) {
            // a reversed edge is made and placed directly next to e
            edge revEdge = m_gc->newEdge(e->target(), e->source());
            m_gc->move(revEdge, e->adjTarget(), ogdf::Direction::before, e->adjSource(),
                    ogdf::Direction::after);
            originalEdge[revEdge] = m_gc->original(e);
        }
        originalEdge[e] = m_gc->original(e);
    }
 
    m_flow.init(*m_gc, -1);
    m_weight.init(*m_gc, 1);
    for (edge e : m_gc->edges) {
        edge origEdge = originalEdge[e];
        m_weight[e] = weight[origEdge];
        OGDF_ASSERT(m_weight[e] >= 0);
    }
 
    m_mfModule->init(*m_gc);
    m_mfModule->computeFlow(m_weight, s, t, m_flow);
 
    computeCut(
            graph, [&](edge e) -> edge { return originalEdge[e]; },
            [&](node v) -> node { return m_gc->original(v); }, s, t, edgeList);
 
    return true;
}
 
template<typename TCost>
void MinSTCutMaxFlow<TCost>::call(const Graph& graph, const EdgeArray<TCost>& weights,
        const EdgeArray<TCost>& flow, const node source, const node target) {
    delete m_gc;
    m_gc = new GraphCopy();
    m_flow = flow;
    m_weight = weights;
    List<edge> edgeList;
    computeCut(
            graph, [&](edge e) -> edge { return e; }, [&](node v) -> node { return v; }, source,
            target, edgeList);
}
}