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

     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   class SmartGraph {

    33     struct NodeT

    34     {

    35       int first_in,first_out;

    36       NodeT() : first_in(-1), first_out(-1) {}

    37     };

    38     struct EdgeT

    39     {

    40       int head, tail, next_in, next_out;

    41       //FIXME: is this necessary?

    42       EdgeT() : next_in(-1), next_out(-1) {}

    43     };

    45     std::vector<NodeT> nodes;

    47     std::vector<EdgeT> edges;

    49     protected:

    51     template <typename Key> class DynMapBase

    52     {

    53     protected:

    54       const SmartGraph* G;

    55     public:

    56       virtual void add(const Key k) = 0;

    57       virtual void erase(const Key k) = 0;

    58       DynMapBase(const SmartGraph &_G) : G(&_G) {}

    59       virtual ~DynMapBase() {}

    60       friend class SmartGraph;

    61     };

    63   public:

    64     template <typename T> class EdgeMap;

    65     template <typename T> class EdgeMap;

    67     class Node;

    68     class Edge;

    70     //  protected:

    71     // HELPME:

    72   protected:

    73     ///\bug It must be public because of SymEdgeMap.

    74     ///

    75     mutable std::vector<DynMapBase<Node> * > dyn_node_maps;

    76     ///\bug It must be public because of SymEdgeMap.

    77     ///

    78     mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;

    80   public:

    82     class NodeIt;

    83     class EdgeIt;

    84     class OutEdgeIt;

    85     class InEdgeIt;

    87     template <typename T> class NodeMap;

    88     template <typename T> class EdgeMap;

    90   public:

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

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

    95     ~SmartGraph()

    96     {

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

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

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

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

   101     }

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

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

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

   107     ///its name would suggests...

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

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

   110     ///its name would suggests...

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

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

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

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

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

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

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

   122     NodeIt& first(NodeIt& v) const {

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

   124     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

   131 //     template< typename It >

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

   134 //     template< typename It >

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

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

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

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

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

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

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

   146     NodeIt& next(NodeIt& it) const {

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

   148       return it;

   149     }

   150     OutEdgeIt& next(OutEdgeIt& it) const

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

   152     InEdgeIt& next(InEdgeIt& it) const

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

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

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

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

   159     Node addNode() {

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

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

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

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

   166       return n;

   167     }

   169     Edge addEdge(Node u, Node v) {

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

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

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

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

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

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

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

   179       return e;

   180     }

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

   184     class Node {

   185       friend class SmartGraph;

   186       template <typename T> friend class NodeMap;

   188       friend class Edge;

   189       friend class OutEdgeIt;

   190       friend class InEdgeIt;

   191       friend class SymEdge;

   193     protected:

   194       int n;

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

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

   197     public:

   198       Node() {}

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

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

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

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

   203     };

   205     class NodeIt : public Node {

   206       friend class SmartGraph;

   207     public:

   208       NodeIt() : Node() { }

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

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

   211     };

   213     class Edge {

   214       friend class SmartGraph;

   215       template <typename T> friend class EdgeMap;

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

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

   220       friend class Node;

   221       friend class NodeIt;

   222     protected:

   223       int n;

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

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

   227     public:

   228       Edge() { }

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

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

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

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

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

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

   235       int &idref() {return n;}

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

   237     };

   239     class EdgeIt : public Edge {

   240       friend class SmartGraph;

   241     public:

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

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

   244       EdgeIt() : Edge() { }

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

   250     class OutEdgeIt : public Edge {

   251       friend class SmartGraph;

   252     public:

   253       OutEdgeIt() : Edge() { }

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

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

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

   258     };

   260     class InEdgeIt : public Edge {

   261       friend class SmartGraph;

   262     public:

   263       InEdgeIt() : Edge() { }

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

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

   266     };

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

   269     {

   270       std::vector<T> container;

   272     public:

   273       typedef T ValueType;

   274       typedef Node KeyType;

   276       NodeMap(const SmartGraph &_G) :

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

   278       {

   279 	G->dyn_node_maps.push_back(this);

   280       }

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

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

   283       {

   284 	G->dyn_node_maps.push_back(this);

   285       }

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

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

   289       {

   290  	G->dyn_node_maps.push_back(this);

   291       }

   293       template<typename TT> friend class NodeMap;

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

   296       ///

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

   298 	DynMapBase<Node>(*m.G)

   299       {

   300 	G->dyn_node_maps.push_back(this);

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

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

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

   304 	    i++)

   305 	  container.push_back(*i);

   306       }

   307       ~NodeMap()

   308       {

   309 	if(G) {

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

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

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

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

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

   315 	  if(*i==this) {

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

   317 	    G->dyn_node_maps.pop_back();

   318 	  }

   319 	}

   320       }

   322       void add(const Node k)

   323       {

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

   325       }

   327       void erase(const Node) { }

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

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

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

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

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

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

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

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

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

   339       ///cause serious problem.

   340       ///\todo Is this really so?

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

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

   343       {

   344 	container = m.container;

   345 	return *this;

   346       }

   347       template<typename TT>

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

   349       {

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

   351 	return *this;

   352       }

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

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

   356     };

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

   359     {

   360       std::vector<T> container;

   362     public:

   363       typedef T ValueType;

   364       typedef Edge KeyType;

   366       EdgeMap(const SmartGraph &_G) :

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

   368       {

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

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

   371 	G->dyn_edge_maps.push_back(this);

   372       }

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

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

   375       {

   376 	G->dyn_edge_maps.push_back(this);

   377       }

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

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

   380       {

   381  	G->dyn_node_maps.push_back(this);

   382       }

   384       template<typename TT> friend class EdgeMap;

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

   387       ///

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

   389 	DynMapBase<Edge>(*m.G)

   390       {

   391 	G->dyn_node_maps.push_back(this);

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

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

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

   395 	    i++)

   396 	  container.push_back(*i);

   397       }

   398       ~EdgeMap()

   399       {

   400 	if(G) {

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

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

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

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

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

   406 	  if(*i==this) {

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

   408 	    G->dyn_edge_maps.pop_back();

   409 	  }

   410 	}

   411       }

   413       void add(const Edge k)

   414       {

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

   416       }

   417       void erase(const Edge) { }

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

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

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

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

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

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

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

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

   428       ///cause serious problem.

   429       ///\todo Is this really so?

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

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

   432       {

   433 	container = m.container;

   434 	return *this;

   435       }

   436       template<typename TT>

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

   438       {

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

   440 	return *this;

   441       }

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

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

   445     };

   447   };

   449   ///Graph for bidirectional edges.

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

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

   453   ///of oppositely directed edges.

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

   455   ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"

   456   ///that complements this

   457   ///feature by

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

   459   ///\ref GraphSkeleton::EdgeMap "EdgeMap"

   460   ///can be used

   461   ///as well.

   462   ///

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

   464   ///using \ref opposite.

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

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

   467   //\sa \ref SmartGraph.

   469   class SymSmartGraph : public SmartGraph

   470   {

   471   public:

   472     template<typename T> class SymEdgeMap;

   473     template<typename T> friend class SymEdgeMap;

   475     SymSmartGraph() : SmartGraph() { }

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

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

   478     Edge addEdge(Node u, Node v)

   479     {

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

   481       SmartGraph::addEdge(v,u);

   482       return e;

   483     }

   485     ///The oppositely directed edge.

   487     ///Returns the oppositely directed

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

   489     Edge opposite(Edge e) const

   490     {

   491       Edge f;

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

   493       return f;

   494     }

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

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

   499     ///directed pairs of edges.

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

   501     {

   502       std::vector<T> container;

   504     public:

   505       typedef T ValueType;

   506       typedef Edge KeyType;

   508       SymEdgeMap(const SymSmartGraph &_G) :

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

   510       {

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

   512       }

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

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

   515       {

   516 	G->dyn_edge_maps.push_back(this);

   517       }

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

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

   521       {

   522  	G->dyn_node_maps.push_back(this);

   523       }

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

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

   528       ///

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

   531 	DynMapBase<SymEdge>(*m.G)

   532       {

   533 	G->dyn_node_maps.push_back(this);

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

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

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

   537 	    i++)

   538 	  container.push_back(*i);

   539       }

   541       ~SymEdgeMap()

   542       {

   543 	if(G) {

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

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

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

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

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

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

   550 	  if(*i==this) {

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

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

   553 	  }

   554 	}

   555       }

   557       void add(const Edge k)

   558       {

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

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

   561       }

   562       void erase(const Edge k) { }

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

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

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

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

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

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

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

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

   573       ///cause serious problem.

   574       ///\todo Is this really so?

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

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

   577       {

   578 	container = m.container;

   579 	return *this;

   580       }

   581       template<typename TT>

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

   583       {

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

   585 	return *this;

   586       }

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

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

   591     };

   593   };

   595   /// @}

   597 } //namespace hugo

   602 #endif //SMART_GRAPH_H

author	alpar
	Mon, 26 Apr 2004 17:33:51 +0000
changeset 425	4fbe868c1fb4
parent 407	e34e1bc610cf
child 456	02c28d3cf97b
permissions	-rw-r--r--