/Users/jst/src/grafalgo/cpp/include/Graph.h

Go to the documentation of this file.

#ifndef GRAPH_H
#define GRAPH_H

#include "Adt.h"
#include "Util.h"
#include "List.h"
#include "ClistSet.h"
#include "SetPair.h"
#include "HashSet.h"
#include "Dheap.h"
#include <list>
#include <vector>

namespace grafalgo {

typedef int vertex;
typedef int edge;

class Graph : public Adt {
public:         Graph(int=1,int=1);
                ~Graph();

        // common methods
        void    clear();
        void    resize(int numv) { resize(numv, numv); }
        virtual void resize(int, int);
        void    expand(int numv) { expand(numv, max(numv,m())); }
        virtual void expand(int, int);
        void    copyFrom(const Graph&);

        // number of edges
        int     m() const;      

        // predicates
        bool    validVertex(int) const;
        bool    validEdge(int) const;

        // methods for iterating through overall edge list, adjacency lists
        edge    first() const;
        edge    next(edge) const;
        virtual edge firstAt(vertex) const;
        virtual edge nextAt(vertex,edge) const;

        // methods for accessing edge endpoints and length
        vertex  left(edge) const;       
        vertex  right(edge) const;      
        vertex  mate(vertex,edge) const;
        edge    getEdge(vertex,vertex) const;

        // methods for adding/removing edges
        virtual edge join(vertex,vertex);       
        bool    remove(edge);   

        // methods for computing properties
        int     getComponents(int*) const;

        // input
        friend istream& operator>>(istream&, Graph&);

        // create a string representation
        virtual string& edge2string(edge,string&) const;
        virtual string& edge2string(edge,vertex,string&) const;
        virtual string& toString(string&) const;
        virtual string& toDotString(string&) const;
        virtual string& elist2string(list<int>&, string&) const;

        void    sortAdjLists();

        // methods for creating random graphs
        void    scramble();
        void    rgraph(int, int, int);
        void    rgraph(int, int);
        void    addEdges(int);
        void    rbigraph(int, int);
        void    rtree(int);
        void    rcgraph(int,int);
protected:
        int     mm;                     
        int     maxEdge;                

        edge    *fe;                    

        struct EdgeInfo {
        vertex  l;                      
        vertex  r;                      
        };
        EdgeInfo *evec;                 

        SetPair *edges;                 

        ClistSet *adjLists;             




        // internal helper methods
        void    makeSpace(int, int);
        void    freeSpace();
        virtual edge joinWith(vertex,vertex,edge);      
        void    shuffle(int*, int*);
        virtual bool readAdjList(istream&);
        virtual string& adjList2string(vertex,string&) const;

        // methods for sorting ajacency lists
        int     ecmp(edge, edge, vertex) const;
        void    sortAlist(vertex);
};

inline int Graph::m() const { return mm; }

inline bool Graph::validVertex(int u) const { return 1 <= u && u <= n(); }

inline bool Graph::validEdge(int e) const { return edges->isIn(e); }

inline edge Graph::first() const { return edges->firstIn(); }

inline edge Graph::next(edge e) const { return edges->nextIn(e); }

inline edge Graph::firstAt(vertex v) const { 
        assert(1 <= v && v <= n());
        return fe[v]/2;
}

inline edge Graph::nextAt(vertex v, edge e) const {
        assert(1 <= v && v <= n() && 1 <= e && e <= maxEdge);
        if (v != evec[e].l && v != evec[e].r) return 0;
        int ee = (v == evec[e].l ? 2*e : 2*e+1);
        int ff = adjLists->suc(ee);
        return (fe[v] == ff ? 0 : ff/2);
}

inline vertex Graph::left(edge e) const {
        assert(0 <= e && e <= maxEdge);
        return evec[e].l;
}

inline vertex Graph::right(edge e) const {
        assert(0 <= e && e <= maxEdge);
        return (evec[e].l == 0 ? 0 : evec[e].r);
}

inline vertex Graph::mate(vertex v, edge e) const {
        assert(1 <= v && v <= n() && 1 <= e && e <= maxEdge);
        return (evec[e].l == 0 ?
                0 : (v == evec[e].l ?
                     evec[e].r : (v == evec[e].r ? evec[e].l : 0)));
}

} // ends namespace

#endif