MinSTCutModule.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/CombinatorialEmbedding.h>
#include <ogdf/basic/extended_graph_alg.h>
 
namespace ogdf {
 
template<typename TCost>
class MinSTCutModule {
public:
    MinSTCutModule() { }
 
    virtual bool call(const Graph& graph, const EdgeArray<TCost>& weight, node s, node t,
            List<edge>& edgeList, edge e_st = nullptr) = 0;
 
    virtual bool call(const Graph& graph, node s, node t, List<edge>& edgeList,
            edge e_st = nullptr) = 0;
 
    virtual ~MinSTCutModule() { delete m_gc; }
 
    virtual bool direction(edge e) {
        OGDF_ASSERT(m_gc->numberOfEdges() != 0);
        OGDF_ASSERT(m_direction[e] != -1);
        return m_direction[e];
    }
 
protected:
    EdgeArray<int> m_direction;
    GraphCopy* m_gc = nullptr;
 
    bool preprocessingDual(const Graph& graph, GraphCopy& gc, CombinatorialEmbedding& CE,
            node source, node target, edge e_st) {
        node gcS(gc.copy(source));
        node gcT(gc.copy(target));
        adjEntry adjT, adjS;
        bool isSTplanarEmbeded(false);
        if (gc.representsCombEmbedding()) {
            CE.init(gc);
            adjS = CE.findCommonFace(gcS, gcT, adjT, false);
            isSTplanarEmbeded = (adjS != nullptr);
        }
        if (isSTplanarEmbeded) {
            if (e_st == nullptr) {
                CE.splitFace(adjS, adjT);
            }
        } else {
            if (e_st == nullptr) {
                gc.newEdge(gcS, gcT);
            }
            if (!planarSTEmbed(gc, gcS, gcT)) {
                return false;
            }
            CE.init(gc);
        }
        return true;
    }
};
}