MaxFlowSTPlanarDigraph.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/CombinatorialEmbedding.h>
#include <ogdf/basic/DualGraph.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/extended_graph_alg.h>
#include <ogdf/basic/simple_graph_alg.h>
#include <ogdf/graphalg/Dijkstra.h>
#include <ogdf/graphalg/MaxFlowModule.h>
 
#include <limits>
 
namespace ogdf {
 
 
template<typename TCap>
class MaxFlowSTPlanarDigraph : public MaxFlowModule<TCap> {
private:
    void createBackArcs(Graph& gr, EdgeArray<TCap>& new_costs) {
        // gr = dg.
        for (edge e = gr.lastEdge(); e != nullptr; e = e->pred()) {
            edge e_new_dg = gr.newEdge(e->target(), e->source());
            new_costs[e_new_dg] = 0;
        }
    }
 
public:
    TCap computeValue(const EdgeArray<TCap>& cap, const node& s, const node& t) override {
        // clear old flow
        (*this->m_flow).fill(0);
        // store capacity, source and sink
        this->m_cap = &cap;
        this->m_s = &s;
        this->m_t = &t;
        OGDF_ASSERT(this->isFeasibleInstance());
 
        OGDF_ASSERT(isSTPlanar(*this->m_G, s, t));
        GraphCopy copyG(*this->m_G);
        node copyS = copyG.copy(s);
        node copyT = copyG.copy(t);
        CombinatorialEmbedding ce(copyG);
        adjEntry adjAtTarget;
        adjEntry adjAtSource = ce.findCommonFace(copyS, copyT, adjAtTarget, false);
        face f_infty = ce.rightFace(adjAtSource);
        ce.setExternalFace(f_infty);
 
        // split the external face
        edge ts_edge = ce.splitFace(adjAtTarget, adjAtSource);
        DualGraph dg(ce);
 
        EdgeArray<TCap> costs(dg, 0);
        for (edge e : (*this->m_G).edges) {
            costs[dg.dualEdge(copyG.copy(e))] = cap[e];
        }
        createBackArcs(dg, costs);
        costs[dg.dualEdge(ts_edge)] = std::numeric_limits<TCap>::max();
 
        Dijkstra<TCap> dij;
        NodeArray<edge> preds(dg, nullptr);
        NodeArray<TCap> dists(dg, 0);
        dij.call(dg, costs, dg.dualNode(f_infty), preds, dists, true); // directed
 
        for (edge e : (*this->m_G).edges) {
            (*this->m_flow)[e] = dists[dg.dualNode(ce.leftFace(copyG.copy(e)->adjSource()))]
                    - dists[dg.dualNode(ce.rightFace(copyG.copy(e)->adjSource()))];
        }
 
        // compute flow value
        TCap flowValue = 0;
        for (adjEntry adj : s->adjEntries) {
            edge e = adj->theEdge();
            if (e->source() == s) {
                flowValue += (*this->m_flow)[e];
            } else {
                flowValue -= (*this->m_flow)[e];
            }
        }
        return flowValue;
    }
 
    void computeFlowAfterValue() override { /* nothing to do here */
    }
 
    void init(const Graph& graph, EdgeArray<TCap>* flow = nullptr) override {
        OGDF_ASSERT(isConnected(graph));
        OGDF_ASSERT(isPlanar(graph));
        MaxFlowModule<TCap>::init(graph, flow);
    }
 
    // use methods from super class
    using MaxFlowModule<TCap>::useEpsilonTest;
    using MaxFlowModule<TCap>::computeFlow;
    using MaxFlowModule<TCap>::computeFlowAfterValue;
    using MaxFlowModule<TCap>::MaxFlowModule;
};
 
}