/Users/jst/src/grafalgo/cpp/graphAlgorithms/maxFlo/augPath.cpp

Go to the documentation of this file.

#include "Adt.h"
#include "augPath.h"

using namespace grafalgo;

augPath::augPath(Flograph& fg1, int& flow_value) : fg(&fg1) {
        pEdge = new edge[fg->n()+1];
}

augPath::~augPath() { delete [] pEdge; }

int augPath::augment() {
// Saturate the augmenting path p.
        vertex u, v; edge e; flow f;

        // determine residual capacity of path
        f = Util::BIGINT32;
        u = fg->snk(); e = pEdge[u];
        while (u != fg->src()) {
                v = fg->mate(u,e);
                f = min(f,fg->res(v,e));
                u = v; e = pEdge[u];
        }
        // add flow to saturate path
        u = fg->snk(); e = pEdge[u];
        while (u != fg->src()) {
                v = fg->mate(u,e);
                fg->addFlow(v,e,f);
                u = v; e = pEdge[u];
        }
        return f;
}