lemon-0.x: src/work/alpar/smart_graph.h@0c6bd3a98edf

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

     3 #ifndef HUGO_SMART_GRAPH_H

     4 #define HUGO_SMART_GRAPH_H

     6 #include <vector>

     7 #include <limits.h>

     9 #include <invalid.h>

    11 namespace hugo {

    13   class SymSmartGraph;

    15   ///A smart graph class.

    17   /// When you read this for the first time,

    18   /// please send an e-mail to alpar\@cs.elte.hu.

    19   ///

    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   ///Apart from this 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     //     class Node { int n; };

    83     //     class NodeIt : public Node { };

    84     //     class Edge { int n; };

    85     //     class EdgeIt : public Edge {};

    86     //     class OutEdgeIt : public Edge {};

    87     //     class InEdgeIt : public Edge {};

    88     //     class SymEdge;

    90     template <typename T> class NodeMap;

    91     template <typename T> class EdgeMap;

    93   public:

    95     /* default constructor */

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

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

   100     ~SmartGraph()

   101     {

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

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

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

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

   106     }

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

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

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

   112     ///its name would suggests...

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

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

   115     ///its name would suggests...

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

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

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

   121     // Marci

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

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

   124 //     //Node aNode(const SymEdge& e) const { return e.aNode(); }

   126     // Marci

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

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

   129 //     //Node bNode(const SymEdge& e) const { return e.bNode(); }

   131     NodeIt& first(NodeIt& v) const {

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

   133     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

   140     template< typename It >

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

   143     template< typename It >

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

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

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

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

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

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

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

   155     NodeIt& next(NodeIt& it) const {

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

   157       return it;

   158     }

   159     OutEdgeIt& next(OutEdgeIt& it) const

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

   161     InEdgeIt& next(InEdgeIt& it) const

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

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

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

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

   168     Node addNode() {

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

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

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

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

   175       return n;

   176     }

   178     Edge addEdge(Node u, Node v) {

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

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

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

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

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

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

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

   188       return e;

   189     }

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

   193     class Node {

   194       friend class SmartGraph;

   195       template <typename T> friend class NodeMap;

   197       friend class Edge;

   198       friend class OutEdgeIt;

   199       friend class InEdgeIt;

   200       friend class SymEdge;

   202     protected:

   203       int n;

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

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

   206     public:

   207       Node() {}

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

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

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

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

   212     };

   214     class NodeIt : public Node {

   215       friend class SmartGraph;

   216     public:

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

   218       NodeIt() : Node() { }

   219     };

   221     class Edge {

   222       friend class SmartGraph;

   223       template <typename T> friend class EdgeMap;

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

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

   228       friend class Node;

   229       friend class NodeIt;

   230     protected:

   231       int n;

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

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

   235     public:

   236       Edge() { }

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

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

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

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

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

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

   243       int &idref() {return n;}

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

   245     };

   247     class EdgeIt : public Edge {

   248       friend class SmartGraph;

   249     public:

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

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

   252       EdgeIt() : Edge() { }

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

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

   255       int &idref() {return n;}

   256     };

   258     class OutEdgeIt : public Edge {

   259       friend class SmartGraph;

   260     public:

   261       OutEdgeIt() : Edge() { }

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

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

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

   266     };

   268     class InEdgeIt : public Edge {

   269       friend class SmartGraph;

   270     public:

   271       InEdgeIt() : Edge() { }

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

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

   274     };

   276     // Map types

   278 //     // Static Maps are not necessary.

   279 //     template <typename T>

   280 //     class NodeMap {

   281 //       const SmartGraph& G;

   282 //       std::vector<T> container;

   283 //     public:

   284 //       typedef T ValueType;

   285 //       typedef Node KeyType;

   286 //       NodeMap(const SmartGraph& _G) : G(_G), container(G.maxNodeId()) { }

   287 //       NodeMap(const SmartGraph& _G, T a) :

   288 // 	G(_G), container(G.maxNodeId(), a) { }

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

   290 //       T get(Node n) const { return container[n.n]; }

   291 //       T& operator[](Node n) { return container[n.n]; }

   292 //       const T& operator[](Node n) const { return container[n.n]; }

   293 //       void update() { container.resize(G.maxNodeId()); }

   294 //       void update(T a) { container.resize(G.maxNodeId(), a); }

   295 //     };

   297 //     template <typename T>

   298 //     class EdgeMap {

   299 //       const SmartGraph& G;

   300 //       std::vector<T> container;

   301 //     public:

   302 //       typedef T ValueType;

   303 //       typedef Edge KeyType;

   304 //       EdgeMap(const SmartGraph& _G) : G(_G), container(G.maxEdgeId()) { }

   305 //       EdgeMap(const SmartGraph& _G, T a) :

   306 // 	G(_G), container(G.maxEdgeId(), a) { }

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

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

   309 //       T& operator[](Edge e) { return container[e.n]; }

   310 //       const T& operator[](Edge e) const { return container[e.n]; }

   311 //       void update() { container.resize(G.maxEdgeId()); }

   312 //       void update(T a) { container.resize(G.maxEdgeId(), a); }

   313 //     };

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

   316     {

   317       std::vector<T> container;

   319     public:

   320       typedef T ValueType;

   321       typedef Node KeyType;

   323       NodeMap(const SmartGraph &_G) :

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

   325       {

   326 	G->dyn_node_maps.push_back(this);

   327       }

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

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

   330       {

   331 	G->dyn_node_maps.push_back(this);

   332       }

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

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

   336       {

   337  	G->dyn_node_maps.push_back(this);

   338       }

   340       template<typename TT> friend class NodeMap;

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

   343       ///

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

   345 	DynMapBase<Node>(*m.G)

   346       {

   347 	G->dyn_node_maps.push_back(this);

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

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

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

   351 	    i++)

   352 	  container.push_back(*i);

   353       }

   354       ~NodeMap()

   355       {

   356 	if(G) {

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

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

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

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

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

   362 	  if(*i==this) {

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

   364 	    G->dyn_node_maps.pop_back();

   365 	  }

   366 	}

   367       }

   369       void add(const Node k)

   370       {

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

   372       }

   374       void erase(const Node) { }

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

   377       //T get(Node n) const { return container[n.n]; }

   378       //Hajjaj:

   379       //T& operator[](Node n) { return container[n.n]; }

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

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

   382       //const T& operator[](Node n) const { return container[n.n]; }

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

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

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

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

   388       ///cause serious problem.

   389       ///\todo Is this really so?

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

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

   392       {

   393 	container = m.container;

   394 	return *this;

   395       }

   396       template<typename TT>

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

   398       {

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

   400 	return *this;

   401       }

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

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

   405     };

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

   408     {

   409       std::vector<T> container;

   411     public:

   412       typedef T ValueType;

   413       typedef Edge KeyType;

   415       EdgeMap(const SmartGraph &_G) :

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

   417       {

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

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

   420 	G->dyn_edge_maps.push_back(this);

   421       }

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

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

   424       {

   425 	G->dyn_edge_maps.push_back(this);

   426       }

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

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

   429       {

   430  	G->dyn_node_maps.push_back(this);

   431       }

   433       template<typename TT> friend class EdgeMap;

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

   436       ///

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

   438 	DynMapBase<Edge>(*m.G)

   439       {

   440 	G->dyn_node_maps.push_back(this);

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

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

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

   444 	    i++)

   445 	  container.push_back(*i);

   446       }

   447       ~EdgeMap()

   448       {

   449 	if(G) {

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

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

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

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

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

   455 	  if(*i==this) {

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

   457 	    G->dyn_edge_maps.pop_back();

   458 	  }

   459 	}

   460       }

   462       void add(const Edge k)

   463       {

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

   465       }

   466       void erase(const Edge) { }

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

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

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

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

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

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

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

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

   477       ///cause serious problem.

   478       ///\todo Is this really so?

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

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

   481       {

   482 	container = m.container;

   483 	return *this;

   484       }

   485       template<typename TT>

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

   487       {

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

   489 	return *this;

   490       }

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

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

   494     };

   496   };

   498   ///Graph for bidirectional edges.

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

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

   502   ///of oppositely directed edges.

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

   504   ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"

   505   ///that complements this

   506   ///feature by

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

   508   ///\ref GraphSkeleton::EdgeMap "EdgeMap"

   509   ///can be used

   510   ///as well.

   511   ///

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

   513   ///using \ref opposite.

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

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

   516   //\sa \ref SmartGraph.

   518   class SymSmartGraph : public SmartGraph

   519   {

   520   public:

   521     template<typename T> class SymEdgeMap;

   522     template<typename T> friend class SymEdgeMap;

   524     SymSmartGraph() : SmartGraph() { }

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

   526     Edge addEdge(Node u, Node v)

   527     {

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

   529       SmartGraph::addEdge(v,u);

   530       return e;

   531     }

   533     ///The oppositely directed edge.

   535     ///Returns the oppositely directed

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

   537     Edge opposite(Edge e) const

   538     {

   539       Edge f;

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

   541       return f;

   542     }

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

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

   547     ///directed pairs of edges.

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

   549     {

   550       std::vector<T> container;

   552     public:

   553       typedef T ValueType;

   554       typedef Edge KeyType;

   556       SymEdgeMap(const SymSmartGraph &_G) :

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

   558       {

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

   560       }

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

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

   563       {

   564 	G->dyn_edge_maps.push_back(this);

   565       }

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

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

   569       {

   570  	G->dyn_node_maps.push_back(this);

   571       }

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

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

   576       ///

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

   579 	DynMapBase<SymEdge>(*m.G)

   580       {

   581 	G->dyn_node_maps.push_back(this);

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

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

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

   585 	    i++)

   586 	  container.push_back(*i);

   587       }

   589       ~SymEdgeMap()

   590       {

   591 	if(G) {

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

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

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

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

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

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

   598 	  if(*i==this) {

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

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

   601 	  }

   602 	}

   603       }

   605       void add(const Edge k)

   606       {

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

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

   609       }

   610       void erase(const Edge k) { }

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

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

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

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

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

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

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

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

   621       ///cause serious problem.

   622       ///\todo Is this really so?

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

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

   625       {

   626 	container = m.container;

   627 	return *this;

   628       }

   629       template<typename TT>

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

   631       {

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

   633 	return *this;

   634       }

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

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

   639     };

   641   };

   644 } //namespace hugo

   649 #endif //SMART_GRAPH_H

author	alpar
	Sat, 20 Mar 2004 21:38:16 +0000
changeset 222	0c6bd3a98edf
parent 209	9a37b8d02d74
child 242	b255f25ad394
permissions	-rw-r--r--