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

Go to the documentation of this file.

#include "Wdigraph.h"

namespace grafalgo {

Wdigraph::Wdigraph(int numv, int maxe) : Digraph(numv,maxe) {
        makeSpace(numv,maxe);
}

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

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

void Wdigraph::freeSpace() { delete [] len; }

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

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

void Wdigraph::copyFrom(const Wdigraph& 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));
                setLength(ee,source.length(e));
        }
        sortAdjLists();
}

bool Wdigraph::readAdjList(istream& in) {
        if (!Util::verify(in,'[')) return 0;
        vertex u;
        if (!Adt::readItem(in,u)) return 0;
        if (u > n()) expand(u,m());
        if (!Util::verify(in,':')) return 0;
        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 w;
                if (!Util::verify(in,'(') || !Util::readInt(in,w) ||
                    !Util::verify(in,')'))
                        return 0;
                edge e = join(u,v); setLength(e,w);
        }
        return in.good();
}

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


string& Wdigraph::edge2string(edge e, string& s) const {
        stringstream ss;
        vertex u = tail(e); vertex v = head(e);
        ss << "(" << item2string(u,s) << ",";
        ss << item2string(v,s) << "," << length(e) + ")";
        s = ss.str();
        return s;
}

string& Wdigraph::toDotString(string& s) const {
        stringstream ss;
        ss << "digraph G { " << endl;
        int cnt = 0;
        for (edge e = first(); e != 0; e = next(e)) {
                vertex u = tail(e); vertex v = head(e);
                ss << Adt::item2string(u,s) << " -> ";
                ss << Adt::item2string(v,s);
                ss << " [label = \" " << length(e) << " \"] ; "; 
                if (++cnt == 10) { s += "\n"; cnt = 0; }
        }
        ss << "}\n" << endl;
        s = ss.str();
        return s;
}

/*
bool Wdigraph::readEdge(istream& in) {
        vertex u, v; int len;
        if (!Util::verify(in,'(') || !Util::readNode(in,u,n()) ||
            !Util::verify(in,',') || !Util::readNode(in,v,n()) ||
            !Util::verify(in,',') || !Util::readNum(in,len) ||
            !Util::verify(in,')')) {
                return false;
        }
        edge e = join(u,v);
        setLength(e,len);

        return true;
}
*/

void Wdigraph::randLength(int lo, int hi) {
        for (edge e = first(); e != 0; e = next(e))
                setLength(e,Util::randint(lo,hi));
}

} // ends namespace