Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/hugo/smart_graph.h
changeset 792 147eb3a58706
parent 774 4297098d9677
child 798 6d1abeb62dd3
equal deleted inserted replaced
8:006e6696a1fe 9:2d81cfa10d0a 
     6 ///\ingroup graphs
 
     6 ///\ingroup graphs
 
     7 ///\file
 
     7 ///\file
 
     8 ///\brief SmartGraph and SymSmartGraph classes.
 
     8 ///\brief SmartGraph and SymSmartGraph classes.
 
     9 
     9 
    10 #include <vector>
 
    10 #include <vector>
 
    11 #include <limits.h>
 
    11 #include <climits>
 
    12 
    12 
    13 #include <hugo/invalid.h>
 
    13 #include <hugo/invalid.h>
 
       
    14 
       
    15 #include <hugo/array_map_factory.h>
 
       
    16 #include <hugo/sym_map_factory.h>
 
       
    17 #include <hugo/map_registry.h>
 
       
    18 
       
    19 #include <hugo/map_defines.h>
 
    14 
    20 
    15 namespace hugo {
 
    21 namespace hugo {
 
    16 
    22 
    17 /// \addtogroup graphs
 
    23 /// \addtogroup graphs
 
    18 /// @{
 
    24 /// @{
 
    19   class SymSmartGraph;
 
    25 //  class SymSmartGraph;
 
    20 
    26 
    21   ///A smart graph class.
 
    27   ///A smart graph class.
 
    22 
    28 
    23   ///This is a simple and fast graph implementation.
 
    29   ///This is a simple and fast graph implementation.
 
    24   ///It is also quite memory efficient, but at the price
 
    30   ///It is also quite memory efficient, but at the price
 
    51 
    57 
    52     std::vector<NodeT> nodes;
 
    58     std::vector<NodeT> nodes;
 
    53 
    59 
    54     std::vector<EdgeT> edges;
 
    60     std::vector<EdgeT> edges;
 
    55     
    61     
    56     protected:
 
       
    57     
       
    58     template <typename Key> class DynMapBase
 
       
    59     {
 
       
    60     protected:
 
       
    61       const SmartGraph* G; 
       
    62     public:
 
       
    63       virtual void add(const Key k) = 0;
 
       
    64       virtual void erase(const Key k) = 0;
 
       
    65       DynMapBase(const SmartGraph &_G) : G(&_G) {}
 
       
    66       virtual ~DynMapBase() {}
 
       
    67       friend class SmartGraph;
 
       
    68     };
 
       
    69     
    62     
    70   public:
 
    63   public:
 
    71     template <typename T> class EdgeMap;
 
    64 
    72     template <typename T> class NodeMap;
 
    65     typedef SmartGraph Graph;
 
    73 
    66 
    74     class Node;
 
    67     class Node;
 
    75     class Edge;
 
    68     class Edge;
 
    76 
       
    77     //  protected:
 
       
    78     // HELPME:
 
       
    79   protected:
 
       
    80     ///\bug It must be public because of SymEdgeMap.
 
       
    81     ///
 
       
    82     mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
 
       
    83     ///\bug It must be public because of SymEdgeMap.
 
       
    84     ///
 
       
    85     mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
 
       
    86     
       
    87   public:
 
       
    88 
       
    89 
    69 
    90     class NodeIt;
 
    70     class NodeIt;
 
    91     class EdgeIt;
 
    71     class EdgeIt;
 
    92     class OutEdgeIt;
 
    72     class OutEdgeIt;
 
    93     class InEdgeIt;
 
    73     class InEdgeIt;
 
    94     
    74     
    95     template <typename T> class NodeMap;
 
    75     CREATE_MAP_REGISTRIES;
 
    96     template <typename T> class EdgeMap;
 
    76     CREATE_MAPS(ArrayMapFactory);
 
    97     
    77     
    98   public:
 
    78   public:
 
    99 
    79 
   100     SmartGraph() : nodes(), edges() { }
 
    80     SmartGraph() : nodes(), edges() { }
 
   101     SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
 
    81     SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
 
   102     
    82     
   103     ~SmartGraph()
 
       
   104     {
 
       
   105       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
 
       
   106 	  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
 
       
   107       for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
 
       
   108 	  i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
 
       
   109     }
 
       
   110 
       
   111     int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
 
    83     int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
 
   112     int edgeNum() const { return edges.size(); }  //FIXME: What is this?
 
    84     int edgeNum() const { return edges.size(); }  //FIXME: What is this?
 
   113 
    85 
   114     ///\bug This function does something different than
 
    86     ///\bug This function does something different than
 
   115     ///its name would suggests...
 
    87     ///its name would suggests...
 
   135 
   107 
   136     Node addNode() {
 
   108     Node addNode() {
 
   137       Node n; n.n=nodes.size();
 
   109       Node n; n.n=nodes.size();
 
   138       nodes.push_back(NodeT()); //FIXME: Hmmm...
 
   110       nodes.push_back(NodeT()); //FIXME: Hmmm...
 
   139 
   111 
   140       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
 
   112       
   141 	  i!=dyn_node_maps.end(); ++i) (**i).add(n);
 
   113       node_maps.add(n);
 
   142 
       
   143       return n;
 
   114       return n;
 
   144     }
 
   115     }
 
   145     
   116     
   146     Edge addEdge(Node u, Node v) {
 
   117     Edge addEdge(Node u, Node v) {
 
   147       Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
 
   118       Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
 
   148       edges[e.n].tail=u.n; edges[e.n].head=v.n;
 
   119       edges[e.n].tail=u.n; edges[e.n].head=v.n;
 
   149       edges[e.n].next_out=nodes[u.n].first_out;
 
   120       edges[e.n].next_out=nodes[u.n].first_out;
 
   150       edges[e.n].next_in=nodes[v.n].first_in;
 
   121       edges[e.n].next_in=nodes[v.n].first_in;
 
   151       nodes[u.n].first_out=nodes[v.n].first_in=e.n;
 
   122       nodes[u.n].first_out=nodes[v.n].first_in=e.n;
 
   152 
   123 
   153       for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
 
   124       edge_maps.add(e);
 
   154 	  i!=dyn_edge_maps.end(); ++i) (**i).add(e);
 
       
   155 
   125 
   156       return e;
 
   126       return e;
 
   157     }
 
   127     }
 
   158 
   128 
   159     /// Finds an edge between two nodes.
 
   129     /// Finds an edge between two nodes.
 
   170       while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;
 
   140       while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;
 
   171       prev.n=e;
 
   141       prev.n=e;
 
   172       return prev;
 
   142       return prev;
 
   173     }
 
   143     }
 
   174     
   144     
   175     void clear() {nodes.clear();edges.clear();}
 
   145     void clear() {
 
       
   146       edge_maps.clear();
 
       
   147       edges.clear();
 
       
   148       node_maps.clear();
 
       
   149       nodes.clear();
 
       
   150     }
 
   176 
   151 
   177     class Node {
 
   152     class Node {
 
   178       friend class SmartGraph;
 
   153       friend class SmartGraph;
 
   179       template <typename T> friend class NodeMap;
 
   154       template <typename T> friend class NodeMap;
 
   180       
   155       
   286       InEdgeIt(const SmartGraph& _G,Node v)
 
   261       InEdgeIt(const SmartGraph& _G,Node v)
 
   287 	: Edge(_G.nodes[v.n].first_in), G(&_G) { }
 
   262 	: Edge(_G.nodes[v.n].first_in), G(&_G) { }
 
   288       InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
 
   263       InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
 
   289 //       ///Validity check
 
   264 //       ///Validity check
 
   290 //       operator bool() { return Edge::operator bool(); }      
   265 //       operator bool() { return Edge::operator bool(); }      
   291     };
 
       
   292 
       
   293     template <typename T> class NodeMap : public DynMapBase<Node>
 
       
   294     {
 
       
   295       std::vector<T> container;
 
       
   296 
       
   297     public:
 
       
   298       typedef T ValueType;
 
       
   299       typedef Node KeyType;
 
       
   300 
       
   301       NodeMap(const SmartGraph &_G) :
 
       
   302 	DynMapBase<Node>(_G), container(_G.maxNodeId())
 
       
   303       {
 
       
   304 	G->dyn_node_maps.push_back(this);
 
       
   305       }
 
       
   306       NodeMap(const SmartGraph &_G,const T &t) :
 
       
   307 	DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
 
       
   308       {
 
       
   309 	G->dyn_node_maps.push_back(this);
 
       
   310       }
 
       
   311       
       
   312       NodeMap(const NodeMap<T> &m) :
 
       
   313  	DynMapBase<Node>(*m.G), container(m.container)
 
       
   314       {
 
       
   315  	G->dyn_node_maps.push_back(this);
 
       
   316       }
 
       
   317 
       
   318       template<typename TT> friend class NodeMap;
 
       
   319  
       
   320       ///\todo It can copy between different types.
 
       
   321       ///\todo We could use 'copy'
 
       
   322       template<typename TT> NodeMap(const NodeMap<TT> &m) :
 
       
   323 	DynMapBase<Node>(*m.G), container(m.container.size())
 
       
   324       {
 
       
   325 	G->dyn_node_maps.push_back(this);
 
       
   326 	typename std::vector<TT>::const_iterator i;
 
       
   327 	for(typename std::vector<TT>::const_iterator i=m.container.begin();
 
       
   328 	    i!=m.container.end();
 
       
   329 	    i++)
 
       
   330 	  container.push_back(*i);
 
       
   331       }
 
       
   332       ~NodeMap()
 
       
   333       {
 
       
   334 	if(G) {
 
       
   335 	  std::vector<DynMapBase<Node>* >::iterator i;
 
       
   336 	  for(i=G->dyn_node_maps.begin();
 
       
   337 	      i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
 
       
   338 	  //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
 
       
   339 	  //A better way to do that: (Is this really important?)
 
       
   340 	  if(*i==this) {
 
       
   341 	    *i=G->dyn_node_maps.back();
 
       
   342 	    G->dyn_node_maps.pop_back();
 
       
   343 	  }
 
       
   344 	}
 
       
   345       }
 
       
   346 
       
   347       void add(const Node k) 
       
   348       {
 
       
   349 	if(k.n>=int(container.size())) container.resize(k.n+1);
 
       
   350       }
 
       
   351 
       
   352       void erase(const Node) { }
 
       
   353       
       
   354       void set(Node n, T a) { container[n.n]=a; }
 
       
   355       //'T& operator[](Node n)' would be wrong here
 
       
   356       typename std::vector<T>::reference
 
       
   357       operator[](Node n) { return container[n.n]; }
 
       
   358       //'const T& operator[](Node n)' would be wrong here
 
       
   359       typename std::vector<T>::const_reference 
       
   360       operator[](Node n) const { return container[n.n]; }
 
       
   361 
       
   362       ///\warning There is no safety check at all!
 
       
   363       ///Using operator = between maps attached to different graph may
 
       
   364       ///cause serious problem.
 
       
   365       ///\todo Is this really so?
 
       
   366       ///\todo It can copy between different types.
 
       
   367       const NodeMap<T>& operator=(const NodeMap<T> &m)
 
       
   368       {
 
       
   369 	container = m.container;
 
       
   370 	return *this;
 
       
   371       }
 
       
   372       template<typename TT>
 
       
   373       const NodeMap<T>& operator=(const NodeMap<TT> &m)
 
       
   374       {
 
       
   375 	std::copy(m.container.begin(), m.container.end(), container.begin());
 
       
   376 	return *this;
 
       
   377       }
 
       
   378       
       
   379       void update() {}    //Useless for Dynamic Maps
 
       
   380       void update(T a) {}  //Useless for Dynamic Maps
 
       
   381     };
 
       
   382     
       
   383     template <typename T> class EdgeMap : public DynMapBase<Edge>
 
       
   384     {
 
       
   385       std::vector<T> container;
 
       
   386 
       
   387     public:
 
       
   388       typedef T ValueType;
 
       
   389       typedef Edge KeyType;
 
       
   390 
       
   391       EdgeMap(const SmartGraph &_G) :
 
       
   392 	DynMapBase<Edge>(_G), container(_G.maxEdgeId())
 
       
   393       {
 
       
   394 	//FIXME: What if there are empty Id's?
 
       
   395 	//FIXME: Can I use 'this' in a constructor?
 
       
   396 	G->dyn_edge_maps.push_back(this);
 
       
   397       }
 
       
   398       EdgeMap(const SmartGraph &_G,const T &t) :
 
       
   399 	DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
 
       
   400       {
 
       
   401 	G->dyn_edge_maps.push_back(this);
 
       
   402       } 
       
   403       EdgeMap(const EdgeMap<T> &m) :
 
       
   404  	DynMapBase<Edge>(*m.G), container(m.container)
 
       
   405       {
 
       
   406  	G->dyn_edge_maps.push_back(this);
 
       
   407       }
 
       
   408 
       
   409       template<typename TT> friend class EdgeMap;
 
       
   410 
       
   411       ///\todo It can copy between different types.
 
       
   412       template<typename TT> EdgeMap(const EdgeMap<TT> &m)
 
       
   413 	: DynMapBase<Edge>(*m.G), container(m.container.size())
 
       
   414       {
 
       
   415 	G->dyn_edge_maps.push_back(this);
 
       
   416 	typename std::vector<TT>::const_iterator i;
 
       
   417 	for(typename std::vector<TT>::const_iterator i=m.container.begin();
 
       
   418 	    i!=m.container.end();
 
       
   419 	    i++)
 
       
   420 	  container.push_back(*i);
 
       
   421       }
 
       
   422       ~EdgeMap()
 
       
   423       {
 
       
   424 	if(G) {
 
       
   425 	  std::vector<DynMapBase<Edge>* >::iterator i;
 
       
   426 	  for(i=G->dyn_edge_maps.begin();
 
       
   427 	      i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
 
       
   428 	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
 
       
   429 	  //A better way to do that: (Is this really important?)
 
       
   430 	  if(*i==this) {
 
       
   431 	    *i=G->dyn_edge_maps.back();
 
       
   432 	    G->dyn_edge_maps.pop_back();
 
       
   433 	  }
 
       
   434 	}
 
       
   435       }
 
       
   436       
       
   437       void add(const Edge k) 
       
   438       {
 
       
   439 	if(k.n>=int(container.size())) container.resize(k.n+1);
 
       
   440       }
 
       
   441       void erase(const Edge) { }
 
       
   442       
       
   443       void set(Edge n, T a) { container[n.n]=a; }
 
       
   444       //T get(Edge n) const { return container[n.n]; }
 
       
   445       typename std::vector<T>::reference
 
       
   446       operator[](Edge n) { return container[n.n]; }
 
       
   447       typename std::vector<T>::const_reference
 
       
   448       operator[](Edge n) const { return container[n.n]; }
 
       
   449 
       
   450       ///\warning There is no safety check at all!
 
       
   451       ///Using operator = between maps attached to different graph may
 
       
   452       ///cause serious problem.
 
       
   453       ///\todo Is this really so?
 
       
   454       ///\todo It can copy between different types.
 
       
   455       const EdgeMap<T>& operator=(const EdgeMap<T> &m)
 
       
   456       {
 
       
   457 	container = m.container;
 
       
   458 	return *this;
 
       
   459       }
 
       
   460       template<typename TT>
 
       
   461       const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
 
       
   462       {
 
       
   463 	std::copy(m.container.begin(), m.container.end(), container.begin());
 
       
   464 	return *this;
 
       
   465       }
 
       
   466       
       
   467       void update() {}    //Useless for DynMaps
 
       
   468       void update(T a) {}  //Useless for DynMaps
 
       
   469     };
 
   266     };
 
   470 
   267 
   471   };
 
   268   };
 
   472 
   269 
   473   ///Graph for bidirectional edges.
 
   270   ///Graph for bidirectional edges.
 
   491   //\sa \ref SmartGraph.
 
   288   //\sa \ref SmartGraph.
 
   492 
   289 
   493   class SymSmartGraph : public SmartGraph
 
   290   class SymSmartGraph : public SmartGraph
 
   494   {
 
   291   {
 
   495   public:
 
   292   public:
 
   496     template<typename T> class SymEdgeMap;
 
   293     typedef SymSmartGraph Graph;
 
   497     template<typename T> friend class SymEdgeMap;
 
   294 
       
   295     KEEP_NODE_MAP(SmartGraph);
 
       
   296     KEEP_EDGE_MAP(SmartGraph);
 
       
   297 
       
   298     CREATE_SYM_EDGE_MAP_REGISTRY;
 
       
   299     CREATE_SYM_EDGE_MAP_FACTORY(ArrayMapFactory);
 
       
   300     IMPORT_SYM_EDGE_MAP(SymEdgeMapFactory);
 
   498 
   301 
   499     SymSmartGraph() : SmartGraph() { }
 
   302     SymSmartGraph() : SmartGraph() { }
 
   500     SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
 
   303     SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
 
   501     ///Adds a pair of oppositely directed edges to the graph.
 
   304     ///Adds a pair of oppositely directed edges to the graph.
 
   502     Edge addEdge(Node u, Node v)
 
   305     Edge addEdge(Node u, Node v)
 
   515       Edge f;
 
   318       Edge f;
 
   516       f.idref() = e.idref() - 2*(e.idref()%2) + 1;
 
   319       f.idref() = e.idref() - 2*(e.idref()%2) + 1;
 
   517       return f;
 
   320       return f;
 
   518     }
 
   321     }
 
   519     
   322     
   520     ///Common data storage for the edge pairs.
 
       
   521 
       
   522     ///This map makes it possible to store data shared by the oppositely
 
       
   523     ///directed pairs of edges.
 
       
   524     template <typename T> class SymEdgeMap : public DynMapBase<Edge>
 
       
   525     {
 
       
   526       std::vector<T> container;
 
       
   527       
       
   528     public:
 
       
   529       typedef T ValueType;
 
       
   530       typedef Edge KeyType;
 
       
   531 
       
   532       SymEdgeMap(const SymSmartGraph &_G) :
 
       
   533 	DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
 
       
   534       {
 
       
   535 	static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);
 
       
   536       }
 
       
   537       SymEdgeMap(const SymSmartGraph &_G,const T &t) :
 
       
   538 	DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
 
       
   539       {
 
       
   540 	G->dyn_edge_maps.push_back(this);
 
       
   541       }
 
       
   542 
       
   543       SymEdgeMap(const SymEdgeMap<T> &m) :
 
       
   544  	DynMapBase<SymEdge>(*m.G), container(m.container)
 
       
   545       {
 
       
   546  	G->dyn_node_maps.push_back(this);
 
       
   547       }
 
       
   548 
       
   549       //      template<typename TT> friend class SymEdgeMap;
 
       
   550 
       
   551       ///\todo It can copy between different types.
 
       
   552       ///
 
       
   553 
       
   554       template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m)
 
       
   555 	: DynMapBase<SymEdge>(*m.G), container(m.container.size())
 
       
   556       {
 
       
   557 	G->dyn_node_maps.push_back(this);
 
       
   558 	typename std::vector<TT>::const_iterator i;
 
       
   559 	for(typename std::vector<TT>::const_iterator i=m.container.begin();
 
       
   560 	    i!=m.container.end();
 
       
   561 	    i++)
 
       
   562 	  container.push_back(*i);
 
       
   563       }
 
       
   564  
       
   565       ~SymEdgeMap()
 
       
   566       {
 
       
   567 	if(G) {
 
       
   568 	  std::vector<DynMapBase<Edge>* >::iterator i;
 
       
   569 	  for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
 
       
   570 	      i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
 
       
   571 		&& *i!=this; ++i) ;
 
       
   572 	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
 
       
   573 	  //A better way to do that: (Is this really important?)
 
       
   574 	  if(*i==this) {
 
       
   575 	    *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();
 
       
   576 	    static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
 
       
   577 	  }
 
       
   578 	}
 
       
   579       }
 
       
   580       
       
   581       void add(const Edge k) 
       
   582       {
 
       
   583 	if(!k.idref()%2&&k.idref()/2>=int(container.size()))
 
       
   584 	  container.resize(k.idref()/2+1);
 
       
   585       }
 
       
   586       void erase(const Edge k) { }
 
       
   587       
       
   588       void set(Edge n, T a) { container[n.idref()/2]=a; }
 
       
   589       //T get(Edge n) const { return container[n.idref()/2]; }
 
       
   590       typename std::vector<T>::reference
 
       
   591       operator[](Edge n) { return container[n.idref()/2]; }
 
       
   592       typename std::vector<T>::const_reference
 
       
   593       operator[](Edge n) const { return container[n.idref()/2]; }
 
       
   594 
       
   595       ///\warning There is no safety check at all!
 
       
   596       ///Using operator = between maps attached to different graph may
 
       
   597       ///cause serious problem.
 
       
   598       ///\todo Is this really so?
 
       
   599       ///\todo It can copy between different types.
 
       
   600       const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
 
       
   601       {
 
       
   602 	container = m.container;
 
       
   603 	return *this;
 
       
   604       }
 
       
   605       template<typename TT>
 
       
   606       const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
 
       
   607       {
 
       
   608 	std::copy(m.container.begin(), m.container.end(), container.begin());
 
       
   609 	return *this;
 
       
   610       }
 
       
   611       
       
   612       void update() {}    //Useless for DynMaps
 
       
   613       void update(T a) {}  //Useless for DynMaps
 
       
   614 
       
   615     };
 
       
   616 
   323 
   617   };
 
   324   };
 
   618   
   325   
   619   /// @}  
   326   /// @}  
   620 
       
   621 } //namespace hugo
 
   327 } //namespace hugo
 
   622 
   328 
   623 
   329 
   624 
   330 
   625 
   331
lemon-0.x