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

     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   ///This is a simple and fast graph implementation.

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

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

    20   ///Apart from this it conforms to the graph interface documented under

    21   ///the description of \ref GraphSkeleton.

    22   ///\sa \ref GraphSkeleton.

    23   class SmartGraph {

    25     struct NodeT

    26     {

    27       int first_in,first_out;

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

    29     };

    30     struct EdgeT

    31     {

    32       int head, tail, next_in, next_out;

    33       //FIXME: is this necessary?

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

    35     };

    37     std::vector<NodeT> nodes;

    39     std::vector<EdgeT> edges;

    41     protected:

    43     template <typename Key> class DynMapBase

    44     {

    45     protected:

    46       const SmartGraph* G;

    47     public:

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

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

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

    51       virtual ~DynMapBase() {}

    52       friend class SmartGraph;

    53     };

    55   public:

    56     template <typename T> class EdgeMap;

    57     template <typename T> class EdgeMap;

    59     class Node;

    60     class Edge;

    62     //  protected:

    63     // HELPME:

    64   protected:

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

    66     ///

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

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

    69     ///

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

    72   public:

    74     class NodeIt;

    75     class EdgeIt;

    76     class OutEdgeIt;

    77     class InEdgeIt;

    79     //     class Node { int n; };

    80     //     class NodeIt : public Node { };

    81     //     class Edge { int n; };

    82     //     class EdgeIt : public Edge {};

    83     //     class OutEdgeIt : public Edge {};

    84     //     class InEdgeIt : public Edge {};

    85     //     class SymEdge;

    87     template <typename T> class NodeMap;

    88     template <typename T> class EdgeMap;

    90   public:

    92     /* default constructor */

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

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

    97     ~SmartGraph()

    98     {

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

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

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

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

   103     }

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

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

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

   109     ///its name would suggests...

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

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

   112     ///its name would suggests...

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

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

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

   118     // Marci

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

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

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

   123     // Marci

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

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

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

   128     NodeIt& first(NodeIt& v) const {

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

   130     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

   137     template< typename It >

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

   140     template< typename It >

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

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

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

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

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

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

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

   152     NodeIt& next(NodeIt& it) const {

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

   154       return it;

   155     }

   156     OutEdgeIt& next(OutEdgeIt& it) const

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

   158     InEdgeIt& next(InEdgeIt& it) const

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

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

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

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

   165     Node addNode() {

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

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

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

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

   172       return n;

   173     }

   175     Edge addEdge(Node u, Node v) {

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

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

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

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

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

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

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

   185       return e;

   186     }

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

   190     class Node {

   191       friend class SmartGraph;

   192       template <typename T> friend class NodeMap;

   194       friend class Edge;

   195       friend class OutEdgeIt;

   196       friend class InEdgeIt;

   197       friend class SymEdge;

   199     protected:

   200       int n;

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

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

   203     public:

   204       Node() {}

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

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

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

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

   209     };

   211     class NodeIt : public Node {

   212       friend class SmartGraph;

   213     public:

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

   215       NodeIt() : Node() { }

   216     };

   218     class Edge {

   219       friend class SmartGraph;

   220       template <typename T> friend class EdgeMap;

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

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

   225       friend class Node;

   226       friend class NodeIt;

   227     protected:

   228       int n;

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

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

   232     public:

   233       Edge() { }

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

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

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

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

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

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

   240       int &idref() {return n;}

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

   242     };

   244     class EdgeIt : public Edge {

   245       friend class SmartGraph;

   246     public:

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

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

   249       EdgeIt() : Edge() { }

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

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

   252       int &idref() {return n;}

   253     };

   255     class OutEdgeIt : public Edge {

   256       friend class SmartGraph;

   257     public:

   258       OutEdgeIt() : Edge() { }

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

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

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

   263     };

   265     class InEdgeIt : public Edge {

   266       friend class SmartGraph;

   267     public:

   268       InEdgeIt() : Edge() { }

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

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

   271     };

   273     // Map types

   275 //     // Static Maps are not necessary.

   276 //     template <typename T>

   277 //     class NodeMap {

   278 //       const SmartGraph& G;

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

   280 //     public:

   281 //       typedef T ValueType;

   282 //       typedef Node KeyType;

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

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

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

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

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

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

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

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

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

   292 //     };

   294 //     template <typename T>

   295 //     class EdgeMap {

   296 //       const SmartGraph& G;

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

   298 //     public:

   299 //       typedef T ValueType;

   300 //       typedef Edge KeyType;

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

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

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

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

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

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

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

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

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

   310 //     };

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

   313     {

   314       std::vector<T> container;

   316     public:

   317       typedef T ValueType;

   318       typedef Node KeyType;

   320       NodeMap(const SmartGraph &_G) :

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

   322       {

   323 	G->dyn_node_maps.push_back(this);

   324       }

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

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

   327       {

   328 	G->dyn_node_maps.push_back(this);

   329       }

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

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

   333       {

   334  	G->dyn_node_maps.push_back(this);

   335       }

   337       template<typename TT> friend class NodeMap;

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

   340       ///

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

   342 	DynMapBase<Node>(*m.G)

   343       {

   344 	G->dyn_node_maps.push_back(this);

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

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

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

   348 	    i++)

   349 	  container.push_back(*i);

   350       }

   351       ~NodeMap()

   352       {

   353 	if(G) {

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

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

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

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

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

   359 	  if(*i==this) {

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

   361 	    G->dyn_node_maps.pop_back();

   362 	  }

   363 	}

   364       }

   366       void add(const Node k)

   367       {

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

   369       }

   371       void erase(const Node k) { }

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

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

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

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

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

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

   380       ///cause serious problem.

   381       ///\todo Is this really so?

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

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

   384       {

   385 	container = m.container;

   386 	return *this;

   387       }

   388       template<typename TT>

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

   390       {

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

   392 	return *this;

   393       }

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

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

   397     };

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

   400     {

   401       std::vector<T> container;

   403     public:

   404       typedef T ValueType;

   405       typedef Edge KeyType;

   407       EdgeMap(const SmartGraph &_G) :

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

   409       {

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

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

   412 	G->dyn_edge_maps.push_back(this);

   413       }

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

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

   416       {

   417 	G->dyn_edge_maps.push_back(this);

   418       }

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

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

   421       {

   422  	G->dyn_node_maps.push_back(this);

   423       }

   425       template<typename TT> friend class EdgeMap;

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

   428       ///

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

   430 	DynMapBase<Edge>(*m.G)

   431       {

   432 	G->dyn_node_maps.push_back(this);

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

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

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

   436 	    i++)

   437 	  container.push_back(*i);

   438       }

   439       ~EdgeMap()

   440       {

   441 	if(G) {

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

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

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

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

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

   447 	  if(*i==this) {

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

   449 	    G->dyn_edge_maps.pop_back();

   450 	  }

   451 	}

   452       }

   454       void add(const Edge k)

   455       {

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

   457       }

   458       void erase(const Edge k) { }

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

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

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

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

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

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

   467       ///cause serious problem.

   468       ///\todo Is this really so?

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

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

   471       {

   472 	container = m.container;

   473 	return *this;

   474       }

   475       template<typename TT>

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

   477       {

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

   479 	return *this;

   480       }

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

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

   484     };

   486   };

   488   ///Graph for bidirectional edges.

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

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

   492   ///of oppositely directed edges.

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

   494   ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"

   495   ///that complements this

   496   ///feature by

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

   498   ///\ref GraphSkeleton::EdgeMap "EdgeMap"

   499   ///can be used

   500   ///as well.

   501   ///

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

   503   ///using \ref opposite.

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

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

   506   //\sa \ref SmartGraph.

   508   class SymSmartGraph : public SmartGraph

   509   {

   510   public:

   511     template<typename T> class SymEdgeMap;

   512     template<typename T> friend class SymEdgeMap;

   514     SymSmartGraph() : SmartGraph() { }

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

   516     Edge addEdge(Node u, Node v)

   517     {

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

   519       SmartGraph::addEdge(v,u);

   520       return e;

   521     }

   523     ///The oppositely directed edge.

   525     ///Returns the oppositely directed

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

   527     Edge opposite(Edge e) const

   528     {

   529       Edge f;

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

   531       return f;

   532     }

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

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

   537     ///directed pairs of edges.

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

   539     {

   540       std::vector<T> container;

   542     public:

   543       typedef T ValueType;

   544       typedef Edge KeyType;

   546       SymEdgeMap(const SymSmartGraph &_G) :

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

   548       {

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

   550       }

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

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

   553       {

   554 	G->dyn_edge_maps.push_back(this);

   555       }

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

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

   559       {

   560  	G->dyn_node_maps.push_back(this);

   561       }

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

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

   566       ///

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

   569 	DynMapBase<SymEdge>(*m.G)

   570       {

   571 	G->dyn_node_maps.push_back(this);

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

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

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

   575 	    i++)

   576 	  container.push_back(*i);

   577       }

   579       ~SymEdgeMap()

   580       {

   581 	if(G) {

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

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

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

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

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

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

   588 	  if(*i==this) {

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

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

   591 	  }

   592 	}

   593       }

   595       void add(const Edge k)

   596       {

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

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

   599       }

   600       void erase(const Edge k) { }

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

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

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

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

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

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

   609       ///cause serious problem.

   610       ///\todo Is this really so?

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

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

   613       {

   614 	container = m.container;

   615 	return *this;

   616       }

   617       template<typename TT>

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

   619       {

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

   621 	return *this;

   622       }

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

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

   627     };

   629   };

   632 } //namespace hugo

   637 #endif //SMART_GRAPH_H

author	alpar
	Mon, 15 Mar 2004 16:30:20 +0000
changeset 186	47cd1716870e
parent 185	259540358bbf
child 187	35a2c1fd5d73
permissions	-rw-r--r--