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

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

     3 #ifndef SMART_GRAPH_H

     4 #define SMART_GRAPH_H

     6 #include <vector>

     7 #include <limits.h>

     9 struct _Invalid {} Invalid;

    11 namespace hugo {

    13   class SmartGraph {

    15 //     static const int INVALID=-1;

    16 //     static const int INVALID_NODE=INT_MAX;

    18     struct NodeT

    19     {

    20       int first_in,first_out;

    21       NodeT() : first_in(-1), first_out(-1) {}

    22     };

    23     struct EdgeT

    24     {

    25       int head, tail, next_in, next_out;

    26       //FIXME: is this necessary?

    27       EdgeT() : next_in(-1), next_out(-1) {}

    28     };

    30     std::vector<NodeT> nodes;

    32     std::vector<EdgeT> edges;

    34     template <typename Key> class DynMapBase

    35     {

    36     protected:

    37       SmartGraph* G;

    38     public:

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

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

    41       DynMapBase(const SmartGraph &_G) : G(&_G) {}

    42       virtual ~DynMapBase() {}

    43       friend class SmartGraph;

    44     };

    45   public:

    46     template <typename T> class DynEdgeMap;

    47     template <typename T> class DynEdgeMap;

    49     class NodeIt;

    50     class EdgeIt;

    52   protected:

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

    54     mutable 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!=-1; }

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

   132     bool valid(NodeIt n) const { return n.n!=-1; }

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

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

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

   138     { It tmp(it); return next(tmp); }

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

   141     NodeIt& next(NodeIt& it) const { it.n=(it.n+2)%nodes.size()-1; return it; }

   142     OutEdgeIt& next(OutEdgeIt& it) const

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

   144     InEdgeIt& next(InEdgeIt& it) const

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

   146     EachEdgeIt& next(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);

   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       NodeIt(int nn) {n=nn;}

   190     public:

   191       NodeIt() {}

   192       NodeIt (_Invalid i) { n=-1; }

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

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

   195       bool operator<(const NodeIt i) const {return n<i.n;}

   196     };

   198     class EachNodeIt : public NodeIt {

   199       friend class SmartGraph;

   200     public:

   201       EachNodeIt(const SmartGraph& G) : NodeIt(G.nodes.size()?0:-1) { }

   202       EachNodeIt() : NodeIt() { }

   203     };

   205     class EdgeIt {

   206       friend class SmartGraph;

   207       template <typename T> friend class EdgeMap;

   208       template <typename T> friend class DynEdgeMap;

   210       friend class NodeIt;

   211       friend class EachNodeIt;

   212     protected:

   213       int n;

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

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

   217     public:

   218       EdgeIt() { }

   219       EdgeIt (_Invalid i) { n=-1; }

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

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

   222       bool operator<(const EdgeIt i) const {return n<i.n;}

   223     };

   225     class EachEdgeIt : public EdgeIt {

   226       friend class SmartGraph;

   227     public:

   228       EachEdgeIt(const SmartGraph& G) : EdgeIt(G.edges.size()-1) { }

   229       EachEdgeIt (_Invalid i) : EdgeIt(i) { }

   230       EachEdgeIt() : EdgeIt() { }

   231     };

   233     class OutEdgeIt : public EdgeIt {

   234       friend class SmartGraph;

   235     public:

   236       OutEdgeIt() : EdgeIt() { }

   237       OutEdgeIt (_Invalid i) : EdgeIt(i) { }

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

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

   241     };

   243     class InEdgeIt : public EdgeIt {

   244       friend class SmartGraph;

   245     public:

   246       InEdgeIt() : EdgeIt() { }

   247       InEdgeIt (_Invalid i) : EdgeIt(i) { }

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

   249     };

   251     // Map types

   253     template <typename T>

   254     class NodeMap {

   255       const SmartGraph& G;

   256       std::vector<T> container;

   257     public:

   258       typedef T ValueType;

   259       typedef NodeIt KeyType;

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

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

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

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

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

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

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

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

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

   269     };

   271     template <typename T>

   272     class EdgeMap {

   273       const SmartGraph& G;

   274       std::vector<T> container;

   275     public:

   276       typedef T ValueType;

   277       typedef EdgeIt KeyType;

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

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

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

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

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

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

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

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

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

   287     };

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

   290     {

   291       std::vector<T> container;

   293     public:

   294       typedef T ValueType;

   295       typedef NodeIt KeyType;

   297       DynNodeMap(const SmartGraph &_G) :

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

   299       {

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

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

   302 	G->dyn_node_maps.push_back(this);

   303       }

   304       ~DynNodeMap()

   305       {

   306 	if(G) {

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

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

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

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

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

   312 	  if(*i==this) {

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

   314 	    G->dyn_node_maps.pop_back();

   315 	  }

   316 	}

   317       }

   319       void add(const NodeIt k)

   320       {

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

   322       }

   323 //       void erase(const NodeIt k)

   324 //       {

   325 // 	//FIXME: Please implement me.

   326 //       }

   327 //       void erase(const EdgeIt k)

   328 //       {

   329 // 	//FIXME: Please implement me.

   330 //       }

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

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

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

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

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

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

   339     };

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

   342     {

   343       std::vector<T> container;

   345     public:

   346       typedef T ValueType;

   347       typedef EdgeIt KeyType;

   349       DynEdgeMap(const SmartGraph &_G) :

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

   351       {

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

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

   354 	G->dyn_edge_maps.push_back(this);

   355       }

   356       ~DynEdgeMap()

   357       {

   358 	if(G) {

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

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

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

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

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

   364 	  if(*i==this) {

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

   366 	    G->dyn_edge_maps.pop_back();

   367 	  }

   368 	}

   369       }

   371       void add(const EdgeIt k)

   372       {

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

   374       }

   375       void erase(const EdgeIt k)

   376       {

   377 	//FIXME: Please implement me.

   378       }

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

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

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

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

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

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

   387     };

   389   };

   390 } //namespace hugo

   395 #endif //SMART_GRAPH_H

author	alpar
	Wed, 10 Mar 2004 16:43:50 +0000
changeset 162	abfae454c3b5
parent 136	e342e66d9762
child 164	970b265696b0
permissions	-rw-r--r--