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

     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() { }

    80     ~SmartGraph()

    81     {

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

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

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

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

    86     }

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

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

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

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

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

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

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

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

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

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

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

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

   106     EachNodeIt& getFirst(EachNodeIt& v) const {

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

   108     EachEdgeIt& getFirst(EachEdgeIt& e) const {

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

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

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

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

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

   115     template< typename It >

   116     It first() const {

   117       It e;

   118       getFirst(e);

   119       return e;

   120     }

   122     template< typename It >

   123     It first(NodeIt v) const {

   124       It e;

   125       getFirst(e, v);

   126       return e;

   127     }

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

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

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

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

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

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

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

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

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

   141     OutEdgeIt& goNext(OutEdgeIt& it) const

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

   143     InEdgeIt& goNext(InEdgeIt& it) const

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

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

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

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

   150     NodeIt addNode() {

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

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

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

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

   157       return n;

   158     }

   160     EdgeIt addEdge(NodeIt u, NodeIt v) {

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

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

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

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

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

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

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

   170       return e;

   171     }

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

   175     class NodeIt {

   176       friend class SmartGraph;

   177       template <typename T> friend class NodeMap;

   178       template <typename T> friend class DynNodeMap;

   180       friend class EdgeIt;

   181       friend class OutEdgeIt;

   182       friend class InEdgeIt;

   183       friend class SymEdgeIt;

   185     protected:

   186       int n;

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

   188     public:

   189       NodeIt() {}

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

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

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

   193     };

   195     class EachNodeIt : public NodeIt {

   196       friend class SmartGraph;

   197     public:

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

   199       EachNodeIt() : NodeIt() { }

   200     };

   202     class EdgeIt {

   203       friend class SmartGraph;

   204       template <typename T> friend class EdgeMap;

   205       template <typename T> friend class DynEdgeMap;

   207       friend class NodeIt;

   208       friend class EachNodeIt;

   209     protected:

   210       int n;

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

   212     public:

   213       EdgeIt() { }

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

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

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

   217     };

   219     class EachEdgeIt : public EdgeIt {

   220       friend class SmartGraph;

   221     public:

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

   223       EachEdgeIt() : EdgeIt() { }

   224     };

   226     class OutEdgeIt : public EdgeIt {

   227       friend class SmartGraph;

   228     public:

   229       OutEdgeIt() : EdgeIt() { }

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

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

   232     };

   234     class InEdgeIt : public EdgeIt {

   235       friend class SmartGraph;

   236     public:

   237       InEdgeIt() : EdgeIt() { }

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

   239     };

   241     // Map types

   243     template <typename T>

   244     class NodeMap {

   245       const SmartGraph& G;

   246       std::vector<T> container;

   247     public:

   248       typedef T ValueType;

   249       typedef NodeIt KeyType;

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

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

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

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

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

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

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

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

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

   259     };

   261     template <typename T>

   262     class EdgeMap {

   263       const SmartGraph& G;

   264       std::vector<T> container;

   265     public:

   266       typedef T ValueType;

   267       typedef EdgeIt KeyType;

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

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

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

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

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

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

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

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

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

   277     };

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

   280     {

   281       std::vector<T> container;

   283     public:

   284       typedef T ValueType;

   285       typedef NodeIt KeyType;

   287       DynNodeMap(SmartGraph &_G) :

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

   289       {

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

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

   292 	G->dyn_node_maps.push_back(this);

   293       }

   294       ~DynNodeMap()

   295       {

   296 	if(G) {

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

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

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

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

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

   302 	  if(*i==this) {

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

   304 	    G->dyn_node_maps.pop_back();

   305 	  }

   306 	}

   307       }

   309       void add(const NodeIt k)

   310       {

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

   312       }

   313       void erase(const NodeIt k)

   314       {

   315 	//FIXME: Please implement me.

   316       }

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

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

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

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

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

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

   325     };

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

   328     {

   329       std::vector<T> container;

   331     public:

   332       typedef T ValueType;

   333       typedef EdgeIt KeyType;

   335       DynEdgeMap(SmartGraph &_G) :

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

   337       {

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

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

   340 	G->dyn_edge_maps.push_back(this);

   341       }

   342       ~DynEdgeMap()

   343       {

   344 	if(G) {

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

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

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

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

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

   350 	  if(*i==this) {

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

   352 	    G->dyn_edge_maps.pop_back();

   353 	  }

   354 	}

   355       }

   357       void add(const EdgeIt k)

   358       {

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

   360       }

   361       void erase(const EdgeIt k)

   362       {

   363 	//FIXME: Please implement me.

   364       }

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

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

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

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

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

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

   373     };

   375   };

   376 } //namespace hugo

   378 #endif //SMART_GRAPH_H

author	klao
	Thu, 26 Feb 2004 16:07:40 +0000
changeset 132	1ac27e476e25
parent 129	1630a5b631c8
child 136	e342e66d9762
permissions	-rw-r--r--