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

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

     3 #ifndef SMART_GRAPH_H

     4 #define SMART_GRAPH_H

     6 #include <iostream>

     7 #include <vector>

     9 namespace hugo {

    11   class SmartGraph {

    13     static const int INVALID=-1;

    15     struct NodeT

    16     {

    17       int first_in,first_out;

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

    19     };

    20     struct EdgeT

    21     {

    22       int head, tail, next_in, next_out;

    23       //FIXME: is this necessary?

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

    25     };

    27     std::vector<NodeT> nodes;

    28     std::vector<EdgeT> edges;

    30     template <typename Key> class DynMapBase

    31     {

    32     protected:

    33       SmartGraph* G;

    34     public:

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

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

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

    38       virtual ~DynMapBase() {}

    39       friend class SmartGraph;

    40     };

    42   public:

    43     template <typename T> class DynEdgeMap;

    44     template <typename T> class DynEdgeMap;

    46     class NodeIt;

    47     class EdgeIt;

    49   protected:

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

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

    53   public:

    55     class EachNodeIt;

    56     class EachEdgeIt;

    57     class OutEdgeIt;

    58     class InEdgeIt;

    60     //      class NodeIt { int n; };

    61     //     class EachNodeIt : public NodeIt { };

    62     //     class EdgeIt { int n; };

    63     //     class EachEdgeIt : public EdgeIt {};

    64     //     class OutEdgeIt : public EdgeIt {};

    65     //     class InEdgeIt : public EdgeIt {};

    66     //    class SymEdgeIt;

    68     template <typename T> class NodeMap;

    69     template <typename T> class EdgeMap;

    71   public:

    73     /* default constructor */

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

    77     ~SmartGraph()

    78     {

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

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

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

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

    83     }

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

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

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

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

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

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

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

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

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

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

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

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

   103     EachNodeIt& getFirst(EachNodeIt& v) const {

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

   105     EachEdgeIt& getFirst(EachEdgeIt& e) const {

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

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

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

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

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

   112     template< typename It >

   113     It first() const {

   114       It e;

   115       getFirst(e);

   116       return e;

   117     }

   119     template< typename It >

   120     It first(NodeIt v) const {

   121       It e;

   122       getFirst(e, v);

   123       return e;

   124     }

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

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

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

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

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

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

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

   135     OutEdgeIt& goNext(OutEdgeIt& it) const

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

   137     InEdgeIt& goNext(InEdgeIt& it) const

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

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

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

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

   144     NodeIt addNode() {

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

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

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

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

   151       return n;

   152     }

   154     EdgeIt addEdge(NodeIt u, NodeIt v) {

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

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

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

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

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

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

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

   164       return e;

   165     }

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

   169     class NodeIt {

   170       friend class SmartGraph;

   171       template <typename T> friend class NodeMap;

   172       template <typename T> friend class DynNodeMap;

   174       friend class EdgeIt;

   175       friend class OutEdgeIt;

   176       friend class InEdgeIt;

   177       friend class SymEdgeIt;

   179     protected:

   180       int n;

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

   182     public:

   183       NodeIt() {}

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

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

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

   187     };

   189     class EachNodeIt : public NodeIt {

   190       friend class SmartGraph;

   191     public:

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

   193       EachNodeIt() : NodeIt() { }

   194     };

   196     class EdgeIt {

   197       friend class SmartGraph;

   198       template <typename T> friend class EdgeMap;

   199       template <typename T> friend class DynEdgeMap;

   201       friend class NodeIt;

   202       friend class EachNodeIt;

   203     protected:

   204       int n;

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

   206     public:

   207       EdgeIt() { }

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

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

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

   211     };

   213     class EachEdgeIt : public EdgeIt {

   214       friend class SmartGraph;

   215     public:

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

   217       EachEdgeIt() : EdgeIt() { }

   218     };

   220     class OutEdgeIt : public EdgeIt {

   221       friend class SmartGraph;

   222     public:

   223       OutEdgeIt() : EdgeIt() { }

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

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

   226     };

   228     class InEdgeIt : public EdgeIt {

   229       friend class SmartGraph;

   230     public:

   231       InEdgeIt() : EdgeIt() { }

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

   233     };

   235     // Map types

   237     template <typename T>

   238     class NodeMap {

   239       const SmartGraph& G;

   240       std::vector<T> container;

   241     public:

   242       typedef T ValueType;

   243       typedef NodeIt KeyType;

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

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

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

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

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

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

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

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

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

   253     };

   255     template <typename T>

   256     class EdgeMap {

   257       const SmartGraph& G;

   258       std::vector<T> container;

   259     public:

   260       typedef T ValueType;

   261       typedef EdgeIt KeyType;

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

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

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

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

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

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

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

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

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

   271     };

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

   274     {

   275       std::vector<T> container;

   277     public:

   278       typedef T ValueType;

   279       typedef NodeIt KeyType;

   281       DynNodeMap(SmartGraph &_G) :

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

   283       {

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

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

   286 	G->dyn_node_maps.push_back(this);

   287       }

   288       ~DynNodeMap()

   289       {

   290 	if(G) {

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

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

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

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

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

   296 	  if(*i==this) {

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

   298 	    G->dyn_node_maps.pop_back();

   299 	  }

   300 	}

   301       }

   303       void add(const NodeIt k)

   304       {

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

   306       }

   307       void erase(const NodeIt k)

   308       {

   309 	//FIXME: Please implement me.

   310       }

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

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

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

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

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

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

   319     };

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

   322     {

   323       std::vector<T> container;

   325     public:

   326       typedef T ValueType;

   327       typedef EdgeIt KeyType;

   329       DynEdgeMap(SmartGraph &_G) :

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

   331       {

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

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

   334 	G->dyn_edge_maps.push_back(this);

   335       }

   336       ~DynEdgeMap()

   337       {

   338 	if(G) {

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

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

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

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

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

   344 	  if(*i==this) {

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

   346 	    G->dyn_edge_maps.pop_back();

   347 	  }

   348 	}

   349       }

   351       void add(const EdgeIt k)

   352       {

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

   354       }

   355       void erase(const EdgeIt k)

   356       {

   357 	//FIXME: Please implement me.

   358       }

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

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

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

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

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

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

   367     };

   369   };

   370 } //namespace hugo

   372 #endif //SMART_GRAPH_H

author	alpar
	Sun, 22 Feb 2004 15:17:58 +0000
changeset 117	67253d52b284
parent 115	3d9681ef6116
child 129	1630a5b631c8
permissions	-rw-r--r--