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

     1 // -*- mode:C++ -*-

     3 #ifndef SMART_GRAPH_H

     4 #define SMART_GRAPH_H

     6 #include <iostream>

     7 #include <vector>

     8 #include <limits.h>

    10 namespace hugo {

    12   class SmartGraph {

    14     static const int INVALID_EDGE=-1;

    15     static const int INVALID_NODE=INT_MAX;

    17     struct NodeT

    18     {

    19       int first_in,first_out;

    20       NodeT() : first_in(INVALID_EDGE), first_out(INVALID_EDGE) {}

    21     };

    22     struct EdgeT

    23     {

    24       int head, tail, next_in, next_out;

    25       //FIXME: is this necessary?

    26       EdgeT() : next_in(INVALID_EDGE), next_out(INVALID_EDGE) {}

    27     };

    29     std::vector<NodeT> nodes;

    31     std::vector<EdgeT> edges;

    33     template <typename Key> class DynMapBase

    34     {

    35     protected:

    36       SmartGraph* G;

    37     public:

    38       virtual void add(const Key k) = NULL;

    39       virtual void erase(const Key k) = NULL;

    40       DynMapBase(SmartGraph &_G) : G(&_G) {}

    41       virtual ~DynMapBase() {}

    42       friend class SmartGraph;

    43     };

    45   public:

    46     template <typename T> class DynEdgeMap;

    47     template <typename T> class DynEdgeMap;

    49     class NodeIt;

    50     class EdgeIt;

    52   protected:

    53     std::vector<DynMapBase<NodeIt> * > dyn_node_maps;

    54     std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;

    56   public:

    58     class EachNodeIt;

    59     class EachEdgeIt;

    60     class OutEdgeIt;

    61     class InEdgeIt;

    63     //      class NodeIt { int n; };

    64     //     class EachNodeIt : public NodeIt { };

    65     //     class EdgeIt { int n; };

    66     //     class EachEdgeIt : public EdgeIt {};

    67     //     class OutEdgeIt : public EdgeIt {};

    68     //     class InEdgeIt : public EdgeIt {};

    69     //    class SymEdgeIt;

    71     template <typename T> class NodeMap;

    72     template <typename T> class EdgeMap;

    74   public:

    76     /* default constructor */

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

    79     SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }

    81     ~SmartGraph()

    82     {

    83       for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();

    84 	  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;

    85       for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();

    86 	  i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;

    87     }

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

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

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

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

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

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

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

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

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

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

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

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

   107     EachNodeIt& getFirst(EachNodeIt& v) const {

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

   109     EachEdgeIt& getFirst(EachEdgeIt& e) const {

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

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

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

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

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

   116     template< typename It >

   117     It first() const {

   118       It e;

   119       getFirst(e);

   120       return e;

   121     }

   123     template< typename It >

   124     It first(NodeIt v) const {

   125       It e;

   126       getFirst(e, v);

   127       return e;

   128     }

   130     bool valid(EdgeIt e) const { return e.n!=INVALID_EDGE; }

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

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

   134     void setInvalid(EdgeIt &e) { e.n=INVALID_EDGE; }

   135     void setInvalid(NodeIt &n) { n.n=INVALID_NODE; }

   137     template <typename It> It next(It it) const

   138       //    { It tmp(it); return goNext(tmp); }

   139     { It tmp; tmp.n=it.n+1; return tmp; }

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

   142     OutEdgeIt& goNext(OutEdgeIt& it) const

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

   144     InEdgeIt& goNext(InEdgeIt& it) const

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

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

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

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

   151     NodeIt addNode() {

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

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

   155       for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();

   156 	  i!=dyn_node_maps.end(); ++i) (**i).add(n.n);

   158       return n;

   159     }

   161     EdgeIt addEdge(NodeIt u, NodeIt v) {

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

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

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

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

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

   168       for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();

   169 	  i!=dyn_edge_maps.end(); ++i) (**i).add(e.n);

   171       return e;

   172     }

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

   176     class NodeIt {

   177       friend class SmartGraph;

   178       template <typename T> friend class NodeMap;

   179       template <typename T> friend class DynNodeMap;

   181       friend class EdgeIt;

   182       friend class OutEdgeIt;

   183       friend class InEdgeIt;

   184       friend class SymEdgeIt;

   186     protected:

   187       int n;

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

   189     public:

   190       NodeIt() {}

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

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

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

   194     };

   196     class EachNodeIt : public NodeIt {

   197       friend class SmartGraph;

   198     public:

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

   200       EachNodeIt() : NodeIt() { }

   201     };

   203     class EdgeIt {

   204       friend class SmartGraph;

   205       template <typename T> friend class EdgeMap;

   206       template <typename T> friend class DynEdgeMap;

   208       friend class NodeIt;

   209       friend class EachNodeIt;

   210     protected:

   211       int n;

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

   213     public:

   214       EdgeIt() { }

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

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

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

   218     };

   220     class EachEdgeIt : public EdgeIt {

   221       friend class SmartGraph;

   222     public:

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

   224       EachEdgeIt() : EdgeIt() { }

   225     };

   227     class OutEdgeIt : public EdgeIt {

   228       friend class SmartGraph;

   229     public:

   230       OutEdgeIt() : EdgeIt() { }

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

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

   233     };

   235     class InEdgeIt : public EdgeIt {

   236       friend class SmartGraph;

   237     public:

   238       InEdgeIt() : EdgeIt() { }

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

   240     };

   242     // Map types

   244     template <typename T>

   245     class NodeMap {

   246       const SmartGraph& G;

   247       std::vector<T> container;

   248     public:

   249       typedef T ValueType;

   250       typedef NodeIt KeyType;

   251       NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }

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

   253 	G(_G), container(G.maxNodeId(), a) { }

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

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

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

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

   258       void update() { container.resize(G.maxNodeId()); }

   259       void update(T a) { container.resize(G.maxNodeId(), a); }

   260     };

   262     template <typename T>

   263     class EdgeMap {

   264       const SmartGraph& G;

   265       std::vector<T> container;

   266     public:

   267       typedef T ValueType;

   268       typedef EdgeIt KeyType;

   269       EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }

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

   271 	G(_G), container(G.maxEdgeId(), a) { }

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

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

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

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

   276       void update() { container.resize(G.maxEdgeId()); }

   277       void update(T a) { container.resize(G.maxEdgeId(), a); }

   278     };

   280     template <typename T> class DynNodeMap : public DynMapBase<NodeIt>

   281     {

   282       std::vector<T> container;

   284     public:

   285       typedef T ValueType;

   286       typedef NodeIt KeyType;

   288       DynNodeMap(SmartGraph &_G) :

   289 	DynMapBase<NodeIt>(_G), container(_G.maxNodeId())

   290       {

   291 	//FIXME: What if there are empty Id's?

   292 	//FIXME: Can I use 'this' in a constructor?

   293 	G->dyn_node_maps.push_back(this);

   294       }

   295       ~DynNodeMap()

   296       {

   297 	if(G) {

   298 	  std::vector<DynMapBase<NodeIt>* >::iterator i;

   299 	  for(i=G->dyn_node_maps.begin();

   300 	      i!=G->dyn_node_maps.end() && *i!=this; ++i) ;

   301 	  //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...

   302 	  //A better way to do that: (Is this really important?)

   303 	  if(*i==this) {

   304 	    *i=G->dyn_node_maps.back();

   305 	    G->dyn_node_maps.pop_back();

   306 	  }

   307 	}

   308       }

   310       void add(const NodeIt k)

   311       {

   312 	if(k.n>=container.size()) container.resize(k.n+1);

   313       }

   314       void erase(const NodeIt k)

   315       {

   316 	//FIXME: Please implement me.

   317       }

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

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

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

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

   324       void update() {}    //Useless for DynMaps

   325       void update(T a) {}  //Useless for DynMaps

   326     };

   328     template <typename T> class DynEdgeMap : public DynMapBase<EdgeIt>

   329     {

   330       std::vector<T> container;

   332     public:

   333       typedef T ValueType;

   334       typedef EdgeIt KeyType;

   336       DynEdgeMap(SmartGraph &_G) :

   337 	DynMapBase<EdgeIt>(_G), container(_G.maxEdgeId())

   338       {

   339 	//FIXME: What if there are empty Id's?

   340 	//FIXME: Can I use 'this' in a constructor?

   341 	G->dyn_edge_maps.push_back(this);

   342       }

   343       ~DynEdgeMap()

   344       {

   345 	if(G) {

   346 	  std::vector<DynMapBase<EdgeIt>* >::iterator i;

   347 	  for(i=G->dyn_edge_maps.begin();

   348 	      i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;

   349 	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...

   350 	  //A better way to do that: (Is this really important?)

   351 	  if(*i==this) {

   352 	    *i=G->dyn_edge_maps.back();

   353 	    G->dyn_edge_maps.pop_back();

   354 	  }

   355 	}

   356       }

   358       void add(const EdgeIt k)

   359       {

   360 	if(k.n>=int(container.size())) container.resize(k.n+1);

   361       }

   362       void erase(const EdgeIt k)

   363       {

   364 	//FIXME: Please implement me.

   365       }

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

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

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

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

   372       void update() {}    //Useless for DynMaps

   373       void update(T a) {}  //Useless for DynMaps

   374     };

   376   };

   377 } //namespace hugo

   379 #endif //SMART_GRAPH_H

author	marci
	Mon, 01 Mar 2004 12:06:56 +0000
changeset 138	c6297c121409
parent 130	571003783202
child 157	ee17030e5f47
permissions	-rw-r--r--