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

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

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

   225     class Edge {

   226       friend class SmartGraph;

   227       template <typename T> friend class EdgeMap;

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

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

   232       friend class Node;

   233       friend class NodeIt;

   234     protected:

   235       int n;

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

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

   239     public:

   240       Edge() { }

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

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

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

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

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

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

   247       int &idref() {return n;}

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

   249     };

   251     class EdgeIt : public Edge {

   252       friend class SmartGraph;

   253     public:

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

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

   256       EdgeIt() : Edge() { }

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

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

   259       int &idref() {return n;}

   260     };

   262     class OutEdgeIt : public Edge {

   263       friend class SmartGraph;

   264     public:

   265       OutEdgeIt() : Edge() { }

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

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

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

   270     };

   272     class InEdgeIt : public Edge {

   273       friend class SmartGraph;

   274     public:

   275       InEdgeIt() : Edge() { }

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

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

   278     };

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

   281     {

   282       std::vector<T> container;

   284     public:

   285       typedef T ValueType;

   286       typedef Node KeyType;

   288       NodeMap(const SmartGraph &_G) :

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

   290       {

   291 	G->dyn_node_maps.push_back(this);

   292       }

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

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

   295       {

   296 	G->dyn_node_maps.push_back(this);

   297       }

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

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

   301       {

   302  	G->dyn_node_maps.push_back(this);

   303       }

   305       template<typename TT> friend class NodeMap;

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

   308       ///

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

   310 	DynMapBase<Node>(*m.G)

   311       {

   312 	G->dyn_node_maps.push_back(this);

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

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

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

   316 	    i++)

   317 	  container.push_back(*i);

   318       }

   319       ~NodeMap()

   320       {

   321 	if(G) {

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

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

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

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

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

   327 	  if(*i==this) {

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

   329 	    G->dyn_node_maps.pop_back();

   330 	  }

   331 	}

   332       }

   334       void add(const Node k)

   335       {

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

   337       }

   339       void erase(const Node) { }

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

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

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

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

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

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

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

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

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

   351       ///cause serious problem.

   352       ///\todo Is this really so?

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

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

   355       {

   356 	container = m.container;

   357 	return *this;

   358       }

   359       template<typename TT>

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

   361       {

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

   363 	return *this;

   364       }

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

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

   368     };

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

   371     {

   372       std::vector<T> container;

   374     public:

   375       typedef T ValueType;

   376       typedef Edge KeyType;

   378       EdgeMap(const SmartGraph &_G) :

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

   380       {

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

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

   383 	G->dyn_edge_maps.push_back(this);

   384       }

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

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

   387       {

   388 	G->dyn_edge_maps.push_back(this);

   389       }

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

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

   392       {

   393  	G->dyn_edge_maps.push_back(this);

   394       }

   396       template<typename TT> friend class EdgeMap;

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

   399       ///

   400       template<typename TT> EdgeMap(const EdgeMap<TT> &m) :

   401 	DynMapBase<Edge>(*m.G)

   402       {

   403 	G->dyn_edge_maps.push_back(this);

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

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

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

   407 	    i++)

   408 	  container.push_back(*i);

   409       }

   410       ~EdgeMap()

   411       {

   412 	if(G) {

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

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

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

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

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

   418 	  if(*i==this) {

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

   420 	    G->dyn_edge_maps.pop_back();

   421 	  }

   422 	}

   423       }

   425       void add(const Edge k)

   426       {

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

   428       }

   429       void erase(const Edge) { }

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

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

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

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

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

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

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

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

   440       ///cause serious problem.

   441       ///\todo Is this really so?

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

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

   444       {

   445 	container = m.container;

   446 	return *this;

   447       }

   448       template<typename TT>

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

   450       {

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

   452 	return *this;

   453       }

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

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

   457     };

   459   };

   461   ///Graph for bidirectional edges.

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

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

   465   ///of oppositely directed edges.

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

   467   ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"

   468   ///that complements this

   469   ///feature by

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

   471   ///\ref GraphSkeleton::EdgeMap "EdgeMap"

   472   ///can be used

   473   ///as well.

   474   ///

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

   476   ///using \ref opposite.

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

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

   479   //\sa \ref SmartGraph.

   481   class SymSmartGraph : public SmartGraph

   482   {

   483   public:

   484     template<typename T> class SymEdgeMap;

   485     template<typename T> friend class SymEdgeMap;

   487     SymSmartGraph() : SmartGraph() { }

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

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

   490     Edge addEdge(Node u, Node v)

   491     {

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

   493       SmartGraph::addEdge(v,u);

   494       return e;

   495     }

   497     ///The oppositely directed edge.

   499     ///Returns the oppositely directed

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

   501     Edge opposite(Edge e) const

   502     {

   503       Edge f;

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

   505       return f;

   506     }

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

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

   511     ///directed pairs of edges.

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

   513     {

   514       std::vector<T> container;

   516     public:

   517       typedef T ValueType;

   518       typedef Edge KeyType;

   520       SymEdgeMap(const SymSmartGraph &_G) :

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

   522       {

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

   524       }

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

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

   527       {

   528 	G->dyn_edge_maps.push_back(this);

   529       }

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

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

   533       {

   534  	G->dyn_node_maps.push_back(this);

   535       }

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

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

   540       ///

   542       template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :

   543 	DynMapBase<SymEdge>(*m.G)

   544       {

   545 	G->dyn_node_maps.push_back(this);

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

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

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

   549 	    i++)

   550 	  container.push_back(*i);

   551       }

   553       ~SymEdgeMap()

   554       {

   555 	if(G) {

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

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

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

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

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

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

   562 	  if(*i==this) {

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

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

   565 	  }

   566 	}

   567       }

   569       void add(const Edge k)

   570       {

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

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

   573       }

   574       void erase(const Edge k) { }

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

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

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

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

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

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

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

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

   585       ///cause serious problem.

   586       ///\todo Is this really so?

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

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

   589       {

   590 	container = m.container;

   591 	return *this;

   592       }

   593       template<typename TT>

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

   595       {

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

   597 	return *this;

   598       }

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

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

   603     };

   605   };

   607   /// @}

   609 } //namespace hugo

   614 #endif //SMART_GRAPH_H

author	alpar
	Fri, 07 May 2004 06:35:02 +0000
changeset 566	14355e502338
parent 539	fb261e3a9a0f
child 579	859f8c7e2a40
permissions	-rw-r--r--