lemon-0.x: src/include/smart_graph.h@eb8bfa683d92

     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 "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:

    83     class NodeIt;

    84     class EdgeIt;

    85     class OutEdgeIt;

    86     class InEdgeIt;

    88     template <typename T> class NodeMap;

    89     template <typename T> class EdgeMap;

    91   public:

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

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

    96     ~SmartGraph()

    97     {

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

    99 	  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;

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

   101 	  i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;

   102     }

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

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

   107     ///\bug This function does something different than

   108     ///its name would suggests...

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

   110     ///\bug This function does something different than

   111     ///its name would suggests...

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

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

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

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

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

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

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

   123     NodeIt& first(NodeIt& v) const {

   124       v=NodeIt(*this); return v; }

   125     EdgeIt& first(EdgeIt& e) const {

   126       e=EdgeIt(*this); return e; }

   127     OutEdgeIt& first(OutEdgeIt& e, const Node v) const {

   128       e=OutEdgeIt(*this,v); return e; }

   129     InEdgeIt& first(InEdgeIt& e, const Node v) const {

   130       e=InEdgeIt(*this,v); return e; }

   132 //     template< typename It >

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

   135 //     template< typename It >

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

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

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

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

   142     void setInvalid(Node &n) { n.n=-1; }

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

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

   147     NodeIt& next(NodeIt& it) const {

   148       it.n=(it.n+2)%(nodes.size()+1)-1;

   149       return it;

   150     }

   151     OutEdgeIt& next(OutEdgeIt& it) const

   152     { it.n=edges[it.n].next_out; return it; }

   153     InEdgeIt& next(InEdgeIt& it) const

   154     { it.n=edges[it.n].next_in; return it; }

   155     EdgeIt& next(EdgeIt& it) const { --it.n; return it; }

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

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

   160     Node addNode() {

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

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

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

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

   167       return n;

   168     }

   170     Edge addEdge(Node u, Node v) {

   171       Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...

   172       edges[e.n].tail=u.n; edges[e.n].head=v.n;

   173       edges[e.n].next_out=nodes[u.n].first_out;

   174       edges[e.n].next_in=nodes[v.n].first_in;

   175       nodes[u.n].first_out=nodes[v.n].first_in=e.n;

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

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

   180       return e;

   181     }

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

   185     class Node {

   186       friend class SmartGraph;

   187       template <typename T> friend class NodeMap;

   189       friend class Edge;

   190       friend class OutEdgeIt;

   191       friend class InEdgeIt;

   192       friend class SymEdge;

   194     protected:

   195       int n;

   196       friend int SmartGraph::id(Node v) const;

   197       Node(int nn) {n=nn;}

   198     public:

   199       Node() {}

   200       Node (Invalid i) { n=-1; }

   201       bool operator==(const Node i) const {return n==i.n;}

   202       bool operator!=(const Node i) const {return n!=i.n;}

   203       bool operator<(const Node i) const {return n<i.n;}

   204     };

   206     class NodeIt : public Node {

   207       friend class SmartGraph;

   208     public:

   209       NodeIt() : Node() { }

   210       NodeIt(Invalid i) : Node(i) { }

   211       NodeIt(const SmartGraph& G) : Node(G.nodes.size()?0:-1) { }

   212     };

   214     class Edge {

   215       friend class SmartGraph;

   216       template <typename T> friend class EdgeMap;

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

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

   221       friend class Node;

   222       friend class NodeIt;

   223     protected:

   224       int n;

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

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

   228     public:

   229       Edge() { }

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

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

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

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

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

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

   236       int &idref() {return n;}

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

   238     };

   240     class EdgeIt : public Edge {

   241       friend class SmartGraph;

   242     public:

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

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

   245       EdgeIt() : Edge() { }

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

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

   248       int &idref() {return n;}

   249     };

   251     class OutEdgeIt : public Edge {

   252       friend class SmartGraph;

   253     public:

   254       OutEdgeIt() : Edge() { }

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

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

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

   259     };

   261     class InEdgeIt : public Edge {

   262       friend class SmartGraph;

   263     public:

   264       InEdgeIt() : Edge() { }

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

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

   267     };

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

   270     {

   271       std::vector<T> container;

   273     public:

   274       typedef T ValueType;

   275       typedef Node KeyType;

   277       NodeMap(const SmartGraph &_G) :

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

   279       {

   280 	G->dyn_node_maps.push_back(this);

   281       }

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

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

   284       {

   285 	G->dyn_node_maps.push_back(this);

   286       }

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

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

   290       {

   291  	G->dyn_node_maps.push_back(this);

   292       }

   294       template<typename TT> friend class NodeMap;

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

   297       ///

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

   299 	DynMapBase<Node>(*m.G)

   300       {

   301 	G->dyn_node_maps.push_back(this);

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

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

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

   305 	    i++)

   306 	  container.push_back(*i);

   307       }

   308       ~NodeMap()

   309       {

   310 	if(G) {

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

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

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

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

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

   316 	  if(*i==this) {

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

   318 	    G->dyn_node_maps.pop_back();

   319 	  }

   320 	}

   321       }

   323       void add(const Node k)

   324       {

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

   326       }

   328       void erase(const Node) { }

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

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

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

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

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

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

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

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

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

   340       ///cause serious problem.

   341       ///\todo Is this really so?

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

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

   344       {

   345 	container = m.container;

   346 	return *this;

   347       }

   348       template<typename TT>

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

   350       {

   351 	copy(m.container.begin(), m.container.end(), container.begin());

   352 	return *this;

   353       }

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

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

   357     };

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

   360     {

   361       std::vector<T> container;

   363     public:

   364       typedef T ValueType;

   365       typedef Edge KeyType;

   367       EdgeMap(const SmartGraph &_G) :

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

   369       {

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

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

   372 	G->dyn_edge_maps.push_back(this);

   373       }

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

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

   376       {

   377 	G->dyn_edge_maps.push_back(this);

   378       }

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

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

   381       {

   382  	G->dyn_node_maps.push_back(this);

   383       }

   385       template<typename TT> friend class EdgeMap;

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

   388       ///

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

   390 	DynMapBase<Edge>(*m.G)

   391       {

   392 	G->dyn_node_maps.push_back(this);

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

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

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

   396 	    i++)

   397 	  container.push_back(*i);

   398       }

   399       ~EdgeMap()

   400       {

   401 	if(G) {

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

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

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

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

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

   407 	  if(*i==this) {

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

   409 	    G->dyn_edge_maps.pop_back();

   410 	  }

   411 	}

   412       }

   414       void add(const Edge k)

   415       {

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

   417       }

   418       void erase(const Edge) { }

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

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

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

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

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

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

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

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

   429       ///cause serious problem.

   430       ///\todo Is this really so?

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

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

   433       {

   434 	container = m.container;

   435 	return *this;

   436       }

   437       template<typename TT>

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

   439       {

   440 	copy(m.container.begin(), m.container.end(), container.begin());

   441 	return *this;

   442       }

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

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

   446     };

   448   };

   450   ///Graph for bidirectional edges.

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

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

   454   ///of oppositely directed edges.

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

   456   ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"

   457   ///that complements this

   458   ///feature by

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

   460   ///\ref GraphSkeleton::EdgeMap "EdgeMap"

   461   ///can be used

   462   ///as well.

   463   ///

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

   465   ///using \ref opposite.

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

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

   468   //\sa \ref SmartGraph.

   470   class SymSmartGraph : public SmartGraph

   471   {

   472   public:

   473     template<typename T> class SymEdgeMap;

   474     template<typename T> friend class SymEdgeMap;

   476     SymSmartGraph() : SmartGraph() { }

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

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

   479     Edge addEdge(Node u, Node v)

   480     {

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

   482       SmartGraph::addEdge(v,u);

   483       return e;

   484     }

   486     ///The oppositely directed edge.

   488     ///Returns the oppositely directed

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

   490     Edge opposite(Edge e) const

   491     {

   492       Edge f;

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

   494       return f;

   495     }

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

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

   500     ///directed pairs of edges.

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

   502     {

   503       std::vector<T> container;

   505     public:

   506       typedef T ValueType;

   507       typedef Edge KeyType;

   509       SymEdgeMap(const SymSmartGraph &_G) :

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

   511       {

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

   513       }

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

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

   516       {

   517 	G->dyn_edge_maps.push_back(this);

   518       }

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

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

   522       {

   523  	G->dyn_node_maps.push_back(this);

   524       }

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

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

   529       ///

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

   532 	DynMapBase<SymEdge>(*m.G)

   533       {

   534 	G->dyn_node_maps.push_back(this);

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

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

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

   538 	    i++)

   539 	  container.push_back(*i);

   540       }

   542       ~SymEdgeMap()

   543       {

   544 	if(G) {

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

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

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

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

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

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

   551 	  if(*i==this) {

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

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

   554 	  }

   555 	}

   556       }

   558       void add(const Edge k)

   559       {

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

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

   562       }

   563       void erase(const Edge k) { }

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

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

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

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

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

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

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

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

   574       ///cause serious problem.

   575       ///\todo Is this really so?

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

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

   578       {

   579 	container = m.container;

   580 	return *this;

   581       }

   582       template<typename TT>

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

   584       {

   585 	copy(m.container.begin(), m.container.end(), container.begin());

   586 	return *this;

   587       }

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

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

   592     };

   594   };

   596   /// @}

   598 } //namespace hugo

   603 #endif //SMART_GRAPH_H

author	marci
	Fri, 30 Apr 2004 16:46:19 +0000
changeset 498	eb8bfa683d92
parent 456	02c28d3cf97b
child 503	769f31e9f7b0
permissions	-rw-r--r--