lemon-0.x: src/work/alpar/smart_graph.h@7a2d991e9852

     1 #ifndef SMART_GRAPH_H

     2 #define SMART_GRAPH_H

     4 #include <iostream>

     5 #include <vector>

     7 namespace marci {

     9   class SmartGraph {

    11     static const int INVALID=-1;

    13     struct NodeT

    14     {

    15       int first_in,first_out;

    16       NodeT() : first_in(INVALID), first_out(INVALID) {}

    17     };

    18     struct EdgeT

    19     {

    20       int head, tail, next_in, next_out;

    21       //FIXME: is this necessary?

    22       EdgeT() : next_in(INVALID), next_out(INVALID) {}

    23     };

    25     std::vector<NodeT> nodes;

    26     std::vector<EdgeT> edges;

    29   public:

    31     class NodeIt;

    32     class EachNodeIt;

    33     class EdgeIt;

    34     class EachEdgeIt;

    35     class OutEdgeIt;

    36     class InEdgeIt;

    38 //      class NodeIt { int n; };

    39 //     class EachNodeIt : public NodeIt { };

    40 //     class EdgeIt { int n; };

    41 //     class EachEdgeIt : public EdgeIt {};

    42 //     class OutEdgeIt : public EdgeIt {};

    43 //     class InEdgeIt : public EdgeIt {};

    44     //    class SymEdgeIt;

    46  template <typename T> class NodeMap;

    47     template <typename T> class EdgeMap;

    49   private:

    51     template <typename T> friend class NodeMap;

    52     template <typename T> friend class EdgeMap;

    54     template <typename T>

    55     class NodeMap {

    56       const SmartGraph& G;

    57       std::vector<T> container;

    58     public:

    59       typedef T ValueType;

    60       typedef NodeIt KeyType;

    61       NodeMap(const SmartGraph& _G) : G(_G), container(G.nodeNum()) { }

    62       NodeMap(const SmartGraph& _G, T a) :

    63 	G(_G), container(G.nodeNum(), a) { }

    64       void set(NodeIt n, T a) { container[n.n]=a; }

    65       T get(NodeIt n) const { return container[n.n]; }

    66       T& operator[](NodeIt n) { return container[n.n]; }

    67       const T& operator[](NodeIt n) const { return container[n.n]; }

    68       void resize() { container.resize(G.nodeNum()); }

    69       void resize(T a) { container.resize(G.nodeNum(), a); }

    70     };

    72     template <typename T>

    73     class EdgeMap {

    74       const SmartGraph& G;

    75       std::vector<T> container;

    76     public:

    77       typedef T ValueType;

    78       typedef EdgeIt KeyType;

    79       EdgeMap(const SmartGraph& _G) : G(_G), container(G.edgeNum()) { }

    80       EdgeMap(const SmartGraph& _G, T a) :

    81 	G(_G), container(G.edgeNum(), a) { }

    82       void set(EdgeIt e, T a) { container[e.n]=a; }

    83       T get(EdgeIt e) const { return container[e.n]; }

    84       T& operator[](EdgeIt e) { return container[e.n]; }

    85       const T& operator[](EdgeIt e) const { return container[e.n]; }

    86       void resize() { container.resize(G.edgeNum()); }

    87       void resize(T a) { container.resize(G.edgeNum(), a); }

    88     };

    90   public:

    92     /* default constructor */

    94     SmartGraph() : nodes(), edges() { }

    96     ~SmartGraph() {}

    98     int nodeNum() const { return nodes.size(); }  //FIXME: What is this?

    99     int edgeNum() const { return edges.size(); }  //FIXME: What is this?

   101     NodeIt tail(EdgeIt e) const { return edges[e.n].tail; }

   102     NodeIt head(EdgeIt e) const { return edges[e.n].head; }

   104     NodeIt aNode(const OutEdgeIt& e) const { return tail(e); }

   105     NodeIt aNode(const InEdgeIt& e) const { return head(e); }

   106     //NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); }

   108     NodeIt bNode(const OutEdgeIt& e) const { return head(e); }

   109     NodeIt bNode(const InEdgeIt& e) const { return tail(e); }

   110     //NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); }

   112     EachNodeIt& getFirst(EachNodeIt& v) const {

   113       v=EachNodeIt(*this); return v; }

   114     EachEdgeIt& getFirst(EachEdgeIt& e) const {

   115       e=EachEdgeIt(*this); return e; }

   116     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt v) const {

   117       e=OutEdgeIt(*this,v); return e; }

   118     InEdgeIt& getFirst(InEdgeIt& e, const NodeIt v) const {

   119       e=InEdgeIt(*this,v); return e; }

   121     template< typename It >

   122     It first() const {

   123       It e;

   124       getFirst(e);

   125       return e;

   126     }

   128     template< typename It >

   129     It first(NodeIt v) const {

   130       It e;

   131       getFirst(e, v);

   132       return e;

   133     }

   135     bool valid(EdgeIt e) const { return e.n!=INVALID; }

   136     bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); }

   137     bool valid(NodeIt n) const { return n.n<int(nodes.size()); }

   139     template <typename It> It next(It it) const {

   140       It tmp(it); return goNext(it); }

   142     NodeIt& goNext(NodeIt& it) const { ++it.n; return it; }

   143     OutEdgeIt& goNext(OutEdgeIt& it) const

   144     { it.n=edges[it.n].next_out; return it; }

   145     InEdgeIt& goNext(InEdgeIt& it) const

   146     { it.n=edges[it.n].next_in; return it; }

   147     EachEdgeIt& goNext(EachEdgeIt& it) const { ++it.n; return it; }

   149     int id(NodeIt v) const { return v.n; }

   150     int id(EdgeIt e) const { return e.n; }

   152     NodeIt addNode() {

   153       NodeIt n; n.n=nodes.size();

   154       nodes.push_back(NodeT()); //FIXME: Hmmm...

   155       return n;

   156     }

   157     EdgeIt addEdge(NodeIt u, NodeIt v) {

   158       EdgeIt e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...

   159       edges[e.n].tail=u.n; edges[e.n].head=v.n;

   160       edges[e.n].next_out=nodes[u.n].first_out;

   161       edges[e.n].next_in=nodes[v.n].first_in;

   162       nodes[u.n].first_out=nodes[v.n].first_in=e.n;

   163       return e;

   164     }

   166     void clear() {nodes.clear();edges.clear();}

   168     class NodeIt {

   169       friend class SmartGraph;

   170       template <typename T> friend class NodeMap;

   172       friend class EdgeIt;

   173       friend class OutEdgeIt;

   174       friend class InEdgeIt;

   175       friend class SymEdgeIt;

   177     protected:

   178       int n;

   179       friend int SmartGraph::id(NodeIt v) const;

   180     public:

   181       NodeIt() {}

   182       NodeIt(int nn) {n=nn;}

   183       bool operator==(const NodeIt i) const {return n==i.n;}

   184       bool operator!=(const NodeIt i) const {return n!=i.n;}

   185     };

   187     class EachNodeIt : public NodeIt {

   188       friend class SmartGraph;

   189     public:

   190       EachNodeIt(const SmartGraph& G) : NodeIt(0) { }

   191       EachNodeIt() : NodeIt() { }

   192     };

   194     class EdgeIt {

   195       friend class SmartGraph;

   196       template <typename T> friend class EdgeMap;

   198       friend class NodeIt;

   199       friend class EachNodeIt;

   200     protected:

   201       int n;

   202       friend int SmartGraph::id(EdgeIt e) const;

   203     public:

   204       EdgeIt() { }

   205       EdgeIt(int nn) {n=nn;}

   206       bool operator==(const EdgeIt i) const {return n==i.n;}

   207       bool operator!=(const EdgeIt i) const {return n!=i.n;}

   208     };

   210     class EachEdgeIt : public EdgeIt {

   211       friend class SmartGraph;

   212     public:

   213       EachEdgeIt(const SmartGraph& G) : EdgeIt(0) { }

   214       EachEdgeIt() : EdgeIt() { }

   215     };

   217     class OutEdgeIt : public EdgeIt {

   218       friend class SmartGraph;

   219     public:

   220       OutEdgeIt() : EdgeIt() { }

   221       OutEdgeIt(const SmartGraph& G,const NodeIt v)

   222 	: EdgeIt(G.nodes[v.n].first_out) {}

   223     };

   225     class InEdgeIt : public EdgeIt {

   226       friend class SmartGraph;

   227     public:

   228       InEdgeIt() : EdgeIt() { }

   229       InEdgeIt(const SmartGraph& G,NodeIt v) :EdgeIt(G.nodes[v.n].first_in){}

   230     };

   231   };

   232 } //namespace marci

   234 #endif //SMART_GRAPH_H

author	alpar
	Fri, 20 Feb 2004 00:29:19 +0000
changeset 104	7a2d991e9852
child 105	a3c73e9b9b2e
permissions	-rw-r--r--