MaxFlowModule.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/EpsilonTest.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphList.h>
 
namespace ogdf {
 
template<typename T>
class MaxFlowModule {
protected:
    EpsilonTest* m_et; 
    EdgeArray<T>* m_flow; 
    const Graph* m_G; 
    const EdgeArray<T>* m_cap; 
    const node* m_s; 
    const node* m_t; 
 
private:
    bool usingExternFlow = false; 
    bool doingAReInit = false; 
 
    void destroy() {
        if (!usingExternFlow) {
            delete m_flow;
        }
        delete m_et;
    }
 
public:
    MaxFlowModule()
        : m_et(nullptr), m_flow(nullptr), m_G(nullptr), m_cap(nullptr), m_s(nullptr), m_t(nullptr) { }
 
 
    explicit MaxFlowModule(const Graph& graph, EdgeArray<T>* flow = nullptr)
        : m_s(nullptr), m_t(nullptr) {
        init(graph, flow);
    }
 
    virtual ~MaxFlowModule() { destroy(); }
 
 
    virtual void init(const Graph& graph, EdgeArray<T>* flow = nullptr) {
        // if re-init after an init with internal flow:
        if (doingAReInit) {
            destroy();
        }
        m_G = &graph;
        if (flow) {
            m_flow = flow;
            usingExternFlow = true;
        } else {
            usingExternFlow = false; // in case of a re-init
            m_flow = new EdgeArray<T>(*m_G, 0);
        }
        m_et = new EpsilonTest();
        doingAReInit = true;
    }
 
 
    void useEpsilonTest(const double& eps) {
        delete m_et;
        m_et = new EpsilonTest(eps);
    }
 
    virtual T computeValue(const EdgeArray<T>& cap, const node& s, const node& t) = 0;
 
    virtual void computeFlowAfterValue() = 0;
 
 
    void computeFlowAfterValue(EdgeArray<T>& flow) {
        computeFlowAfterValue();
        flow = *m_flow;
    }
 
    bool isFeasibleInstance() const {
        for (edge e : m_G->edges) {
            if ((*m_cap)[e] < 0) {
                return false;
            }
        }
        return true;
    }
 
 
    T computeFlow(EdgeArray<T>& cap, node& s, node& t, EdgeArray<T>& flow) {
        T val = computeValue(cap, s, t);
        computeFlowAfterValue(flow);
        return val;
    }
};
 
}