src/hugo/smart_graph.h
author ladanyi
Fri, 28 May 2004 07:48:16 +0000
changeset 666 410a1419e86b
parent 579 859f8c7e2a40
child 706 0fe42b8ec5a6
permissions -rw-r--r--
Added a short tutorial on using graphs.
     1 // -*- mode:C++ -*-
     2 
     3 #ifndef HUGO_SMART_GRAPH_H
     4 #define HUGO_SMART_GRAPH_H
     5 
     6 ///\ingroup graphs
     7 ///\file
     8 ///\brief SmartGraph and SymSmartGraph classes.
     9 
    10 #include <vector>
    11 #include <limits.h>
    12 
    13 #include <hugo/invalid.h>
    14 
    15 namespace hugo {
    16 
    17 /// \addtogroup graphs
    18 /// @{
    19   class SymSmartGraph;
    20 
    21   ///A smart graph class.
    22 
    23   ///This is a simple and fast graph implementation.
    24   ///It is also quite memory efficient, but at the price
    25   ///that <b> it does not support node and edge deletion</b>.
    26   ///It conforms to the graph interface documented under
    27   ///the description of \ref GraphSkeleton.
    28   ///\sa \ref GraphSkeleton.
    29   ///
    30   ///\todo Some member functions could be \c static.
    31   ///\author Alpar Juttner
    32   class SmartGraph {
    33 
    34     struct NodeT 
    35     {
    36       int first_in,first_out;      
    37       NodeT() : first_in(-1), first_out(-1) {}
    38     };
    39     struct EdgeT 
    40     {
    41       int head, tail, next_in, next_out;      
    42       //FIXME: is this necessary?
    43       EdgeT() : next_in(-1), next_out(-1) {}  
    44     };
    45 
    46     std::vector<NodeT> nodes;
    47 
    48     std::vector<EdgeT> edges;
    49     
    50     protected:
    51     
    52     template <typename Key> class DynMapBase
    53     {
    54     protected:
    55       const SmartGraph* G; 
    56     public:
    57       virtual void add(const Key k) = 0;
    58       virtual void erase(const Key k) = 0;
    59       DynMapBase(const SmartGraph &_G) : G(&_G) {}
    60       virtual ~DynMapBase() {}
    61       friend class SmartGraph;
    62     };
    63     
    64   public:
    65     template <typename T> class EdgeMap;
    66     template <typename T> class NodeMap;
    67 
    68     class Node;
    69     class Edge;
    70 
    71     //  protected:
    72     // HELPME:
    73   protected:
    74     ///\bug It must be public because of SymEdgeMap.
    75     ///
    76     mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
    77     ///\bug It must be public because of SymEdgeMap.
    78     ///
    79     mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
    80     
    81   public:
    82 
    83 
    84     class NodeIt;
    85     class EdgeIt;
    86     class OutEdgeIt;
    87     class InEdgeIt;
    88     
    89     template <typename T> class NodeMap;
    90     template <typename T> class EdgeMap;
    91     
    92   public:
    93 
    94     SmartGraph() : nodes(), edges() { }
    95     SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
    96     
    97     ~SmartGraph()
    98     {
    99       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
   100 	  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
   101       for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
   102 	  i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
   103     }
   104 
   105     int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
   106     int edgeNum() const { return edges.size(); }  //FIXME: What is this?
   107 
   108     ///\bug This function does something different than
   109     ///its name would suggests...
   110     int maxNodeId() const { return nodes.size(); }  //FIXME: What is this?
   111     ///\bug This function does something different than
   112     ///its name would suggests...
   113     int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?
   114 
   115     Node tail(Edge e) const { return edges[e.n].tail; }
   116     Node head(Edge e) const { return edges[e.n].head; }
   117 
   118     Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
   119     Node aNode(InEdgeIt e) const { return edges[e.n].head; }
   120 
   121     Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
   122     Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
   123 
   124     NodeIt& first(NodeIt& v) const { 
   125       v=NodeIt(*this); return v; }
   126     EdgeIt& first(EdgeIt& e) const { 
   127       e=EdgeIt(*this); return e; }
   128     OutEdgeIt& first(OutEdgeIt& e, const Node v) const { 
   129       e=OutEdgeIt(*this,v); return e; }
   130     InEdgeIt& first(InEdgeIt& e, const Node v) const { 
   131       e=InEdgeIt(*this,v); return e; }
   132 
   133 //     template< typename It >
   134 //     It first() const { It e; first(e); return e; }
   135 
   136 //     template< typename It >
   137 //     It first(Node v) const { It e; first(e,v); return e; }
   138 
   139     bool valid(Edge e) const { return e.n!=-1; }
   140     bool valid(Node n) const { return n.n!=-1; }
   141     
   142     ///\deprecated Use
   143     ///\code
   144     ///  e=INVALID;
   145     ///\endcode
   146     ///instead.
   147     void setInvalid(Edge &e) { e.n=-1; }
   148     ///\deprecated Use
   149     ///\code
   150     ///  e=INVALID;
   151     ///\endcode
   152     ///instead.
   153     void setInvalid(Node &n) { n.n=-1; }
   154     
   155     template <typename It> It getNext(It it) const
   156     { It tmp(it); return next(tmp); }
   157 
   158     NodeIt& next(NodeIt& it) const { 
   159       it.n=(it.n+2)%(nodes.size()+1)-1; 
   160       return it; 
   161     }
   162     OutEdgeIt& next(OutEdgeIt& it) const
   163     { it.n=edges[it.n].next_out; return it; }
   164     InEdgeIt& next(InEdgeIt& it) const
   165     { it.n=edges[it.n].next_in; return it; }
   166     EdgeIt& next(EdgeIt& it) const { --it.n; return it; }
   167 
   168     int id(Node v) const { return v.n; }
   169     int id(Edge e) const { return e.n; }
   170 
   171     Node addNode() {
   172       Node n; n.n=nodes.size();
   173       nodes.push_back(NodeT()); //FIXME: Hmmm...
   174 
   175       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
   176 	  i!=dyn_node_maps.end(); ++i) (**i).add(n);
   177 
   178       return n;
   179     }
   180     
   181     Edge addEdge(Node u, Node v) {
   182       Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
   183       edges[e.n].tail=u.n; edges[e.n].head=v.n;
   184       edges[e.n].next_out=nodes[u.n].first_out;
   185       edges[e.n].next_in=nodes[v.n].first_in;
   186       nodes[u.n].first_out=nodes[v.n].first_in=e.n;
   187 
   188       for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
   189 	  i!=dyn_edge_maps.end(); ++i) (**i).add(e);
   190 
   191       return e;
   192     }
   193 
   194     void clear() {nodes.clear();edges.clear();}
   195 
   196     class Node {
   197       friend class SmartGraph;
   198       template <typename T> friend class NodeMap;
   199       
   200       friend class Edge;
   201       friend class OutEdgeIt;
   202       friend class InEdgeIt;
   203       friend class SymEdge;
   204 
   205     protected:
   206       int n;
   207       friend int SmartGraph::id(Node v) const; 
   208       Node(int nn) {n=nn;}
   209     public:
   210       Node() {}
   211       Node (Invalid) { n=-1; }
   212       bool operator==(const Node i) const {return n==i.n;}
   213       bool operator!=(const Node i) const {return n!=i.n;}
   214       bool operator<(const Node i) const {return n<i.n;}
   215     };
   216     
   217     class NodeIt : public Node {
   218       friend class SmartGraph;
   219     public:
   220       NodeIt() : Node() { }
   221       NodeIt(Invalid i) : Node(i) { }
   222       NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }
   223       ///\todo Undocumented conversion Node -\> NodeIt.
   224       NodeIt(const SmartGraph& G, const Node &n) : Node(n) { }
   225     };
   226 
   227     class Edge {
   228       friend class SmartGraph;
   229       template <typename T> friend class EdgeMap;
   230 
   231       //template <typename T> friend class SymSmartGraph::SymEdgeMap;      
   232       //friend Edge SymSmartGraph::opposite(Edge) const;
   233       
   234       friend class Node;
   235       friend class NodeIt;
   236     protected:
   237       int n;
   238       friend int SmartGraph::id(Edge e) const;
   239 
   240       Edge(int nn) {n=nn;}
   241     public:
   242       Edge() { }
   243       Edge (Invalid) { n=-1; }
   244       bool operator==(const Edge i) const {return n==i.n;}
   245       bool operator!=(const Edge i) const {return n!=i.n;}
   246       bool operator<(const Edge i) const {return n<i.n;}
   247       ///\bug This is a workaround until somebody tells me how to
   248       ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
   249       int &idref() {return n;}
   250       const int &idref() const {return n;}
   251     };
   252     
   253     class EdgeIt : public Edge {
   254       friend class SmartGraph;
   255     public:
   256       EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }
   257       EdgeIt (Invalid i) : Edge(i) { }
   258       EdgeIt() : Edge() { }
   259       ///\bug This is a workaround until somebody tells me how to
   260       ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
   261       int &idref() {return n;}
   262     };
   263     
   264     class OutEdgeIt : public Edge {
   265       friend class SmartGraph;
   266     public: 
   267       OutEdgeIt() : Edge() { }
   268       OutEdgeIt (Invalid i) : Edge(i) { }
   269 
   270       OutEdgeIt(const SmartGraph& G,const Node v)
   271 	: Edge(G.nodes[v.n].first_out) {}
   272     };
   273     
   274     class InEdgeIt : public Edge {
   275       friend class SmartGraph;
   276     public: 
   277       InEdgeIt() : Edge() { }
   278       InEdgeIt (Invalid i) : Edge(i) { }
   279       InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
   280     };
   281 
   282     template <typename T> class NodeMap : public DynMapBase<Node>
   283     {
   284       std::vector<T> container;
   285 
   286     public:
   287       typedef T ValueType;
   288       typedef Node KeyType;
   289 
   290       NodeMap(const SmartGraph &_G) :
   291 	DynMapBase<Node>(_G), container(_G.maxNodeId())
   292       {
   293 	G->dyn_node_maps.push_back(this);
   294       }
   295       NodeMap(const SmartGraph &_G,const T &t) :
   296 	DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
   297       {
   298 	G->dyn_node_maps.push_back(this);
   299       }
   300       
   301       NodeMap(const NodeMap<T> &m) :
   302  	DynMapBase<Node>(*m.G), container(m.container)
   303       {
   304  	G->dyn_node_maps.push_back(this);
   305       }
   306 
   307       template<typename TT> friend class NodeMap;
   308  
   309       ///\todo It can copy between different types.
   310       ///\todo We could use 'copy'
   311       template<typename TT> NodeMap(const NodeMap<TT> &m) :
   312 	DynMapBase<Node>(*m.G), container(m.container.size())
   313       {
   314 	G->dyn_node_maps.push_back(this);
   315 	typename std::vector<TT>::const_iterator i;
   316 	for(typename std::vector<TT>::const_iterator i=m.container.begin();
   317 	    i!=m.container.end();
   318 	    i++)
   319 	  container.push_back(*i);
   320       }
   321       ~NodeMap()
   322       {
   323 	if(G) {
   324 	  std::vector<DynMapBase<Node>* >::iterator i;
   325 	  for(i=G->dyn_node_maps.begin();
   326 	      i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
   327 	  //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
   328 	  //A better way to do that: (Is this really important?)
   329 	  if(*i==this) {
   330 	    *i=G->dyn_node_maps.back();
   331 	    G->dyn_node_maps.pop_back();
   332 	  }
   333 	}
   334       }
   335 
   336       void add(const Node k) 
   337       {
   338 	if(k.n>=int(container.size())) container.resize(k.n+1);
   339       }
   340 
   341       void erase(const Node) { }
   342       
   343       void set(Node n, T a) { container[n.n]=a; }
   344       //'T& operator[](Node n)' would be wrong here
   345       typename std::vector<T>::reference
   346       operator[](Node n) { return container[n.n]; }
   347       //'const T& operator[](Node n)' would be wrong here
   348       typename std::vector<T>::const_reference 
   349       operator[](Node n) const { return container[n.n]; }
   350 
   351       ///\warning There is no safety check at all!
   352       ///Using operator = between maps attached to different graph may
   353       ///cause serious problem.
   354       ///\todo Is this really so?
   355       ///\todo It can copy between different types.
   356       const NodeMap<T>& operator=(const NodeMap<T> &m)
   357       {
   358 	container = m.container;
   359 	return *this;
   360       }
   361       template<typename TT>
   362       const NodeMap<T>& operator=(const NodeMap<TT> &m)
   363       {
   364 	std::copy(m.container.begin(), m.container.end(), container.begin());
   365 	return *this;
   366       }
   367       
   368       void update() {}    //Useless for Dynamic Maps
   369       void update(T a) {}  //Useless for Dynamic Maps
   370     };
   371     
   372     template <typename T> class EdgeMap : public DynMapBase<Edge>
   373     {
   374       std::vector<T> container;
   375 
   376     public:
   377       typedef T ValueType;
   378       typedef Edge KeyType;
   379 
   380       EdgeMap(const SmartGraph &_G) :
   381 	DynMapBase<Edge>(_G), container(_G.maxEdgeId())
   382       {
   383 	//FIXME: What if there are empty Id's?
   384 	//FIXME: Can I use 'this' in a constructor?
   385 	G->dyn_edge_maps.push_back(this);
   386       }
   387       EdgeMap(const SmartGraph &_G,const T &t) :
   388 	DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
   389       {
   390 	G->dyn_edge_maps.push_back(this);
   391       } 
   392       EdgeMap(const EdgeMap<T> &m) :
   393  	DynMapBase<Edge>(*m.G), container(m.container)
   394       {
   395  	G->dyn_edge_maps.push_back(this);
   396       }
   397 
   398       template<typename TT> friend class EdgeMap;
   399 
   400       ///\todo It can copy between different types.
   401       template<typename TT> EdgeMap(const EdgeMap<TT> &m)
   402 	: DynMapBase<Edge>(*m.G), container(m.container.size())
   403       {
   404 	G->dyn_edge_maps.push_back(this);
   405 	typename std::vector<TT>::const_iterator i;
   406 	for(typename std::vector<TT>::const_iterator i=m.container.begin();
   407 	    i!=m.container.end();
   408 	    i++)
   409 	  container.push_back(*i);
   410       }
   411       ~EdgeMap()
   412       {
   413 	if(G) {
   414 	  std::vector<DynMapBase<Edge>* >::iterator i;
   415 	  for(i=G->dyn_edge_maps.begin();
   416 	      i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
   417 	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
   418 	  //A better way to do that: (Is this really important?)
   419 	  if(*i==this) {
   420 	    *i=G->dyn_edge_maps.back();
   421 	    G->dyn_edge_maps.pop_back();
   422 	  }
   423 	}
   424       }
   425       
   426       void add(const Edge k) 
   427       {
   428 	if(k.n>=int(container.size())) container.resize(k.n+1);
   429       }
   430       void erase(const Edge) { }
   431       
   432       void set(Edge n, T a) { container[n.n]=a; }
   433       //T get(Edge n) const { return container[n.n]; }
   434       typename std::vector<T>::reference
   435       operator[](Edge n) { return container[n.n]; }
   436       typename std::vector<T>::const_reference
   437       operator[](Edge n) const { return container[n.n]; }
   438 
   439       ///\warning There is no safety check at all!
   440       ///Using operator = between maps attached to different graph may
   441       ///cause serious problem.
   442       ///\todo Is this really so?
   443       ///\todo It can copy between different types.
   444       const EdgeMap<T>& operator=(const EdgeMap<T> &m)
   445       {
   446 	container = m.container;
   447 	return *this;
   448       }
   449       template<typename TT>
   450       const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
   451       {
   452 	std::copy(m.container.begin(), m.container.end(), container.begin());
   453 	return *this;
   454       }
   455       
   456       void update() {}    //Useless for DynMaps
   457       void update(T a) {}  //Useless for DynMaps
   458     };
   459 
   460   };
   461 
   462   ///Graph for bidirectional edges.
   463 
   464   ///The purpose of this graph structure is to handle graphs
   465   ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
   466   ///of oppositely directed edges.
   467   ///There is a new edge map type called
   468   ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
   469   ///that complements this
   470   ///feature by
   471   ///storing shared values for the edge pairs. The usual
   472   ///\ref GraphSkeleton::EdgeMap "EdgeMap"
   473   ///can be used
   474   ///as well.
   475   ///
   476   ///The oppositely directed edge can also be obtained easily
   477   ///using \ref opposite.
   478   ///\warning It shares the similarity with \ref SmartGraph that
   479   ///it is not possible to delete edges or nodes from the graph.
   480   //\sa \ref SmartGraph.
   481 
   482   class SymSmartGraph : public SmartGraph
   483   {
   484   public:
   485     template<typename T> class SymEdgeMap;
   486     template<typename T> friend class SymEdgeMap;
   487 
   488     SymSmartGraph() : SmartGraph() { }
   489     SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
   490     ///Adds a pair of oppositely directed edges to the graph.
   491     Edge addEdge(Node u, Node v)
   492     {
   493       Edge e = SmartGraph::addEdge(u,v);
   494       SmartGraph::addEdge(v,u);
   495       return e;
   496     }
   497 
   498     ///The oppositely directed edge.
   499 
   500     ///Returns the oppositely directed
   501     ///pair of the edge \c e.
   502     Edge opposite(Edge e) const
   503     {
   504       Edge f;
   505       f.idref() = e.idref() - 2*(e.idref()%2) + 1;
   506       return f;
   507     }
   508     
   509     ///Common data storage for the edge pairs.
   510 
   511     ///This map makes it possible to store data shared by the oppositely
   512     ///directed pairs of edges.
   513     template <typename T> class SymEdgeMap : public DynMapBase<Edge>
   514     {
   515       std::vector<T> container;
   516       
   517     public:
   518       typedef T ValueType;
   519       typedef Edge KeyType;
   520 
   521       SymEdgeMap(const SymSmartGraph &_G) :
   522 	DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
   523       {
   524 	static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);
   525       }
   526       SymEdgeMap(const SymSmartGraph &_G,const T &t) :
   527 	DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
   528       {
   529 	G->dyn_edge_maps.push_back(this);
   530       }
   531 
   532       SymEdgeMap(const SymEdgeMap<T> &m) :
   533  	DynMapBase<SymEdge>(*m.G), container(m.container)
   534       {
   535  	G->dyn_node_maps.push_back(this);
   536       }
   537 
   538       //      template<typename TT> friend class SymEdgeMap;
   539 
   540       ///\todo It can copy between different types.
   541       ///
   542 
   543       template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m)
   544 	: DynMapBase<SymEdge>(*m.G), container(m.container.size())
   545       {
   546 	G->dyn_node_maps.push_back(this);
   547 	typename std::vector<TT>::const_iterator i;
   548 	for(typename std::vector<TT>::const_iterator i=m.container.begin();
   549 	    i!=m.container.end();
   550 	    i++)
   551 	  container.push_back(*i);
   552       }
   553  
   554       ~SymEdgeMap()
   555       {
   556 	if(G) {
   557 	  std::vector<DynMapBase<Edge>* >::iterator i;
   558 	  for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();
   559 	      i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()
   560 		&& *i!=this; ++i) ;
   561 	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
   562 	  //A better way to do that: (Is this really important?)
   563 	  if(*i==this) {
   564 	    *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();
   565 	    static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();
   566 	  }
   567 	}
   568       }
   569       
   570       void add(const Edge k) 
   571       {
   572 	if(!k.idref()%2&&k.idref()/2>=int(container.size()))
   573 	  container.resize(k.idref()/2+1);
   574       }
   575       void erase(const Edge k) { }
   576       
   577       void set(Edge n, T a) { container[n.idref()/2]=a; }
   578       //T get(Edge n) const { return container[n.idref()/2]; }
   579       typename std::vector<T>::reference
   580       operator[](Edge n) { return container[n.idref()/2]; }
   581       typename std::vector<T>::const_reference
   582       operator[](Edge n) const { return container[n.idref()/2]; }
   583 
   584       ///\warning There is no safety check at all!
   585       ///Using operator = between maps attached to different graph may
   586       ///cause serious problem.
   587       ///\todo Is this really so?
   588       ///\todo It can copy between different types.
   589       const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
   590       {
   591 	container = m.container;
   592 	return *this;
   593       }
   594       template<typename TT>
   595       const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
   596       {
   597 	std::copy(m.container.begin(), m.container.end(), container.begin());
   598 	return *this;
   599       }
   600       
   601       void update() {}    //Useless for DynMaps
   602       void update(T a) {}  //Useless for DynMaps
   603 
   604     };
   605 
   606   };
   607   
   608   /// @}  
   609 
   610 } //namespace hugo
   611 
   612 
   613 
   614 
   615 #endif //HUGO_SMART_GRAPH_H