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

Go to the documentation of this file.

#include "ppHiLab.h"

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

ppHiLab::ppHiLab(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 ppHiLab::doit(bool batch) {
        // ubVec[d] is an unbalanced vertex with a distance label of d
        // or 0 if there is no unbalanced vertex with a distance label of d
        // unbal partitions the vertices into circular lists, where all
        // vertices on the same list are unbalanced and have the same
        // distance label; balanced vertices each form singleton lists
        ubVec = new int[2*fg->n()];
        unbal = new ClistSet(fg->n());

        // initialization
        for (int i = 0; i < 2*fg->n(); i++) ubVec[i] = 0;
        top = 0;
        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()) addUnbal(v);
        }

        vertex u;
        if (!batch) { // incremental relabeling
                while (top > 0) {
                        u = removeUnbal();
                        if (!balance(u)) {
                                d[u] = 1 + minlabel(u);
                                nextedge[u] = fg->firstAt(u);
                                addUnbal(u);
                                relabCount++;
                        }
                }
        } else { // batch relabeling
                while (top > 0) {
                        while (top > 0) {
                                u = removeUnbal();
                                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) addUnbal(u);
                        }
                }
        }
        delete unbal; delete [] ubVec;
}

void ppHiLab::newUnbal(vertex u) {
        if (unbal->suc(u) == u && ubVec[d[u]] != u) addUnbal(u);
}

void ppHiLab::addUnbal(vertex u) {
        if (ubVec[d[u]] == 0) ubVec[d[u]] = u;
        else unbal->join(ubVec[d[u]],u);
        top = max(top,d[u]);
}

vertex ppHiLab::removeUnbal() {
        vertex u = ubVec[top]; 
        vertex v = unbal->suc(u);
        unbal->remove(u);
        if (v != u) {
                ubVec[top] = v;
        } else {
                ubVec[top] = 0;
                while (top > 0 && ubVec[top] == 0) top--;
        }
        return u;
}