/Users/jst/src/grafalgo/cpp/dataStructures/graphs/Flograph.cpp

Go to the documentation of this file.

#include "Flograph.h"

#define flo(x) floInfo[x].flo
#define cpy(x) floInfo[x].cpy

namespace grafalgo {

Flograph::Flograph(int numv, int maxe, int s1, int t1) 
        : Digraph(numv, maxe), s(s1), t(t1) {
        assert(n() >= 2 && maxEdge >= 0 && 1 <= s && s <= n() 
                && 1 <= t && t <= n() && s != t);
        makeSpace(numv,maxe);
}

Flograph::~Flograph() { freeSpace(); }

void Flograph::makeSpace(int numv, int maxe) {
        try {
                floInfo = new FloInfo[maxe+1];
        } catch (std::bad_alloc e) {
                stringstream ss;
                ss << "Flograph::makeSpace: insufficient space for "
                   << maxe << " edge weights";
                string s = ss.str();
                throw OutOfSpaceException(s);
        }
}

void Flograph::freeSpace() { delete [] floInfo; }

void Flograph::resize(int numv, int maxe) {
        freeSpace();
        Digraph::resize(numv,maxe);
        try { makeSpace(numv,maxe); } catch(OutOfSpaceException e) {
                string s; s = "Flograph::resize:" + e.toString(s);
                throw OutOfSpaceException(s);
        }
}

void Flograph::expand(int numv, int maxe) {
        if (numv <= n() && maxe <= maxEdge) return;
        Flograph old(this->n(),this->maxEdge); old.copyFrom(*this);
        resize(numv,maxe); this->copyFrom(old);
}

void Flograph::copyFrom(const Flograph& source) {
        if (&source == this) return;
        if (source.n() > n() || source.m() > maxEdge)
                resize(source.n(),source.m());
        else clear();
        for (edge e = source.first(); e != 0; e = source.next(e)) {
                edge ee = join(source.tail(e),source.head(e));
                setCapacity(ee,source.cap(source.tail(e),e));
                setFlow(ee,source.f(source.tail(e),e));
        }
        sortAdjLists();
}

bool Flograph::readAdjList(istream& in) {
        if (!Util::verify(in,'[')) return 0;
        bool isSrc = false; bool isSnk = false;
        if (Util::verify(in,'-')) {
                if (!Util::verify(in,'>',true)) return 0;
                isSnk = true;
        }
        vertex u;
        if (!Adt::readItem(in,u)) return 0;
        if (Util::verify(in,'-')) {
                if (!Util::verify(in,'>',true)) return 0;
                isSrc = true;
        }
        if (!Util::verify(in,':')) return 0;
        if (u > n()) expand(u,m());
        if (isSrc) setSrc(u);
        if (isSnk) setSnk(u);
        while (in.good() && !Util::verify(in,']')) {
                vertex v;
                if (!Adt::readItem(in,v)) return 0;
                if (v > n()) expand(v,m());
                if (m() >= maxEdge) expand(n(),max(1,2*m()));
                int capacity, flow;
                if (!Util::verify(in,'(') || !Util::readInt(in,capacity) ||
                    !Util::verify(in,',') || !Util::readInt(in,flow) ||
                    !Util::verify(in,')'))
                        return 0;
                edge e = join(u,v);
                setCapacity(e,capacity); setFlow(e,flow);
        }
        return in.good();
}

edge Flograph::join(vertex u, vertex v) {
        assert(1 <= u && u <= n() && 1 <= v && v <= n() && m() < maxEdge);
        edge e = Digraph::join(u,v); setFlow(e,0);
        return e;
}

void Flograph::clearFlow() {
        for (edge e = first(); e != 0; e = next(e)) setFlow(e,0);
}

void Flograph::addFlow(vertex v, edge e, flow ff) {
        if (tail(e) == v) {
                if (ff + flo(e) > cpy(e) || ff + flo(e) < 0) {
                        Util::fatal("addflow: requested flow outside allowed "
                                    "range");
                }
                flo(e) += ff;
        } else {
                if (flo(e) - ff < 0 || flo(e) - ff > cpy(e)) {
                        Util::fatal("addflow: requested flow outside allowed "
                                    "range");
                }
                flo(e) -= ff;
        }
}

string& Flograph::edge2string(edge e, string& s) const {
        stringstream ss;
        vertex u = tail(e); vertex v = head(e);
        if (e == 0) {
               ss << "-"; 
        } else {
                ss << "(" << item2string(u,s);
                ss << "," << item2string(v,s)
                   << "," << cap(u,e) << "," <<  f(u,e) << ")";
        }
        s = ss.str();
        return s;
}

string& Flograph::adjList2string(vertex u, string& s) const {
        s = "";
        if (firstOut(u) == 0) return s;
        stringstream ss;
        ss << "[";
        if (u == snk()) ss << "->";
        ss << Adt::item2string(u,s);
        if (u == src()) ss << "->";
        ss << ":";
        int cnt = 0;
        for (edge e = firstOut(u); e != 0; e = nextOut(u,e)) {
                vertex v = head(e);
                ss << " " << Adt::item2string(v,s) << "(" << cap(u,e) << ","
                   << f(u,e) << ")";
                if (++cnt >= 15 && nextOut(u,e) != 0) {
                        ss <<  "\n"; cnt = 0;
                }
        }
        ss <<  "]\n";
        s = ss.str();
        return s;
}

string& Flograph::toDotString(string& s) const {
        stringstream ss;
        ss << "digraph G { " << endl;
        ss << Adt::item2string(src(),s) 
           << " [ style = bold, peripheries = 2, color = red]; "
           << endl;
        ss << Adt::item2string(snk(),s) 
           << " [ style = bold, peripheries = 2, color = blue]; "
           << endl;
        int cnt = 0;
        for (edge e = first(); e != 0; e = next(e)) {
                vertex u = min(left(e),right(e));
                vertex v = max(left(e),right(e));
                ss << Adt::item2string(u,s) << " -> ";
                ss << Adt::item2string(v,s);
                ss << " [label = \"(" << cap(u,e) << "," << f(u,e) << ")\"]; ";
                if (++cnt == 10) { s += "\n"; cnt = 0; }
        }
        ss << "}\n" << endl;
        s = ss.str();
        return s;
}

void Flograph::shuffle(int vp[], int ep[]) {
        edge e;
        FloInfo *floInfo1 = new FloInfo[m()+1];

        Digraph::shuffle(vp,ep);
        for (e = 1; e <= m(); e++) floInfo1[ep[e]] = floInfo[e];
        for (e = 1; e <= m(); e++) floInfo[e] = floInfo1[e];
        s = vp[s]; t = vp[t];

        delete [] floInfo1;
}

void Flograph::rgraph(int numv, int nume, int mss) {
        mss = max(1,mss); mss = min(mss,(numv-2)/4); 
        numv = max(numv,3); nume = max(2*mss,nume);

        if (n() != numv || maxEdge < nume) resize(numv,nume); 
        else clear();
        Digraph::rgraph(numv-2,nume-2*mss);
        setSrc(numv-1); setSnk(numv);

        vertex *neighbors = new vertex[2*mss+1];
        Util::genPerm(2*mss,neighbors);
        for (int i = 1; i <= mss; i++) {
                join(src(),neighbors[i]);
        }
        Util::genPerm(2*mss,neighbors);
        for (int i = 1; i <= mss; i++) {
                join((numv-2)-neighbors[i],snk());
        }
        sortAdjLists();

        delete [] neighbors;
}

void Flograph::randCapacity(flow ec1, flow ec2) {
        for (edge e = first(); e != 0; e = next(e)) {
                if (tail(e) == s || head(e) == t)
                        setCapacity(e,Util::randint(1,ec1));
                else
                        setCapacity(e,Util::randint(1,ec2));
        }
}

} // ends namespace