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

     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     static bool valid(Edge e) { return e.n!=-1; }

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

   142     ///\deprecated Use

   143     ///\code

   144     ///  e=INVALID;

   145     ///\endcode

   146     ///instead.

   147     static void setInvalid(Edge &e) { e.n=-1; }

   148     ///\deprecated Use

   149     ///\code

   150     ///  e=INVALID;

   151     ///\endcode

   152     ///instead.

   153     static 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     static int id(Node v) { return v.n; }

   169     static int id(Edge e) { 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);

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

   240     public:

   241       /// An Edge with id \c n.

   243       /// \bug It should be

   244       /// obtained by a member function of the Graph.

   245       Edge(int nn) {n=nn;}

   246       Edge() { }

   247       Edge (Invalid) { n=-1; }

   248       bool operator==(const Edge i) const {return n==i.n;}

   249       bool operator!=(const Edge i) const {return n!=i.n;}

   250       bool operator<(const Edge i) const {return n<i.n;}

   251       ///\bug This is a workaround until somebody tells me how to

   252       ///make class \c SymSmartGraph::SymEdgeMap friend of Edge

   253       int &idref() {return n;}

   254       const int &idref() const {return n;}

   255     };

   257     class EdgeIt : public Edge {

   258       friend class SmartGraph;

   259     public:

   260       EdgeIt(const SmartGraph& G) : Edge(G.edges.size()-1) { }

   261       EdgeIt (Invalid i) : Edge(i) { }

   262       EdgeIt() : Edge() { }

   263       ///\bug This is a workaround until somebody tells me how to

   264       ///make class \c SymSmartGraph::SymEdgeMap friend of Edge

   265       int &idref() {return n;}

   266     };

   268     class OutEdgeIt : public Edge {

   269       friend class SmartGraph;

   270     public:

   271       OutEdgeIt() : Edge() { }

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

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

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

   276     };

   278     class InEdgeIt : public Edge {

   279       friend class SmartGraph;

   280     public:

   281       InEdgeIt() : Edge() { }

   282       InEdgeIt (Invalid i) : Edge(i) { }

   283       InEdgeIt(const SmartGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}

   284     };

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

   287     {

   288       std::vector<T> container;

   290     public:

   291       typedef T ValueType;

   292       typedef Node KeyType;

   294       NodeMap(const SmartGraph &_G) :

   295 	DynMapBase<Node>(_G), container(_G.maxNodeId())

   296       {

   297 	G->dyn_node_maps.push_back(this);

   298       }

   299       NodeMap(const SmartGraph &_G,const T &t) :

   300 	DynMapBase<Node>(_G), container(_G.maxNodeId(),t)

   301       {

   302 	G->dyn_node_maps.push_back(this);

   303       }

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

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

   307       {

   308  	G->dyn_node_maps.push_back(this);

   309       }

   311       template<typename TT> friend class NodeMap;

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

   314       ///\todo We could use 'copy'

   315       template<typename TT> NodeMap(const NodeMap<TT> &m) :

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

   317       {

   318 	G->dyn_node_maps.push_back(this);

   319 	typename std::vector<TT>::const_iterator i;

   320 	for(typename std::vector<TT>::const_iterator i=m.container.begin();

   321 	    i!=m.container.end();

   322 	    i++)

   323 	  container.push_back(*i);

   324       }

   325       ~NodeMap()

   326       {

   327 	if(G) {

   328 	  std::vector<DynMapBase<Node>* >::iterator i;

   329 	  for(i=G->dyn_node_maps.begin();

   330 	      i!=G->dyn_node_maps.end() && *i!=this; ++i) ;

   331 	  //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...

   332 	  //A better way to do that: (Is this really important?)

   333 	  if(*i==this) {

   334 	    *i=G->dyn_node_maps.back();

   335 	    G->dyn_node_maps.pop_back();

   336 	  }

   337 	}

   338       }

   340       void add(const Node k)

   341       {

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

   343       }

   345       void erase(const Node) { }

   347       void set(Node n, T a) { container[n.n]=a; }

   348       //'T& operator[](Node n)' would be wrong here

   349       typename std::vector<T>::reference

   350       operator[](Node n) { return container[n.n]; }

   351       //'const T& operator[](Node n)' would be wrong here

   352       typename std::vector<T>::const_reference

   353       operator[](Node n) const { return container[n.n]; }

   355       ///\warning There is no safety check at all!

   356       ///Using operator = between maps attached to different graph may

   357       ///cause serious problem.

   358       ///\todo Is this really so?

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

   360       const NodeMap<T>& operator=(const NodeMap<T> &m)

   361       {

   362 	container = m.container;

   363 	return *this;

   364       }

   365       template<typename TT>

   366       const NodeMap<T>& operator=(const NodeMap<TT> &m)

   367       {

   368 	std::copy(m.container.begin(), m.container.end(), container.begin());

   369 	return *this;

   370       }

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

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

   374     };

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

   377     {

   378       std::vector<T> container;

   380     public:

   381       typedef T ValueType;

   382       typedef Edge KeyType;

   384       EdgeMap(const SmartGraph &_G) :

   385 	DynMapBase<Edge>(_G), container(_G.maxEdgeId())

   386       {

   387 	//FIXME: What if there are empty Id's?

   388 	//FIXME: Can I use 'this' in a constructor?

   389 	G->dyn_edge_maps.push_back(this);

   390       }

   391       EdgeMap(const SmartGraph &_G,const T &t) :

   392 	DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)

   393       {

   394 	G->dyn_edge_maps.push_back(this);

   395       }

   396       EdgeMap(const EdgeMap<T> &m) :

   397  	DynMapBase<Edge>(*m.G), container(m.container)

   398       {

   399  	G->dyn_edge_maps.push_back(this);

   400       }

   402       template<typename TT> friend class EdgeMap;

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

   405       template<typename TT> EdgeMap(const EdgeMap<TT> &m)

   406 	: DynMapBase<Edge>(*m.G), container(m.container.size())

   407       {

   408 	G->dyn_edge_maps.push_back(this);

   409 	typename std::vector<TT>::const_iterator i;

   410 	for(typename std::vector<TT>::const_iterator i=m.container.begin();

   411 	    i!=m.container.end();

   412 	    i++)

   413 	  container.push_back(*i);

   414       }

   415       ~EdgeMap()

   416       {

   417 	if(G) {

   418 	  std::vector<DynMapBase<Edge>* >::iterator i;

   419 	  for(i=G->dyn_edge_maps.begin();

   420 	      i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;

   421 	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...

   422 	  //A better way to do that: (Is this really important?)

   423 	  if(*i==this) {

   424 	    *i=G->dyn_edge_maps.back();

   425 	    G->dyn_edge_maps.pop_back();

   426 	  }

   427 	}

   428       }

   430       void add(const Edge k)

   431       {

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

   433       }

   434       void erase(const Edge) { }

   436       void set(Edge n, T a) { container[n.n]=a; }

   437       //T get(Edge n) const { return container[n.n]; }

   438       typename std::vector<T>::reference

   439       operator[](Edge n) { return container[n.n]; }

   440       typename std::vector<T>::const_reference

   441       operator[](Edge n) const { return container[n.n]; }

   443       ///\warning There is no safety check at all!

   444       ///Using operator = between maps attached to different graph may

   445       ///cause serious problem.

   446       ///\todo Is this really so?

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

   448       const EdgeMap<T>& operator=(const EdgeMap<T> &m)

   449       {

   450 	container = m.container;

   451 	return *this;

   452       }

   453       template<typename TT>

   454       const EdgeMap<T>& operator=(const EdgeMap<TT> &m)

   455       {

   456 	std::copy(m.container.begin(), m.container.end(), container.begin());

   457 	return *this;

   458       }

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

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

   462     };

   464   };

   466   ///Graph for bidirectional edges.

   468   ///The purpose of this graph structure is to handle graphs

   469   ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair

   470   ///of oppositely directed edges.

   471   ///There is a new edge map type called

   472   ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"

   473   ///that complements this

   474   ///feature by

   475   ///storing shared values for the edge pairs. The usual

   476   ///\ref GraphSkeleton::EdgeMap "EdgeMap"

   477   ///can be used

   478   ///as well.

   479   ///

   480   ///The oppositely directed edge can also be obtained easily

   481   ///using \ref opposite.

   482   ///\warning It shares the similarity with \ref SmartGraph that

   483   ///it is not possible to delete edges or nodes from the graph.

   484   //\sa \ref SmartGraph.

   486   class SymSmartGraph : public SmartGraph

   487   {

   488   public:

   489     template<typename T> class SymEdgeMap;

   490     template<typename T> friend class SymEdgeMap;

   492     SymSmartGraph() : SmartGraph() { }

   493     SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }

   494     ///Adds a pair of oppositely directed edges to the graph.

   495     Edge addEdge(Node u, Node v)

   496     {

   497       Edge e = SmartGraph::addEdge(u,v);

   498       SmartGraph::addEdge(v,u);

   499       return e;

   500     }

   502     ///The oppositely directed edge.

   504     ///Returns the oppositely directed

   505     ///pair of the edge \c e.

   506     static Edge opposite(Edge e)

   507     {

   508       Edge f;

   509       f.idref() = e.idref() - 2*(e.idref()%2) + 1;

   510       return f;

   511     }

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

   515     ///This map makes it possible to store data shared by the oppositely

   516     ///directed pairs of edges.

   517     template <typename T> class SymEdgeMap : public DynMapBase<Edge>

   518     {

   519       std::vector<T> container;

   521     public:

   522       typedef T ValueType;

   523       typedef Edge KeyType;

   525       SymEdgeMap(const SymSmartGraph &_G) :

   526 	DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)

   527       {

   528 	static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.push_back(this);

   529       }

   530       SymEdgeMap(const SymSmartGraph &_G,const T &t) :

   531 	DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)

   532       {

   533 	G->dyn_edge_maps.push_back(this);

   534       }

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

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

   538       {

   539  	G->dyn_node_maps.push_back(this);

   540       }

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

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

   545       ///

   547       template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m)

   548 	: DynMapBase<SymEdge>(*m.G), container(m.container.size())

   549       {

   550 	G->dyn_node_maps.push_back(this);

   551 	typename std::vector<TT>::const_iterator i;

   552 	for(typename std::vector<TT>::const_iterator i=m.container.begin();

   553 	    i!=m.container.end();

   554 	    i++)

   555 	  container.push_back(*i);

   556       }

   558       ~SymEdgeMap()

   559       {

   560 	if(G) {

   561 	  std::vector<DynMapBase<Edge>* >::iterator i;

   562 	  for(i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.begin();

   563 	      i!=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.end()

   564 		&& *i!=this; ++i) ;

   565 	  //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...

   566 	  //A better way to do that: (Is this really important?)

   567 	  if(*i==this) {

   568 	    *i=static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.back();

   569 	    static_cast<const SymSmartGraph*>(G)->dyn_edge_maps.pop_back();

   570 	  }

   571 	}

   572       }

   574       void add(const Edge k)

   575       {

   576 	if(!k.idref()%2&&k.idref()/2>=int(container.size()))

   577 	  container.resize(k.idref()/2+1);

   578       }

   579       void erase(const Edge k) { }

   581       void set(Edge n, T a) { container[n.idref()/2]=a; }

   582       //T get(Edge n) const { return container[n.idref()/2]; }

   583       typename std::vector<T>::reference

   584       operator[](Edge n) { return container[n.idref()/2]; }

   585       typename std::vector<T>::const_reference

   586       operator[](Edge n) const { return container[n.idref()/2]; }

   588       ///\warning There is no safety check at all!

   589       ///Using operator = between maps attached to different graph may

   590       ///cause serious problem.

   591       ///\todo Is this really so?

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

   593       const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)

   594       {

   595 	container = m.container;

   596 	return *this;

   597       }

   598       template<typename TT>

   599       const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)

   600       {

   601 	std::copy(m.container.begin(), m.container.end(), container.begin());

   602 	return *this;

   603       }

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

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

   608     };

   610   };

   612   /// @}

   614 } //namespace hugo

   619 #endif //HUGO_SMART_GRAPH_H

author	alpar
	Wed, 04 Aug 2004 18:51:51 +0000
changeset 751	e742d383fffc
parent 713	57c0b110b31e
child 753	f5382a084c07
permissions	-rw-r--r--