MaxFlowEdmondsKarp.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/basic.h>
#include <ogdf/graphalg/MaxFlowModule.h>
 
#include <limits>
 
namespace ogdf {
 
 
template<typename TCap>
class MaxFlowEdmondsKarp : public MaxFlowModule<TCap> {
private:
    bool augmentShortestSourceSinkPath() {
        NodeArray<adjEntry> pred(*this->m_G, nullptr); // edges from the predecessor
        List<node> queue;
        queue.pushBack(*this->m_s);
 
        while (!queue.empty()) {
            node v = queue.popFrontRet();
            if (v == *this->m_t) {
                // find minimum residual capacity value on s-t-path
                TCap augmentVal = std::numeric_limits<TCap>::max();
                for (node w = v; pred[w]; w = pred[w]->theNode()) {
                    const adjEntry adj = pred[w];
                    const edge e = adj->theEdge();
                    if (e->target() == w) { // real edge e = vw
                        if ((*this->m_cap)[e] - (*this->m_flow)[e] < augmentVal) {
                            augmentVal = (*this->m_cap)[e] - (*this->m_flow)[e];
                        }
                    } else { // virtual edge e = wv
                        if ((*this->m_flow)[e] < augmentVal) {
                            augmentVal = (*this->m_flow)[e];
                        }
                    }
                }
                // augment s-t-path by this value
                for (node w = v; pred[w]; w = pred[w]->theNode()) {
                    const adjEntry adj = pred[w];
                    const edge e = adj->theEdge();
                    if (e->target() == w) { // real edge e = vw
                        (*this->m_flow)[e] += augmentVal;
                    } else { // virtual edge e = wv
                        (*this->m_flow)[e] -= augmentVal;
                    }
                }
                return true;
            }
            for (adjEntry adj : v->adjEntries) {
                const node w = adj->twinNode();
                if (w != (*this->m_s) && !pred[w]) // if not already visited
                {
                    const edge e = adj->theEdge();
                    if (e->source() == v) { // real edge e = vw
                        if ((*this->m_et).greater((*this->m_cap)[e], (*this->m_flow)[e])) {
                            // reachable in residual graph
                            queue.pushBack(w);
                            pred[w] = adj;
                        }
                    } else { // virtual edge (adj) wv
                        if ((*this->m_et).greater((*this->m_flow)[e], (TCap)0)) {
                            // reachable in residual graph
                            queue.pushBack(w);
                            pred[w] = adj;
                        }
                    }
                }
            }
        }
 
        return false;
    }
 
public:
 
    TCap computeValue(const EdgeArray<TCap>& cap, const node& s, const node& t) {
        // clear old flow
        this->m_flow->fill((TCap)0);
        // store capacity, source and sink
        this->m_cap = &cap;
        this->m_s = &s;
        this->m_t = &t;
        OGDF_ASSERT(this->isFeasibleInstance());
 
        if (*this->m_s == *this->m_t) {
            return (TCap)0;
        }
 
        while (augmentShortestSourceSinkPath()) {
            ;
        }
        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() { /* nothing to do here */
    }
 
    // use methods from super class
    using MaxFlowModule<TCap>::useEpsilonTest;
    using MaxFlowModule<TCap>::computeFlow;
    using MaxFlowModule<TCap>::computeFlowAfterValue;
    using MaxFlowModule<TCap>::MaxFlowModule;
    using MaxFlowModule<TCap>::init;
};
 
}