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

Go to the documentation of this file.

#include "ppFifo.h"

ppFifo::ppFifo(Flograph& fg1, int& floVal, bool batch) : prePush(fg1,floVal) {
        doit(batch); floVal = flowValue();
}

ppFifo::ppFifo(Flograph& fg1, int& floVal, bool batch, string& stats)
                : prePush(fg1,floVal) {
        doit(batch); floVal = flowValue();
        stringstream ss;
        ss << satCount << " " << nonSatCount << " " << newDistCount
           << " " << relabCount;
        stats = ss.str();
}

void ppFifo::doit(bool batch) {
        unbal = new List(fg->n());

        // initialization
        vertex s = fg->src();
        for (edge e = fg->firstOut(s); e != 0; e = fg->nextOut(s,e)) {
                vertex v = fg->head(e);
                if (v != fg->snk()) unbal->addLast(v); 
        }

        vertex u;
        if (!batch) { // incremental relabeling
                while (!unbal->empty()) {
                        u = unbal->first(); unbal->removeFirst();
                        if (!balance(u)) {
                                d[u] = 1 + minlabel(u);
                                nextedge[u] = fg->firstAt(u);
                                unbal->addLast(u);
                                relabCount++;
                        }
                }
        } else { // batch relabeling
                while (!unbal->empty()) {
                        while (!unbal->empty()) {
                                u = unbal->first(); unbal->removeFirst();
                                balance(u);
                        }
                        initdist();
                        for (u = 1; u <= fg->n(); u++) {
                                if (u == fg->src() || u == fg->snk()) continue;
                                nextedge[u] = fg->firstAt(u);
                                if (excess[u] > 0) unbal->addLast(u);
                        }
                }
        }
        delete unbal;
}

void ppFifo::newUnbal(vertex u) {
        if (!unbal->member(u)) unbal->addLast(u);
}