MinSTCutDijkstra.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/List.h>
#include <ogdf/basic/basic.h>
#include <ogdf/graphalg/Dijkstra.h>
#include <ogdf/graphalg/MinSTCutModule.h>
 
namespace ogdf {
 
template<typename TCost>
class MinSTCutDijkstra : public MinSTCutModule<TCost> {
public:
    MinSTCutDijkstra() { }
 
    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);
    }
 
    using MinSTCutModule<TCost>::m_gc;
};
 
template<typename TCost>
bool MinSTCutDijkstra<TCost>::call(const Graph& graph, const EdgeArray<TCost>& weight, node s,
        node t, List<edge>& edgeList, edge e_st) {
    delete m_gc;
    m_gc = new GraphCopy(graph);
    CombinatorialEmbedding CE;
 
    MinSTCutModule<TCost>::preprocessingDual(graph, *m_gc, CE, s, t, e_st);
 
    MinSTCutModule<TCost>::m_direction.init(graph);
 
    DualGraph dual(CE);
    if (e_st != nullptr) {
        e_st = m_gc->copy(e_st);
    } else {
        e_st = m_gc->searchEdge(m_gc->copy(s), m_gc->copy(t));
    }
    edgeList.clear();
    node source = dual.dualNode(CE.rightFace(e_st->adjSource()));
    node target = dual.dualNode(CE.leftFace(e_st->adjSource()));
 
 
    EdgeArray<TCost> weightDual(dual, 0);
    TCost sumOfWeights(0);
    for (edge e : m_gc->edges) {
        if (e != e_st) {
            weightDual[dual.dualEdge(e)] = weight[m_gc->original(e)];
            sumOfWeights += weightDual[dual.dualEdge(e)];
            OGDF_ASSERT(sumOfWeights > sumOfWeights - weightDual[dual.dualEdge(e)]);
        }
    }
    weightDual[dual.dualEdge(e_st)] = sumOfWeights + 1;
    List<node> sourceNodeList;
    sourceNodeList.pushFront(source);
    NodeArray<edge> prevEdge(dual);
    NodeArray<TCost> distance(dual);
    Dijkstra<TCost> D;
    D.call(dual, weightDual, sourceNodeList, prevEdge, distance);
 
    node v = target;
    do {
        edge eDual = prevEdge[v];
        OGDF_ASSERT(eDual != nullptr);
        edge eG = dual.primalEdge(eDual);
        OGDF_ASSERT(eG != nullptr);
        edgeList.pushBack(m_gc->original(eG));
        MinSTCutModule<TCost>::m_direction[m_gc->original(eG)] = eDual->target() != v;
        v = (v == eDual->target() ? eDual->source() : eDual->target());
    } while (v != source);
    return true;
}
}