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 169 940b13aba5ff
parent 157 ee17030e5f47
child 174 44700ed9ffaa
equal deleted inserted replaced
8:7b75acf5e367 9:70cb42d2f567 
     4 #define SMART_GRAPH_H
 
     4 #define SMART_GRAPH_H
 
     5 
     5 
     6 #include <vector>
 
     6 #include <vector>
 
     7 #include <limits.h>
 
     7 #include <limits.h>
 
     8 
     8 
     9 struct _Invalid {} Invalid;
 
     9 #include <invalid.h>
 
    10 
    10 
    11 namespace hugo {
 
    11 namespace hugo {
 
    12 
    12 
    13   class SmartGraph {
 
    13   class SmartGraph {
 
    14 
    14 
    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 Node;
 
       
    50     class Edge;
 
       
    51 
       
    52   protected:
 
       
    53     mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
 
       
    54     mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
 
       
    55     
       
    56   public:
 
       
    57 
    49     class NodeIt;
 
    58     class NodeIt;
 
    50     class EdgeIt;
 
    59     class EdgeIt;
 
    51 
       
    52   protected:
 
       
    53     mutable std::vector<DynMapBase<NodeIt> * > dyn_node_maps;
 
       
    54     mutable std::vector<DynMapBase<EdgeIt> * > dyn_edge_maps;
 
       
    55     
       
    56   public:
 
       
    57 
       
    58     class EachNodeIt;
 
       
    59     class EachEdgeIt;
 
       
    60     class OutEdgeIt;
 
    60     class OutEdgeIt;
 
    61     class InEdgeIt;
 
    61     class InEdgeIt;
 
    62     
    62     
    63     //     class NodeIt { int n; };
 
    63     //     class Node { int n; };
 
    64     //     class EachNodeIt : public NodeIt { };
 
    64     //     class NodeIt : public Node { };
 
    65     //     class EdgeIt { int n; };
 
    65     //     class Edge { int n; };
 
    66     //     class EachEdgeIt : public EdgeIt {};
 
    66     //     class EdgeIt : public Edge {};
 
    67     //     class OutEdgeIt : public EdgeIt {};
 
    67     //     class OutEdgeIt : public Edge {};
 
    68     //     class InEdgeIt : public EdgeIt {};
 
    68     //     class InEdgeIt : public Edge {};
 
    69     //     class SymEdgeIt;
 
    69     //     class SymEdge;
 
    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:
 
    78     SmartGraph() : nodes(), edges() { }
 
    78     SmartGraph() : nodes(), edges() { }
 
    79     SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
 
    79     SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
 
    80     
    80     
    81     ~SmartGraph()
 
    81     ~SmartGraph()
 
    82     {
 
    82     {
 
    83       for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();
 
    83       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
 
    84 	  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
 
    84 	  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
 
    85       for(std::vector<DynMapBase<EdgeIt> * >::iterator i=dyn_edge_maps.begin();
 
    85       for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
 
    86 	  i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
 
    86 	  i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
 
    87     }
 
    87     }
 
    88 
    88 
    89     int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
 
    89     int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
 
    90     int edgeNum() const { return edges.size(); }  //FIXME: What is this?
 
    90     int edgeNum() const { return edges.size(); }  //FIXME: What is this?
 
    91 
    91 
    92     int maxNodeId() const { return nodes.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?
 
    93     int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?
 
    94 
    94 
    95     
    95     
    96     NodeIt tail(EdgeIt e) const { return edges[e.n].tail; }
 
    96     Node tail(Edge e) const { return edges[e.n].tail; }
 
    97     NodeIt head(EdgeIt e) const { return edges[e.n].head; }
 
    97     Node head(Edge e) const { return edges[e.n].head; }
 
    98 
    98 
    99 //     NodeIt aNode(const OutEdgeIt& e) const { return tail(e); }
 
    99 //     Node aNode(const OutEdgeIt& e) const { return tail(e); }
 
   100 //     NodeIt aNode(const InEdgeIt& e) const { return head(e); }
 
   100 //     Node aNode(const InEdgeIt& e) const { return head(e); }
 
   101 //     //NodeIt aNode(const SymEdgeIt& e) const { return e.aNode(); }
 
   101 //     //Node aNode(const SymEdge& e) const { return e.aNode(); }
 
   102 
   102 
   103 //     NodeIt bNode(const OutEdgeIt& e) const { return head(e); }
 
   103 //     Node bNode(const OutEdgeIt& e) const { return head(e); }
 
   104 //     NodeIt bNode(const InEdgeIt& e) const { return tail(e); }
 
   104 //     Node bNode(const InEdgeIt& e) const { return tail(e); }
 
   105 //     //NodeIt bNode(const SymEdgeIt& e) const { return e.bNode(); }
 
   105 //     //Node bNode(const SymEdge& e) const { return e.bNode(); }
 
   106 
   106 
   107     EachNodeIt& getFirst(EachNodeIt& v) const { 
   107     NodeIt& first(NodeIt& v) const { 
   108       v=EachNodeIt(*this); return v; }
 
   108       v=NodeIt(*this); return v; }
 
   109     EachEdgeIt& getFirst(EachEdgeIt& e) const { 
   109     EdgeIt& first(EdgeIt& e) const { 
   110       e=EachEdgeIt(*this); return e; }
 
   110       e=EdgeIt(*this); return e; }
 
   111     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt v) const { 
   111     OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 
   112       e=OutEdgeIt(*this,v); return e; }
 
   112       e=OutEdgeIt(*this,v); return e; }
 
   113     InEdgeIt& getFirst(InEdgeIt& e, const NodeIt v) const { 
   113     InEdgeIt& first(InEdgeIt& e, const Node v) const { 
   114       e=InEdgeIt(*this,v); return e; }
 
   114       e=InEdgeIt(*this,v); return e; }
 
   115 
   115 
   116     template< typename It >
 
   116     template< typename It >
 
   117     It first() const { 
   117     It first() const { 
   118       It e;
 
   118       It e;
 
   119       getFirst(e);
 
   119       getFirst(e);
 
   120       return e; 
   120       return e; 
   121     }
 
   121     }
 
   122 
   122 
   123     template< typename It >
 
   123     template< typename It >
 
   124     It first(NodeIt v) const { 
   124     It first(Node v) const { 
   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!=-1; }
 
   130     bool valid(Edge e) const { return e.n!=-1; }
 
   131     //    bool valid(EachEdgeIt e) const { return e.n<int(edges.size()); }
 
   131     //    bool valid(EdgeIt e) const { return e.n<int(edges.size()); }
 
   132     bool valid(NodeIt n) const { return n.n!=-1; }
 
   132     bool valid(Node n) const { return n.n!=-1; }
 
   133     
   133     
   134     void setInvalid(EdgeIt &e) { e.n=-1; }
 
   134     void setInvalid(Edge &e) { e.n=-1; }
 
   135     void setInvalid(NodeIt &n) { n.n=-1; }
 
   135     void setInvalid(Node &n) { n.n=-1; }
 
   136     
   136     
   137     template <typename It> It getNext(It it) const
 
   137     template <typename It> It getNext(It it) const
 
   138     { It tmp(it); return next(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& next(NodeIt& it) const { it.n=(it.n+2)%nodes.size()-1; return it; }
 
   141     Node& next(Node& it) const { it.n=(it.n+2)%nodes.size()-1; return it; }
 
   142     OutEdgeIt& next(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& next(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& next(EachEdgeIt& it) const { --it.n; return it; }
 
   146     EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
 
   147 
   147 
   148     int id(NodeIt v) const { return v.n; }
 
   148     int id(Node v) const { return v.n; }
 
   149     int id(EdgeIt e) const { return e.n; }
 
   149     int id(Edge e) const { return e.n; }
 
   150 
   150 
   151     NodeIt addNode() {
 
   151     Node addNode() {
 
   152       NodeIt n; n.n=nodes.size();
 
   152       Node n; n.n=nodes.size();
 
   153       nodes.push_back(NodeT()); //FIXME: Hmmm...
 
   153       nodes.push_back(NodeT()); //FIXME: Hmmm...
 
   154 
   154 
   155       for(std::vector<DynMapBase<NodeIt> * >::iterator i=dyn_node_maps.begin();
 
   155       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
 
   156 	  i!=dyn_node_maps.end(); ++i) (**i).add(n.n);
 
   156 	  i!=dyn_node_maps.end(); ++i) (**i).add(n.n);
 
   157 
   157 
   158       return n;
 
   158       return n;
 
   159     }
 
   159     }
 
   160     
   160     
   161     EdgeIt addEdge(NodeIt u, NodeIt v) {
 
   161     Edge addEdge(Node u, Node v) {
 
   162       EdgeIt e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
 
   162       Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
 
   163       edges[e.n].tail=u.n; edges[e.n].head=v.n;
 
   163       edges[e.n].tail=u.n; edges[e.n].head=v.n;
 
   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<Edge> * >::iterator i=dyn_edge_maps.begin();
 
   169 	  i!=dyn_edge_maps.end(); ++i) (**i).add(e);
 
   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();}
 
   175 
   175 
   176     class NodeIt {
 
   176     class Node {
 
   177       friend class SmartGraph;
 
   177       friend class SmartGraph;
 
   178       template <typename T> friend class NodeMap;
 
   178       template <typename T> friend class NodeMap;
 
   179       template <typename T> friend class DynNodeMap;
 
   179       template <typename T> friend class DynNodeMap;
 
   180       
   180       
   181       friend class EdgeIt;
 
   181       friend class Edge;
 
   182       friend class OutEdgeIt;
 
   182       friend class OutEdgeIt;
 
   183       friend class InEdgeIt;
 
   183       friend class InEdgeIt;
 
   184       friend class SymEdgeIt;
 
   184       friend class SymEdge;
 
   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(Node v) const; 
   189       NodeIt(int nn) {n=nn;}
 
   189       Node(int nn) {n=nn;}
 
   190     public:
 
   190     public:
 
   191       NodeIt() {}
 
   191       Node() {}
 
   192       NodeIt (_Invalid i) { n=-1; }
 
   192       Node (Invalid i) { n=-1; }
 
   193       bool operator==(const NodeIt i) const {return n==i.n;}
 
   193       bool operator==(const Node i) const {return n==i.n;}
 
   194       bool operator!=(const NodeIt i) const {return n!=i.n;}
 
   194       bool operator!=(const Node i) const {return n!=i.n;}
 
   195       bool operator<(const NodeIt i) const {return n<i.n;}
 
   195       bool operator<(const Node i) const {return n<i.n;}
 
   196     };
 
   196     };
 
   197     
   197     
   198     class EachNodeIt : public NodeIt {
 
   198     class NodeIt : public Node {
 
   199       friend class SmartGraph;
 
   199       friend class SmartGraph;
 
   200     public:
 
   200     public:
 
   201       EachNodeIt(const SmartGraph& G) : NodeIt(G.nodes.size()?0:-1) { }
 
   201       NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
 
   202       EachNodeIt() : NodeIt() { }
 
   202       NodeIt() : Node() { }
 
   203     };
 
   203     };
 
   204 
   204 
   205     class EdgeIt {
 
   205     class Edge {
 
   206       friend class SmartGraph;
 
   206       friend class SmartGraph;
 
   207       template <typename T> friend class EdgeMap;
 
   207       template <typename T> friend class EdgeMap;
 
   208       template <typename T> friend class DynEdgeMap;
 
   208       template <typename T> friend class DynEdgeMap;
 
   209       
   209       
       
   210       friend class Node;
 
   210       friend class NodeIt;
 
   211       friend class NodeIt;
 
   211       friend class EachNodeIt;
 
       
   212     protected:
 
   212     protected:
 
   213       int n;
 
   213       int n;
 
   214       friend int SmartGraph::id(EdgeIt e) const;
 
   214       friend int SmartGraph::id(Edge e) const;
 
   215 
   215 
   216       EdgeIt(int nn) {n=nn;}
 
   216       Edge(int nn) {n=nn;}
 
   217     public:
 
   217     public:
 
   218       EdgeIt() { }
 
   218       Edge() { }
 
   219       EdgeIt (_Invalid i) { n=-1; }
 
   219       Edge (Invalid i) { n=-1; }
 
   220       bool operator==(const EdgeIt i) const {return n==i.n;}
 
   220       bool operator==(const Edge i) const {return n==i.n;}
 
   221       bool operator!=(const EdgeIt i) const {return n!=i.n;}
 
   221       bool operator!=(const Edge i) const {return n!=i.n;}
 
   222       bool operator<(const EdgeIt i) const {return n<i.n;}
 
   222       bool operator<(const Edge i) const {return n<i.n;}
 
   223     };
 
   223     };
 
   224     
   224     
   225     class EachEdgeIt : public EdgeIt {
 
   225     class EdgeIt : public Edge {
 
   226       friend class SmartGraph;
 
   226       friend class SmartGraph;
 
   227     public:
 
   227     public:
 
   228       EachEdgeIt(const SmartGraph& G) : EdgeIt(G.edges.size()-1) { }
 
   228       EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
 
   229       EachEdgeIt (_Invalid i) : EdgeIt(i) { }
 
   229       EdgeIt (Invalid i) : Edge(i) { }
 
   230       EachEdgeIt() : EdgeIt() { }
 
   230       EdgeIt() : Edge() { }
 
   231     };
 
   231     };
 
   232     
   232     
   233     class OutEdgeIt : public EdgeIt {
 
   233     class OutEdgeIt : public Edge {
 
   234       friend class SmartGraph;
 
   234       friend class SmartGraph;
 
   235     public: 
   235     public: 
   236       OutEdgeIt() : EdgeIt() { }
 
   236       OutEdgeIt() : Edge() { }
 
   237       OutEdgeIt (_Invalid i) : EdgeIt(i) { }
 
   237       OutEdgeIt (Invalid i) : Edge(i) { }
 
   238 
   238 
   239       OutEdgeIt(const SmartGraph& G,const NodeIt v)
 
   239       OutEdgeIt(const SmartGraph& G,const Node v)
 
   240 	: EdgeIt(G.nodes[v.n].first_out) {}
 
   240 	: Edge(G.nodes[v.n].first_out) {}
 
   241     };
 
   241     };
 
   242     
   242     
   243     class InEdgeIt : public EdgeIt {
 
   243     class InEdgeIt : public Edge {
 
   244       friend class SmartGraph;
 
   244       friend class SmartGraph;
 
   245     public: 
   245     public: 
   246       InEdgeIt() : EdgeIt() { }
 
   246       InEdgeIt() : Edge() { }
 
   247       InEdgeIt (_Invalid i) : EdgeIt(i) { }
 
   247       InEdgeIt (Invalid i) : Edge(i) { }
 
   248       InEdgeIt(const SmartGraph& G,NodeIt v) :EdgeIt(G.nodes[v.n].first_in){}
 
   248       InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
 
   249     };
 
   249     };
 
   250 
   250 
   251     // Map types
 
   251     // Map types
 
   252 
   252 
   253     template <typename T>
 
   253     template <typename T>
 
   254     class NodeMap {
 
   254     class NodeMap {
 
   255       const SmartGraph& G; 
   255       const SmartGraph& G; 
   256       std::vector<T> container;
 
   256       std::vector<T> container;
 
   257     public:
 
   257     public:
 
   258       typedef T ValueType;
 
   258       typedef T ValueType;
 
   259       typedef NodeIt KeyType;
 
   259       typedef Node KeyType;
 
   260       NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }
 
   260       NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }
 
   261       NodeMap(const SmartGraph& _G, T a) : 
   261       NodeMap(const SmartGraph& _G, T a) : 
   262 	G(_G), container(G.maxNodeId(), a) { }
 
   262 	G(_G), container(G.maxNodeId(), a) { }
 
   263       void set(NodeIt n, T a) { container[n.n]=a; }
 
   263       void set(Node n, T a) { container[n.n]=a; }
 
   264       T get(NodeIt n) const { return container[n.n]; }
 
   264       T get(Node n) const { return container[n.n]; }
 
   265       T& operator[](NodeIt n) { return container[n.n]; }
 
   265       T& operator[](Node n) { return container[n.n]; }
 
   266       const T& operator[](NodeIt n) const { return container[n.n]; }
 
   266       const T& operator[](Node n) const { return container[n.n]; }
 
   267       void update() { container.resize(G.maxNodeId()); }
 
   267       void update() { container.resize(G.maxNodeId()); }
 
   268       void update(T a) { container.resize(G.maxNodeId(), a); }
 
   268       void update(T a) { container.resize(G.maxNodeId(), a); }
 
   269     };
 
   269     };
 
   270 
   270 
   271     template <typename T>
 
   271     template <typename T>
 
   272     class EdgeMap {
 
   272     class EdgeMap {
 
   273       const SmartGraph& G; 
   273       const SmartGraph& G; 
   274       std::vector<T> container;
 
   274       std::vector<T> container;
 
   275     public:
 
   275     public:
 
   276       typedef T ValueType;
 
   276       typedef T ValueType;
 
   277       typedef EdgeIt KeyType;
 
   277       typedef Edge KeyType;
 
   278       EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }
 
   278       EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }
 
   279       EdgeMap(const SmartGraph& _G, T a) : 
   279       EdgeMap(const SmartGraph& _G, T a) : 
   280 	G(_G), container(G.maxEdgeId(), a) { }
 
   280 	G(_G), container(G.maxEdgeId(), a) { }
 
   281       void set(EdgeIt e, T a) { container[e.n]=a; }
 
   281       void set(Edge e, T a) { container[e.n]=a; }
 
   282       T get(EdgeIt e) const { return container[e.n]; }
 
   282       T get(Edge e) const { return container[e.n]; }
 
   283       T& operator[](EdgeIt e) { return container[e.n]; } 
   283       T& operator[](Edge e) { return container[e.n]; } 
   284       const T& operator[](EdgeIt e) const { return container[e.n]; } 
   284       const T& operator[](Edge e) const { return container[e.n]; } 
   285       void update() { container.resize(G.maxEdgeId()); }
 
   285       void update() { container.resize(G.maxEdgeId()); }
 
   286       void update(T a) { container.resize(G.maxEdgeId(), a); }
 
   286       void update(T a) { container.resize(G.maxEdgeId(), a); }
 
   287     };
 
   287     };
 
   288 
   288 
   289     template <typename T> class DynNodeMap : public DynMapBase<NodeIt>
 
   289     template <typename T> class DynNodeMap : public DynMapBase<Node>
 
   290     {
 
   290     {
 
   291       std::vector<T> container;
 
   291       std::vector<T> container;
 
   292 
   292 
   293     public:
 
   293     public:
 
   294       typedef T ValueType;
 
   294       typedef T ValueType;
 
   295       typedef NodeIt KeyType;
 
   295       typedef Node KeyType;
 
   296 
   296 
   297       DynNodeMap(const SmartGraph &_G) :
 
   297       DynNodeMap(const SmartGraph &_G) :
 
   298 	DynMapBase<NodeIt>(_G), container(_G.maxNodeId())
 
   298 	DynMapBase<Node>(_G), container(_G.maxNodeId())
 
   299       {
 
   299       {
 
   300 	//FIXME: What if there are empty Id's?
 
   300 	//FIXME: What if there are empty Id's?
 
   301 	//FIXME: Can I use 'this' in a constructor?
 
   301 	//FIXME: Can I use 'this' in a constructor?
 
   302 	G->dyn_node_maps.push_back(this);
 
   302 	G->dyn_node_maps.push_back(this);
 
   303       }
 
   303       }
 
   304       ~DynNodeMap()
 
   304       ~DynNodeMap()
 
   305       {
 
   305       {
 
   306 	if(G) {
 
   306 	if(G) {
 
   307 	  std::vector<DynMapBase<NodeIt>* >::iterator i;
 
   307 	  std::vector<DynMapBase<Node>* >::iterator i;
 
   308 	  for(i=G->dyn_node_maps.begin();
 
   308 	  for(i=G->dyn_node_maps.begin();
 
   309 	      i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
 
   309 	      i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
 
   310 	  //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
 
   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?)
 
   311 	  //A better way to do that: (Is this really important?)
 
   312 	  if(*i==this) {
 
   312 	  if(*i==this) {
 
   314 	    G->dyn_node_maps.pop_back();
 
   314 	    G->dyn_node_maps.pop_back();
 
   315 	  }
 
   315 	  }
 
   316 	}
 
   316 	}
 
   317       }
 
   317       }
 
   318 
   318 
   319       void add(const NodeIt k) 
   319       void add(const Node k) 
   320       {
 
   320       {
 
   321 	if(k.n>=container.size()) container.resize(k.n+1);
 
   321 	if(k.n>=container.size()) container.resize(k.n+1);
 
   322       }
 
   322       }
 
   323 //       void erase(const NodeIt k)
 
   323 //       void erase(const Node k)
 
   324 //       {
 
   324 //       {
 
   325 // 	//FIXME: Please implement me.
 
   325 // 	//FIXME: Please implement me.
 
   326 //       }
 
   326 //       }
 
   327 //       void erase(const EdgeIt k)
 
   327 //       void erase(const Edge k)
 
   328 //       {
 
   328 //       {
 
   329 // 	//FIXME: Please implement me.
 
   329 // 	//FIXME: Please implement me.
 
   330 //       }
 
   330 //       }
 
   331       
   331       
   332       void set(NodeIt n, T a) { container[n.n]=a; }
 
   332       void set(Node n, T a) { container[n.n]=a; }
 
   333       T get(NodeIt n) const { return container[n.n]; }
 
   333       T get(Node n) const { return container[n.n]; }
 
   334       T& operator[](NodeIt n) { return container[n.n]; }
 
   334       T& operator[](Node n) { return container[n.n]; }
 
   335       const T& operator[](NodeIt n) const { return container[n.n]; }
 
   335       const T& operator[](Node n) const { return container[n.n]; }
 
   336 
   336 
   337       void update() {}    //Useless for DynMaps
 
   337       void update() {}    //Useless for DynMaps
 
   338       void update(T a) {}  //Useless for DynMaps
 
   338       void update(T a) {}  //Useless for DynMaps
 
   339     };
 
   339     };
 
   340     
   340     
   341     template <typename T> class DynEdgeMap : public DynMapBase<EdgeIt>
 
   341     template <typename T> class DynEdgeMap : public DynMapBase<Edge>
 
   342     {
 
   342     {
 
   343       std::vector<T> container;
 
   343       std::vector<T> container;
 
   344 
   344 
   345     public:
 
   345     public:
 
   346       typedef T ValueType;
 
   346       typedef T ValueType;
 
   347       typedef EdgeIt KeyType;
 
   347       typedef Edge KeyType;
 
   348 
   348 
   349       DynEdgeMap(const SmartGraph &_G) :
 
   349       DynEdgeMap(const SmartGraph &_G) :
 
   350 	DynMapBase<EdgeIt>(_G), container(_G.maxEdgeId())
 
   350 	DynMapBase<Edge>(_G), container(_G.maxEdgeId())
 
   351       {
 
   351       {
 
   352 	//FIXME: What if there are empty Id's?
 
   352 	//FIXME: What if there are empty Id's?
 
   353 	//FIXME: Can I use 'this' in a constructor?
 
   353 	//FIXME: Can I use 'this' in a constructor?
 
   354 	G->dyn_edge_maps.push_back(this);
 
   354 	G->dyn_edge_maps.push_back(this);
 
   355       }
 
   355       }
 
   356       ~DynEdgeMap()
 
   356       ~DynEdgeMap()
 
   357       {
 
   357       {
 
   358 	if(G) {
 
   358 	if(G) {
 
   359 	  std::vector<DynMapBase<EdgeIt>* >::iterator i;
 
   359 	  std::vector<DynMapBase<Edge>* >::iterator i;
 
   360 	  for(i=G->dyn_edge_maps.begin();
 
   360 	  for(i=G->dyn_edge_maps.begin();
 
   361 	      i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
 
   361 	      i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
 
   362 	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
 
   362 	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
 
   363 	  //A better way to do that: (Is this really important?)
 
   363 	  //A better way to do that: (Is this really important?)
 
   364 	  if(*i==this) {
 
   364 	  if(*i==this) {
 
   366 	    G->dyn_edge_maps.pop_back();
 
   366 	    G->dyn_edge_maps.pop_back();
 
   367 	  }
 
   367 	  }
 
   368 	}
 
   368 	}
 
   369       }
 
   369       }
 
   370       
   370       
   371       void add(const EdgeIt k) 
   371       void add(const Edge k) 
   372       {
 
   372       {
 
   373 	if(k.n>=int(container.size())) container.resize(k.n+1);
 
   373 	if(k.n>=int(container.size())) container.resize(k.n+1);
 
   374       }
 
   374       }
 
   375       void erase(const EdgeIt k)
 
   375       void erase(const Edge k)
 
   376       {
 
   376       {
 
   377 	//FIXME: Please implement me.
 
   377 	//FIXME: Please implement me.
 
   378       }
 
   378       }
 
   379       
   379       
   380       void set(EdgeIt n, T a) { container[n.n]=a; }
 
   380       void set(Edge n, T a) { container[n.n]=a; }
 
   381       T get(EdgeIt n) const { return container[n.n]; }
 
   381       T get(Edge n) const { return container[n.n]; }
 
   382       T& operator[](EdgeIt n) { return container[n.n]; }
 
   382       T& operator[](Edge n) { return container[n.n]; }
 
   383       const T& operator[](EdgeIt n) const { return container[n.n]; }
 
   383       const T& operator[](Edge n) const { return container[n.n]; }
 
   384 
   384 
   385       void update() {}    //Useless for DynMaps
 
   385       void update() {}    //Useless for DynMaps
 
   386       void update(T a) {}  //Useless for DynMaps
 
   386       void update(T a) {}  //Useless for DynMaps
 
   387     };
 
   387     };
 
   388         
   388
lemon-0.x