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

     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 k) { }

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

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

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

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

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

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

   383       ///cause serious problem.

   384       ///\todo Is this really so?

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

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

   387       {

   388 	container = m.container;

   389 	return *this;

   390       }

   391       template<typename TT>

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

   393       {

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

   395 	return *this;

   396       }

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

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

   400     };

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

   403     {

   404       std::vector<T> container;

   406     public:

   407       typedef T ValueType;

   408       typedef Edge KeyType;

   410       EdgeMap(const SmartGraph &_G) :

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

   412       {

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

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

   415 	G->dyn_edge_maps.push_back(this);

   416       }

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

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

   419       {

   420 	G->dyn_edge_maps.push_back(this);

   421       }

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

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

   424       {

   425  	G->dyn_node_maps.push_back(this);

   426       }

   428       template<typename TT> friend class EdgeMap;

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

   431       ///

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

   433 	DynMapBase<Edge>(*m.G)

   434       {

   435 	G->dyn_node_maps.push_back(this);

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

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

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

   439 	    i++)

   440 	  container.push_back(*i);

   441       }

   442       ~EdgeMap()

   443       {

   444 	if(G) {

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

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

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

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

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

   450 	  if(*i==this) {

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

   452 	    G->dyn_edge_maps.pop_back();

   453 	  }

   454 	}

   455       }

   457       void add(const Edge k)

   458       {

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

   460       }

   461       void erase(const Edge k) { }

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

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

   465       T& operator[](Edge n) { return container[n.n]; }

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

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

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

   470       ///cause serious problem.

   471       ///\todo Is this really so?

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

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

   474       {

   475 	container = m.container;

   476 	return *this;

   477       }

   478       template<typename TT>

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

   480       {

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

   482 	return *this;

   483       }

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

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

   487     };

   489   };

   491   ///Graph for bidirectional edges.

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

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

   495   ///of oppositely directed edges.

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

   497   ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"

   498   ///that complements this

   499   ///feature by

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

   501   ///\ref GraphSkeleton::EdgeMap "EdgeMap"

   502   ///can be used

   503   ///as well.

   504   ///

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

   506   ///using \ref opposite.

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

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

   509   //\sa \ref SmartGraph.

   511   class SymSmartGraph : public SmartGraph

   512   {

   513   public:

   514     template<typename T> class SymEdgeMap;

   515     template<typename T> friend class SymEdgeMap;

   517     SymSmartGraph() : SmartGraph() { }

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

   519     Edge addEdge(Node u, Node v)

   520     {

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

   522       SmartGraph::addEdge(v,u);

   523       return e;

   524     }

   526     ///The oppositely directed edge.

   528     ///Returns the oppositely directed

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

   530     Edge opposite(Edge e) const

   531     {

   532       Edge f;

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

   534       return f;

   535     }

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

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

   540     ///directed pairs of edges.

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

   542     {

   543       std::vector<T> container;

   545     public:

   546       typedef T ValueType;

   547       typedef Edge KeyType;

   549       SymEdgeMap(const SymSmartGraph &_G) :

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

   551       {

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

   553       }

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

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

   556       {

   557 	G->dyn_edge_maps.push_back(this);

   558       }

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

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

   562       {

   563  	G->dyn_node_maps.push_back(this);

   564       }

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

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

   569       ///

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

   572 	DynMapBase<SymEdge>(*m.G)

   573       {

   574 	G->dyn_node_maps.push_back(this);

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

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

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

   578 	    i++)

   579 	  container.push_back(*i);

   580       }

   582       ~SymEdgeMap()

   583       {

   584 	if(G) {

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

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

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

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

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

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

   591 	  if(*i==this) {

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

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

   594 	  }

   595 	}

   596       }

   598       void add(const Edge k)

   599       {

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

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

   602       }

   603       void erase(const Edge k) { }

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

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

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

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

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

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

   612       ///cause serious problem.

   613       ///\todo Is this really so?

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

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

   616       {

   617 	container = m.container;

   618 	return *this;

   619       }

   620       template<typename TT>

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

   622       {

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

   624 	return *this;

   625       }

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

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

   630     };

   632   };

   635 } //namespace hugo

   640 #endif //SMART_GRAPH_H

author	marci
	Sat, 20 Mar 2004 11:19:00 +0000
changeset 212	c07e4dd32438
parent 187	35a2c1fd5d73
child 215	b3c4e6646f7f
permissions	-rw-r--r--