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

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

     3 #ifndef HUGO_SMART_GRAPH_H

     4 #define HUGO_SMART_GRAPH_H

     6 ///\file

     7 ///\brief SmartGraph and SymSmartGraph classes.

     9 #include <vector>

    10 #include <limits.h>

    12 #include "invalid.h"

    14 namespace hugo {

    16   class SymSmartGraph;

    18   ///A smart graph class.

    20   ///This is a simple and fast graph implementation.

    21   ///It is also quite memory efficient, but at the price

    22   ///that <b> it does not support node and edge deletion</b>.

    23   ///It conforms to the graph interface documented under

    24   ///the description of \ref GraphSkeleton.

    25   ///\sa \ref GraphSkeleton.

    26   class SmartGraph {

    28     struct NodeT

    29     {

    30       int first_in,first_out;

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

    32     };

    33     struct EdgeT

    34     {

    35       int head, tail, next_in, next_out;

    36       //FIXME: is this necessary?

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

    38     };

    40     std::vector<NodeT> nodes;

    42     std::vector<EdgeT> edges;

    44     protected:

    46     template <typename Key> class DynMapBase

    47     {

    48     protected:

    49       const SmartGraph* G;

    50     public:

    51       virtual void add(const Key k) = NULL;

    52       virtual void erase(const Key k) = NULL;

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

    54       virtual ~DynMapBase() {}

    55       friend class SmartGraph;

    56     };

    58   public:

    59     template <typename T> class EdgeMap;

    60     template <typename T> class EdgeMap;

    62     class Node;

    63     class Edge;

    65     //  protected:

    66     // HELPME:

    67   protected:

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

    69     ///

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

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

    72     ///

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

    75   public:

    77     class NodeIt;

    78     class EdgeIt;

    79     class OutEdgeIt;

    80     class InEdgeIt;

    82     template <typename T> class NodeMap;

    83     template <typename T> class EdgeMap;

    85   public:

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

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

    90     ~SmartGraph()

    91     {

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

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

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

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

    96     }

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

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

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

   102     ///its name would suggests...

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

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

   105     ///its name would suggests...

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

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

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

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

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

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

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

   117     NodeIt& first(NodeIt& v) const {

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

   119     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

   126     template< typename It >

   127     It first() const { It e; first(e); return e; }

   129     template< typename It >

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

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

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

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

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

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

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

   141     NodeIt& next(NodeIt& it) const {

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

   143       return it;

   144     }

   145     OutEdgeIt& next(OutEdgeIt& it) const

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

   147     InEdgeIt& next(InEdgeIt& it) const

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

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

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

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

   154     Node addNode() {

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

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

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

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

   161       return n;

   162     }

   164     Edge addEdge(Node u, Node v) {

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

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

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

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

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

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

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

   174       return e;

   175     }

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

   179     class Node {

   180       friend class SmartGraph;

   181       template <typename T> friend class NodeMap;

   183       friend class Edge;

   184       friend class OutEdgeIt;

   185       friend class InEdgeIt;

   186       friend class SymEdge;

   188     protected:

   189       int n;

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

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

   192     public:

   193       Node() {}

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

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

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

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

   198     };

   200     class NodeIt : public Node {

   201       friend class SmartGraph;

   202     public:

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

   204       NodeIt() : Node() { }

   205     };

   207     class Edge {

   208       friend class SmartGraph;

   209       template <typename T> friend class EdgeMap;

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

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

   214       friend class Node;

   215       friend class NodeIt;

   216     protected:

   217       int n;

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

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

   221     public:

   222       Edge() { }

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

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

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

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

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

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

   229       int &idref() {return n;}

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

   231     };

   233     class EdgeIt : public Edge {

   234       friend class SmartGraph;

   235     public:

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

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

   238       EdgeIt() : Edge() { }

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

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

   241       int &idref() {return n;}

   242     };

   244     class OutEdgeIt : public Edge {

   245       friend class SmartGraph;

   246     public:

   247       OutEdgeIt() : Edge() { }

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

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

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

   252     };

   254     class InEdgeIt : public Edge {

   255       friend class SmartGraph;

   256     public:

   257       InEdgeIt() : Edge() { }

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

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

   260     };

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

   263     {

   264       std::vector<T> container;

   266     public:

   267       typedef T ValueType;

   268       typedef Node KeyType;

   270       NodeMap(const SmartGraph &_G) :

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

   272       {

   273 	G->dyn_node_maps.push_back(this);

   274       }

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

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

   277       {

   278 	G->dyn_node_maps.push_back(this);

   279       }

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

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

   283       {

   284  	G->dyn_node_maps.push_back(this);

   285       }

   287       template<typename TT> friend class NodeMap;

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

   290       ///

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

   292 	DynMapBase<Node>(*m.G)

   293       {

   294 	G->dyn_node_maps.push_back(this);

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

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

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

   298 	    i++)

   299 	  container.push_back(*i);

   300       }

   301       ~NodeMap()

   302       {

   303 	if(G) {

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

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

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

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

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

   309 	  if(*i==this) {

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

   311 	    G->dyn_node_maps.pop_back();

   312 	  }

   313 	}

   314       }

   316       void add(const Node k)

   317       {

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

   319       }

   321       void erase(const Node) { }

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

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

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

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

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

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

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

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

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

   333       ///cause serious problem.

   334       ///\todo Is this really so?

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

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

   337       {

   338 	container = m.container;

   339 	return *this;

   340       }

   341       template<typename TT>

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

   343       {

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

   345 	return *this;

   346       }

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

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

   350     };

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

   353     {

   354       std::vector<T> container;

   356     public:

   357       typedef T ValueType;

   358       typedef Edge KeyType;

   360       EdgeMap(const SmartGraph &_G) :

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

   362       {

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

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

   365 	G->dyn_edge_maps.push_back(this);

   366       }

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

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

   369       {

   370 	G->dyn_edge_maps.push_back(this);

   371       }

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

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

   374       {

   375  	G->dyn_node_maps.push_back(this);

   376       }

   378       template<typename TT> friend class EdgeMap;

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

   381       ///

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

   383 	DynMapBase<Edge>(*m.G)

   384       {

   385 	G->dyn_node_maps.push_back(this);

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

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

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

   389 	    i++)

   390 	  container.push_back(*i);

   391       }

   392       ~EdgeMap()

   393       {

   394 	if(G) {

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

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

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

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

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

   400 	  if(*i==this) {

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

   402 	    G->dyn_edge_maps.pop_back();

   403 	  }

   404 	}

   405       }

   407       void add(const Edge k)

   408       {

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

   410       }

   411       void erase(const Edge) { }

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

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

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

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

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

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

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

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

   422       ///cause serious problem.

   423       ///\todo Is this really so?

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

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

   426       {

   427 	container = m.container;

   428 	return *this;

   429       }

   430       template<typename TT>

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

   432       {

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

   434 	return *this;

   435       }

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

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

   439     };

   441   };

   443   ///Graph for bidirectional edges.

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

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

   447   ///of oppositely directed edges.

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

   449   ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"

   450   ///that complements this

   451   ///feature by

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

   453   ///\ref GraphSkeleton::EdgeMap "EdgeMap"

   454   ///can be used

   455   ///as well.

   456   ///

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

   458   ///using \ref opposite.

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

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

   461   //\sa \ref SmartGraph.

   463   class SymSmartGraph : public SmartGraph

   464   {

   465   public:

   466     template<typename T> class SymEdgeMap;

   467     template<typename T> friend class SymEdgeMap;

   469     SymSmartGraph() : SmartGraph() { }

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

   471     Edge addEdge(Node u, Node v)

   472     {

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

   474       SmartGraph::addEdge(v,u);

   475       return e;

   476     }

   478     ///The oppositely directed edge.

   480     ///Returns the oppositely directed

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

   482     Edge opposite(Edge e) const

   483     {

   484       Edge f;

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

   486       return f;

   487     }

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

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

   492     ///directed pairs of edges.

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

   494     {

   495       std::vector<T> container;

   497     public:

   498       typedef T ValueType;

   499       typedef Edge KeyType;

   501       SymEdgeMap(const SymSmartGraph &_G) :

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

   503       {

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

   505       }

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

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

   508       {

   509 	G->dyn_edge_maps.push_back(this);

   510       }

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

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

   514       {

   515  	G->dyn_node_maps.push_back(this);

   516       }

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

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

   521       ///

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

   524 	DynMapBase<SymEdge>(*m.G)

   525       {

   526 	G->dyn_node_maps.push_back(this);

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

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

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

   530 	    i++)

   531 	  container.push_back(*i);

   532       }

   534       ~SymEdgeMap()

   535       {

   536 	if(G) {

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

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

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

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

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

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

   543 	  if(*i==this) {

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

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

   546 	  }

   547 	}

   548       }

   550       void add(const Edge k)

   551       {

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

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

   554       }

   555       void erase(const Edge k) { }

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

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

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

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

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

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

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

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

   566       ///cause serious problem.

   567       ///\todo Is this really so?

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

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

   570       {

   571 	container = m.container;

   572 	return *this;

   573       }

   574       template<typename TT>

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

   576       {

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

   578 	return *this;

   579       }

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

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

   584     };

   586   };

   589 } //namespace hugo

   594 #endif //SMART_GRAPH_H

author	klao
	Mon, 05 Apr 2004 18:24:37 +0000
changeset 310	76c005b15354
parent 253	f45703336699
child 353	eeae2f4a0d74
permissions	-rw-r--r--