Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/alpar/smart_graph.h
changeset 160 f1a7005e9dff
parent 136 e342e66d9762
child 164 970b265696b0
equal deleted inserted replaced
7:c9b8e5247bd5 8:7b75acf5e367 
     1 // -*- mode:C++ -*-
 
     1 // -*- mode:C++ -*-
 
     2 
     2 
     3 #ifndef SMART_GRAPH_H
 
     3 #ifndef SMART_GRAPH_H
 
     4 #define SMART_GRAPH_H
 
     4 #define SMART_GRAPH_H
 
     5 
     5 
     6 #include <iostream>
 
       
     7 #include <vector>
 
     6 #include <vector>
 
     8 #include <limits.h>
 
     7 #include <limits.h>
 
     9 
     8 
       
     9 struct _Invalid {} Invalid;
 
       
    10 
    10 namespace hugo {
 
    11 namespace hugo {
 
    11 
    12 
    12   class SmartGraph {
 
    13   class SmartGraph {
 
    13 
    14 
    14     static const int INVALID_EDGE=-1;
 
    15 //     static const int INVALID=-1;
 
    15     static const int INVALID_NODE=INT_MAX;
 
    16 //     static const int INVALID_NODE=INT_MAX;
 
    16 
    17 
    17     struct NodeT 
    18     struct NodeT 
    18     {
 
    19     {
 
    19       int first_in,first_out;      
    20       int first_in,first_out;      
    20       NodeT() : first_in(INVALID_EDGE), first_out(INVALID_EDGE) {}
 
    21       NodeT() : first_in(-1), first_out(-1) {}
 
    21     };
 
    22     };
 
    22     struct EdgeT 
    23     struct EdgeT 
    23     {
 
    24     {
 
    24       int head, tail, next_in, next_out;      
    25       int head, tail, next_in, next_out;      
    25       //FIXME: is this necessary?
 
    26       //FIXME: is this necessary?
 
    26       EdgeT() : next_in(INVALID_EDGE), next_out(INVALID_EDGE) {}  
    27       EdgeT() : next_in(-1), next_out(-1) {}  
    27     };
 
    28     };
 
    28 
    29 
    29     std::vector<NodeT> nodes;
 
    30     std::vector<NodeT> nodes;
 
    30 
    31 
    31     std::vector<EdgeT> edges;
 
    32     std::vector<EdgeT> edges;
 
    35     protected:
 
    36     protected:
 
    36       SmartGraph* G; 
    37       SmartGraph* G; 
    37     public:
 
    38     public:
 
    38       virtual void add(const Key k) = NULL;
 
    39       virtual void add(const Key k) = NULL;
 
    39       virtual void erase(const Key k) = NULL;
 
    40       virtual void erase(const Key k) = NULL;
 
    40       DynMapBase(SmartGraph &_G) : G(&_G) {}
 
    41       DynMapBase(const SmartGraph &_G) : G(&_G) {}
 
    41       virtual ~DynMapBase() {}
 
    42       virtual ~DynMapBase() {}
 
    42       friend class SmartGraph;
 
    43       friend class SmartGraph;
 
    43     };
 
    44     };
 
    44 
       
    45   public:
 
    45   public:
 
    46     template <typename T> class DynEdgeMap;
 
    46     template <typename T> class DynEdgeMap;
 
    47     template <typename T> class DynEdgeMap;
 
    47     template <typename T> class DynEdgeMap;
 
    48 
    48 
    49     class NodeIt;
 
    49     class NodeIt;
 
    50     class EdgeIt;
 
    50     class EdgeIt;
 
    51 
    51 
    52   protected:
 
    52   protected:
 
    53     std::vector<DynMapBase<NodeIt> * > dyn_node_maps;
 
    53     mutable std::vector<DynMapBase<NodeIt> * > dyn_node_maps;
 
    54     std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;
 
    54     mutable std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;
 
    55     
    55     
    56   public:
 
    56   public:
 
    57 
    57 
    58     class EachNodeIt;
 
    58     class EachNodeIt;
 
    59     class EachEdgeIt;
 
    59     class EachEdgeIt;
 
    60     class OutEdgeIt;
 
    60     class OutEdgeIt;
 
    61     class InEdgeIt;
 
    61     class InEdgeIt;
 
    62     
    62     
    63     //      class NodeIt { int n; };
 
    63     //     class NodeIt { int n; };
 
    64     //     class EachNodeIt : public NodeIt { };
 
    64     //     class EachNodeIt : public NodeIt { };
 
    65     //     class EdgeIt { int n; };
 
    65     //     class EdgeIt { int n; };
 
    66     //     class EachEdgeIt : public EdgeIt {};
 
    66     //     class EachEdgeIt : public EdgeIt {};
 
    67     //     class OutEdgeIt : public EdgeIt {};
 
    67     //     class OutEdgeIt : public EdgeIt {};
 
    68     //     class InEdgeIt : public EdgeIt {};
 
    68     //     class InEdgeIt : public EdgeIt {};
 
    69     //    class SymEdgeIt;
 
    69     //     class SymEdgeIt;
 
    70     
    70     
    71     template <typename T> class NodeMap;
 
    71     template <typename T> class NodeMap;
 
    72     template <typename T> class EdgeMap;
 
    72     template <typename T> class EdgeMap;
 
    73     
    73     
    74   public:
 
    74   public:
 
    94 
    94 
    95     
    95     
    96     NodeIt tail(EdgeIt e) const { return edges[e.n].tail; }
 
    96     NodeIt tail(EdgeIt e) const { return edges[e.n].tail; }
 
    97     NodeIt head(EdgeIt e) const { return edges[e.n].head; }
 
    97     NodeIt head(EdgeIt e) const { return edges[e.n].head; }
 
    98 
    98 
    99     NodeIt aNode(const OutEdgeIt& e) const { return tail(e); }
 
    99 //     NodeIt aNode(const OutEdgeIt& e) const { return tail(e); }
 
   100     NodeIt aNode(const InEdgeIt& e) const { return head(e); }
 
   100 //     NodeIt aNode(const InEdgeIt& e) const { return head(e); }
 
   101     //NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); }
 
   101 //     //NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); }
 
   102 
   102 
   103     NodeIt bNode(const OutEdgeIt& e) const { return head(e); }
 
   103 //     NodeIt bNode(const OutEdgeIt& e) const { return head(e); }
 
   104     NodeIt bNode(const InEdgeIt& e) const { return tail(e); }
 
   104 //     NodeIt bNode(const InEdgeIt& e) const { return tail(e); }
 
   105     //NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); }
 
   105 //     //NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); }
 
   106 
   106 
   107     EachNodeIt& getFirst(EachNodeIt& v) const { 
   107     EachNodeIt& getFirst(EachNodeIt& v) const { 
   108       v=EachNodeIt(*this); return v; }
 
   108       v=EachNodeIt(*this); return v; }
 
   109     EachEdgeIt& getFirst(EachEdgeIt& e) const { 
   109     EachEdgeIt& getFirst(EachEdgeIt& e) const { 
   110       e=EachEdgeIt(*this); return e; }
 
   110       e=EachEdgeIt(*this); return e; }
 
   125       It e;
 
   125       It e;
 
   126       getFirst(e, v);
 
   126       getFirst(e, v);
 
   127       return e; 
   127       return e; 
   128     }
 
   128     }
 
   129 
   129 
   130     bool valid(EdgeIt e) const { return e.n!=INVALID_EDGE; }
 
   130     bool valid(EdgeIt e) const { return e.n!=-1; }
 
   131     bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); }
 
   131     //    bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); }
 
   132     bool valid(NodeIt n) const { return n.n<int(nodes.size()); }
 
   132     bool valid(NodeIt n) const { return n.n!=-1; }
 
   133     
   133     
   134     void setInvalid(EdgeIt &e) { e.n=INVALID_EDGE; }
 
   134     void setInvalid(EdgeIt &e) { e.n=-1; }
 
   135     void setInvalid(NodeIt &n) { n.n=INVALID_NODE; }
 
   135     void setInvalid(NodeIt &n) { n.n=-1; }
 
   136     
   136     
   137     template <typename It> It next(It it) const
 
   137     template <typename It> It getNext(It it) const
 
   138       //    { It tmp(it); return goNext(tmp); }
 
   138     { It tmp(it); return next(tmp); }
 
   139     { It tmp; tmp.n=it.n+1; return tmp; }
 
   139     //{ It tmp; tmp.n=it.n+1; return tmp; }
 
   140 
   140 
   141     NodeIt& goNext(NodeIt& it) const { ++it.n; return it; }
 
   141     NodeIt& next(NodeIt& it) const { it.n=(it.n+2)%nodes.size()-1; return it; }
 
   142     OutEdgeIt& goNext(OutEdgeIt& it) const
 
   142     OutEdgeIt& next(OutEdgeIt& it) const
 
   143     { it.n=edges[it.n].next_out; return it; }
 
   143     { it.n=edges[it.n].next_out; return it; }
 
   144     InEdgeIt& goNext(InEdgeIt& it) const
 
   144     InEdgeIt& next(InEdgeIt& it) const
 
   145     { it.n=edges[it.n].next_in; return it; }
 
   145     { it.n=edges[it.n].next_in; return it; }
 
   146     EachEdgeIt& goNext(EachEdgeIt& it) const { ++it.n; return it; }
 
   146     EachEdgeIt& next(EachEdgeIt& it) const { --it.n; return it; }
 
   147 
   147 
   148     int id(NodeIt v) const { return v.n; }
 
   148     int id(NodeIt v) const { return v.n; }
 
   149     int id(EdgeIt e) const { return e.n; }
 
   149     int id(EdgeIt e) const { return e.n; }
 
   150 
   150 
   151     NodeIt addNode() {
 
   151     NodeIt addNode() {
 
   164       edges[e.n].next_out=nodes[u.n].first_out;
 
   164       edges[e.n].next_out=nodes[u.n].first_out;
 
   165       edges[e.n].next_in=nodes[v.n].first_in;
 
   165       edges[e.n].next_in=nodes[v.n].first_in;
 
   166       nodes[u.n].first_out=nodes[v.n].first_in=e.n;
 
   166       nodes[u.n].first_out=nodes[v.n].first_in=e.n;
 
   167 
   167 
   168       for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
 
   168       for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
 
   169 	  i!=dyn_edge_maps.end(); ++i) (**i).add(e.n);
 
   169 	  i!=dyn_edge_maps.end(); ++i) (**i).add(e);
 
   170 
   170 
   171       return e;
 
   171       return e;
 
   172     }
 
   172     }
 
   173 
   173 
   174     void clear() {nodes.clear();edges.clear();}
 
   174     void clear() {nodes.clear();edges.clear();}
 
   184       friend class SymEdgeIt;
 
   184       friend class SymEdgeIt;
 
   185 
   185 
   186     protected:
 
   186     protected:
 
   187       int n;
 
   187       int n;
 
   188       friend int SmartGraph::id(NodeIt v) const; 
   188       friend int SmartGraph::id(NodeIt v) const; 
       
   189       NodeIt(int nn) {n=nn;}
 
   189     public:
 
   190     public:
 
   190       NodeIt() {}
 
   191       NodeIt() {}
 
   191       NodeIt(int nn) {n=nn;}
 
   192       NodeIt (_Invalid i) { n=-1; }
 
   192       bool operator==(const NodeIt i) const {return n==i.n;}
 
   193       bool operator==(const NodeIt i) const {return n==i.n;}
 
   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;}
 
   194     };
 
   196     };
 
   195     
   197     
   196     class EachNodeIt : public NodeIt {
 
   198     class EachNodeIt : public NodeIt {
 
   197       friend class SmartGraph;
 
   199       friend class SmartGraph;
 
   198     public:
 
   200     public:
 
   199       EachNodeIt(const SmartGraph& G) : NodeIt(0) { }
 
   201       EachNodeIt(const SmartGraph& G) : NodeIt(G.nodes.size()?0:-1) { }
 
   200       EachNodeIt() : NodeIt() { }
 
   202       EachNodeIt() : NodeIt() { }
 
   201     };
 
   203     };
 
   202 
   204 
   203     class EdgeIt {
 
   205     class EdgeIt {
 
   204       friend class SmartGraph;
 
   206       friend class SmartGraph;
 
   208       friend class NodeIt;
 
   210       friend class NodeIt;
 
   209       friend class EachNodeIt;
 
   211       friend class EachNodeIt;
 
   210     protected:
 
   212     protected:
 
   211       int n;
 
   213       int n;
 
   212       friend int SmartGraph::id(EdgeIt e) const;
 
   214       friend int SmartGraph::id(EdgeIt e) const;
 
       
   215 
       
   216       EdgeIt(int nn) {n=nn;}
 
   213     public:
 
   217     public:
 
   214       EdgeIt() { }
 
   218       EdgeIt() { }
 
   215       EdgeIt(int nn) {n=nn;}
 
   219       EdgeIt (_Invalid i) { n=-1; }
 
   216       bool operator==(const EdgeIt i) const {return n==i.n;}
 
   220       bool operator==(const EdgeIt i) const {return n==i.n;}
 
   217       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;}
 
   218     };
 
   223     };
 
   219     
   224     
   220     class EachEdgeIt : public EdgeIt {
 
   225     class EachEdgeIt : public EdgeIt {
 
   221       friend class SmartGraph;
 
   226       friend class SmartGraph;
 
   222     public:
 
   227     public:
 
   223       EachEdgeIt(const SmartGraph& G) : EdgeIt(0) { }
 
   228       EachEdgeIt(const SmartGraph& G) : EdgeIt(G.edges.size()-1) { }
 
       
   229       EachEdgeIt (_Invalid i) : EdgeIt(i) { }
 
   224       EachEdgeIt() : EdgeIt() { }
 
   230       EachEdgeIt() : EdgeIt() { }
 
   225     };
 
   231     };
 
   226     
   232     
   227     class OutEdgeIt : public EdgeIt {
 
   233     class OutEdgeIt : public EdgeIt {
 
   228       friend class SmartGraph;
 
   234       friend class SmartGraph;
 
   229     public: 
   235     public: 
   230       OutEdgeIt() : EdgeIt() { }
 
   236       OutEdgeIt() : EdgeIt() { }
 
       
   237       OutEdgeIt (_Invalid i) : EdgeIt(i) { }
 
       
   238 
   231       OutEdgeIt(const SmartGraph& G,const NodeIt v)
 
   239       OutEdgeIt(const SmartGraph& G,const NodeIt v)
 
   232 	: EdgeIt(G.nodes[v.n].first_out) {}
 
   240 	: EdgeIt(G.nodes[v.n].first_out) {}
 
   233     };
 
   241     };
 
   234     
   242     
   235     class InEdgeIt : public EdgeIt {
 
   243     class InEdgeIt : public EdgeIt {
 
   236       friend class SmartGraph;
 
   244       friend class SmartGraph;
 
   237     public: 
   245     public: 
   238       InEdgeIt() : EdgeIt() { }
 
   246       InEdgeIt() : EdgeIt() { }
 
       
   247       InEdgeIt (_Invalid i) : EdgeIt(i) { }
 
   239       InEdgeIt(const SmartGraph& G,NodeIt v) :EdgeIt(G.nodes[v.n].first_in){}
 
   248       InEdgeIt(const SmartGraph& G,NodeIt v) :EdgeIt(G.nodes[v.n].first_in){}
 
   240     };
 
   249     };
 
   241 
   250 
   242     // Map types
 
   251     // Map types
 
   243 
   252 
   283 
   292 
   284     public:
 
   293     public:
 
   285       typedef T ValueType;
 
   294       typedef T ValueType;
 
   286       typedef NodeIt KeyType;
 
   295       typedef NodeIt KeyType;
 
   287 
   296 
   288       DynNodeMap(SmartGraph &_G) :
 
   297       DynNodeMap(const SmartGraph &_G) :
 
   289 	DynMapBase<NodeIt>(_G), container(_G.maxNodeId())
 
   298 	DynMapBase<NodeIt>(_G), container(_G.maxNodeId())
 
   290       {
 
   299       {
 
   291 	//FIXME: What if there are empty Id's?
 
   300 	//FIXME: What if there are empty Id's?
 
   292 	//FIXME: Can I use 'this' in a constructor?
 
   301 	//FIXME: Can I use 'this' in a constructor?
 
   293 	G->dyn_node_maps.push_back(this);
 
   302 	G->dyn_node_maps.push_back(this);
 
   309 
   318 
   310       void add(const NodeIt k) 
   319       void add(const NodeIt k) 
   311       {
 
   320       {
 
   312 	if(k.n>=container.size()) container.resize(k.n+1);
 
   321 	if(k.n>=container.size()) container.resize(k.n+1);
 
   313       }
 
   322       }
 
   314       void erase(const NodeIt k)
 
   323 //       void erase(const NodeIt k)
 
   315       {
 
   324 //       {
 
   316 	//FIXME: Please implement me.
 
   325 // 	//FIXME: Please implement me.
 
   317       }
 
   326 //       }
 
       
   327 //       void erase(const EdgeIt k)
 
       
   328 //       {
 
       
   329 // 	//FIXME: Please implement me.
 
       
   330 //       }
 
   318       
   331       
   319       void set(NodeIt n, T a) { container[n.n]=a; }
 
   332       void set(NodeIt n, T a) { container[n.n]=a; }
 
   320       T get(NodeIt n) const { return container[n.n]; }
 
   333       T get(NodeIt n) const { return container[n.n]; }
 
   321       T& operator[](NodeIt n) { return container[n.n]; }
 
   334       T& operator[](NodeIt n) { return container[n.n]; }
 
   322       const T& operator[](NodeIt n) const { return container[n.n]; }
 
   335       const T& operator[](NodeIt n) const { return container[n.n]; }
 
   331 
   344 
   332     public:
 
   345     public:
 
   333       typedef T ValueType;
 
   346       typedef T ValueType;
 
   334       typedef EdgeIt KeyType;
 
   347       typedef EdgeIt KeyType;
 
   335 
   348 
   336       DynEdgeMap(SmartGraph &_G) :
 
   349       DynEdgeMap(const SmartGraph &_G) :
 
   337 	DynMapBase<EdgeIt>(_G), container(_G.maxEdgeId())
 
   350 	DynMapBase<EdgeIt>(_G), container(_G.maxEdgeId())
 
   338       {
 
   351       {
 
   339 	//FIXME: What if there are empty Id's?
 
   352 	//FIXME: What if there are empty Id's?
 
   340 	//FIXME: Can I use 'this' in a constructor?
 
   353 	//FIXME: Can I use 'this' in a constructor?
 
   341 	G->dyn_edge_maps.push_back(this);
 
   354 	G->dyn_edge_maps.push_back(this);
 
   374     };
 
   387     };
 
   375         
   388         
   376   };
 
   389   };
 
   377 } //namespace hugo
 
   390 } //namespace hugo
 
   378 
   391 
       
   392 
       
   393 
       
   394 
   379 #endif //SMART_GRAPH_H
 
   395 #endif //SMART_GRAPH_H
lemon-0.x