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

Go to the documentation of this file.

#include "stdinc.h"
#include "Wgraph.h"

namespace grafalgo {

Wgraph::Wgraph(int numv, int maxe) : Graph(numv,maxe) {
        makeSpace(numv, maxe);
}

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

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

void Wgraph::freeSpace() { delete [] wt; }

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

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

void Wgraph::copyFrom(const Wgraph& 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.left(e),source.right(e));
                setWeight(ee,source.weight(e));
        }
        sortAdjLists();
}

bool Wgraph::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;
                if (u < v) { edge e = join(u,v); setWeight(e,w); }
        }
        return in.good();
}

string& Wgraph::edge2string(edge e, vertex u, string& s) const {
        stringstream ss;
        vertex v = mate(u,e);
        ss << "(" << item2string(u,s);
        ss << "," << item2string(v,s) << "," << weight(e) << ")";
        s = ss.str();
        return s;
}

string& Wgraph::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 = firstAt(u); e != 0; e = nextAt(u,e)) {
                vertex v = mate(u,e);
                ss <<  " " << item2string(v,s) << "(" << weight(e) << ")";
                if (++cnt >= 15 && nextAt(u,e) != 0) {
                        ss <<  "\n"; cnt = 0;
                }
        }
        ss <<  "]\n";
        s = ss.str();
        return s;
}

void Wgraph::randWeight(int lo, int hi) {
        for (edge e = first(); e != 0; e = next(e))
                setWeight(e,Util::randint(lo,hi));
}

string& Wgraph::toDotString(string& s) const {
        stringstream ss;
        ss << "graph G { " << 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 = \" " << weight(e) << " \"] ; "; 
                if (++cnt == 10) { s += "\n"; cnt = 0; }
        }
        ss << "}\n" << endl;
        s = ss.str();
        return s;
}

} // ends namespace