lemon-0.x: src/hugo/smart_graph.h@1ea8162ce638

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

     3 #ifndef HUGO_SMART_GRAPH_H

     4 #define HUGO_SMART_GRAPH_H

     6 ///\ingroup graphs

     7 ///\file

     8 ///\brief SmartGraph and SymSmartGraph classes.

    10 #include <vector>

    11 #include <limits.h>

    13 #include <hugo/invalid.h>

    15 namespace hugo {

    17 /// \addtogroup graphs

    18 /// @{

    19   class SymSmartGraph;

    21   ///A smart graph class.

    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 {

    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     };

    46     std::vector<NodeT> nodes;

    48     std::vector<EdgeT> edges;

    50     protected:

    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     };

    64   public:

    65     template <typename T> class EdgeMap;

    66     template <typename T> class NodeMap;

    68     class Node;

    69     class Edge;

    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;

    81   public:

    84     class NodeIt;

    85     class EdgeIt;

    86     class OutEdgeIt;

    87     class InEdgeIt;

    89     template <typename T> class NodeMap;

    90     template <typename T> class EdgeMap;

    92   public:

    94     SmartGraph() : nodes(), edges() { }

    95     SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }

    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     }

   105     int nodeNum() const { return nodes.size(); }  //FIXME: What is this?

   106     int edgeNum() const { return edges.size(); }  //FIXME: What is this?

   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?

   115     Node tail(Edge e) const { return edges[e.n].tail; }

   116     Node head(Edge e) const { return edges[e.n].head; }

   118     Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }

   119     Node aNode(InEdgeIt e) const { return edges[e.n].head; }

   121     Node bNode(OutEdgeIt e) const { return edges[e.n].head; }

   122     Node bNode(InEdgeIt e) const { return edges[e.n].tail; }

   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; }

   133 //     template< typename It >

   134 //     It first() const { It e; first(e); return e; }

   136 //     template< typename It >

   137 //     It first(Node v) const { It e; first(e,v); return e; }

   139     bool valid(Edge e) const { return e.n!=-1; }

   140     bool valid(Node n) const { return n.n!=-1; }

   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; }

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

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

   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; }

   168     int id(Node v) const { return v.n; }

   169     int id(Edge e) const { return e.n; }

   171     Node addNode() {

   172       Node n; n.n=nodes.size();

   173       nodes.push_back(NodeT()); //FIXME: Hmmm...

   175       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();

   176 	  i!=dyn_node_maps.end(); ++i) (**i).add(n);

   178       return n;

   179     }

   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;

   188       for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();

   189 	  i!=dyn_edge_maps.end(); ++i) (**i).add(e);

   191       return e;

   192     }

   194     void clear() {nodes.clear();edges.clear();}

   196     class Node {

   197       friend class SmartGraph;

   198       template <typename T> friend class NodeMap;

   200       friend class Edge;

   201       friend class OutEdgeIt;

   202       friend class InEdgeIt;

   203       friend class SymEdge;

   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     };

   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     };

   227     class Edge {

   228       friend class SmartGraph;

   229       template <typename T> friend class EdgeMap;

   231       //template <typename T> friend class SymSmartGraph::SymEdgeMap;

   232       //friend Edge SymSmartGraph::opposite(Edge) const;

   234       friend class Node;

   235       friend class NodeIt;

   236     protected:

   237       int n;

   238       friend int SmartGraph::id(Edge e) const;

   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     };

   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     };

   264     class OutEdgeIt : public Edge {

   265       friend class SmartGraph;

   266     public:

   267       OutEdgeIt() : Edge() { }

   268       OutEdgeIt (Invalid i) : Edge(i) { }

   270       OutEdgeIt(const SmartGraph& G,const Node v)

   271 	: Edge(G.nodes[v.n].first_out) {}

   272     };

   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     };

   282     template <typename T> class NodeMap : public DynMapBase<Node>

   283     {

   284       std::vector<T> container;

   286     public:

   287       typedef T ValueType;

   288       typedef Node KeyType;

   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       }

   301       NodeMap(const NodeMap<T> &m) :

   302  	DynMapBase<Node>(*m.G), container(m.container)

   303       {

   304  	G->dyn_node_maps.push_back(this);

   305       }

   307       template<typename TT> friend class NodeMap;

   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       }

   336       void add(const Node k)

   337       {

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

   339       }

   341       void erase(const Node) { }

   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]; }

   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       }

   368       void update() {}    //Useless for Dynamic Maps

   369       void update(T a) {}  //Useless for Dynamic Maps

   370     };

   372     template <typename T> class EdgeMap : public DynMapBase<Edge>

   373     {

   374       std::vector<T> container;

   376     public:

   377       typedef T ValueType;

   378       typedef Edge KeyType;

   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       }

   398       template<typename TT> friend class EdgeMap;

   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       }

   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) { }

   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]; }

   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       }

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

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

   458     };

   460   };

   462   ///Graph for bidirectional edges.

   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.

   482   class SymSmartGraph : public SmartGraph

   483   {

   484   public:

   485     template<typename T> class SymEdgeMap;

   486     template<typename T> friend class SymEdgeMap;

   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     }

   498     ///The oppositely directed edge.

   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     }

   509     ///Common data storage for the edge pairs.

   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;

   517     public:

   518       typedef T ValueType;

   519       typedef Edge KeyType;

   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       }

   532       SymEdgeMap(const SymEdgeMap<T> &m) :

   533  	DynMapBase<SymEdge>(*m.G), container(m.container)

   534       {

   535  	G->dyn_node_maps.push_back(this);

   536       }

   538       //      template<typename TT> friend class SymEdgeMap;

   540       ///\todo It can copy between different types.

   541       ///

   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       }

   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       }

   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) { }

   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]; }

   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       }

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

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

   604     };

   606   };

   608   /// @}

   610 } //namespace hugo

   615 #endif //HUGO_SMART_GRAPH_H

author	alpar
	Mon, 14 Jun 2004 09:47:54 +0000
changeset 682	1ea8162ce638
parent 579	859f8c7e2a40
child 706	0fe42b8ec5a6
permissions	-rw-r--r--