lemon-0.x: src/work/alpar/list_graph.h@ecebcedd8960

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

     3 #ifndef HUGO_SMART_GRAPH_H

     4 #define HUGO_SMART_GRAPH_H

     6 ///\file

     7 ///\brief ListGraph and SymListGraph classes.

     9 #include <vector>

    10 #include <limits.h>

    12 #include "invalid.h"

    14 namespace hugo {

    16   class SymListGraph;

    18   ///A smart graph class.

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

    21   ///

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

    23   ///the description of \ref GraphSkeleton.

    24   ///\sa \ref GraphSkeleton.

    25   class ListGraph {

    27     //Nodes are double linked.

    28     //The free nodes are only single linked using the "next" field.

    29     struct NodeT

    30     {

    31       int first_in,first_out;

    32       int prev, next;

    33       //      NodeT() {}

    34     };

    35     //Edges are double linked.

    36     //The free edges are only single linked using the "next_in" field.

    37     struct EdgeT

    38     {

    39       int head, tail;

    40       int prev_in, prev_out;

    41       int next_in, next_out;

    42       //FIXME: is this necessary?

    43       //      EdgeT() : next_in(-1), next_out(-1) prev_in(-1), prev_out(-1) {}

    44     };

    46     std::vector<NodeT> nodes;

    47     //The first node

    48     int first_node;

    49     //The first free node

    50     int first_free_node;

    51     std::vector<EdgeT> edges;

    52     //The first free edge

    53     int first_free_edge;

    55   protected:

    57     template <typename Key> class DynMapBase

    58     {

    59     protected:

    60       const ListGraph* G;

    61     public:

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

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

    64       DynMapBase(const ListGraph &_G) : G(&_G) {}

    65       virtual ~DynMapBase() {}

    66       friend class ListGraph;

    67     };

    69   public:

    70     template <typename T> class EdgeMap;

    71     template <typename T> class EdgeMap;

    73     class Node;

    74     class Edge;

    76     //  protected:

    77     // HELPME:

    78   protected:

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

    80     ///

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

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

    83     ///

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

    86   public:

    88     class NodeIt;

    89     class EdgeIt;

    90     class OutEdgeIt;

    91     class InEdgeIt;

    93     template <typename T> class NodeMap;

    94     template <typename T> class EdgeMap;

    96   public:

    98     ListGraph() : nodes(), first_node(-1),

    99 		  first_free_node(-1), edges(), first_free_edge(-1) {}

   100     ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node),

   101 				     first_free_node(_g.first_free_node),

   102 				     edges(_g.edges),

   103 				     first_free_edge(_g.first_free_edge) {}

   105     ~ListGraph()

   106     {

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

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

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

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

   111     }

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

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

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

   117     ///its name would suggests...

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

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

   120     ///its name would suggests...

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

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

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

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

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

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

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

   132     NodeIt& first(NodeIt& v) const {

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

   134     EdgeIt& first(EdgeIt& e) const {

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

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

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

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

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

   141 //     template< typename It >

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

   144 //     template< typename It >

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

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

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

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

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

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

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

   156     NodeIt& next(NodeIt& it) const {

   157       it.n=nodes[it.n].next;

   158       return it;

   159     }

   160     OutEdgeIt& next(OutEdgeIt& it) const

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

   162     InEdgeIt& next(InEdgeIt& it) const

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

   164     EdgeIt& next(EdgeIt& it) const {

   165       if(edges[it.n].next_in!=-1) {

   166 	it.n=edges[it.n].next_in;

   167       }

   168       else {

   169 	int n;

   170 	for(n=nodes[edges[it.n].head].next;

   171 	    n!=-1 && nodes[n].first_in == -1;

   172 	    n = nodes[n].next) ;

   173 	it.n = (n==-1)?-1:nodes[n].first_in;

   174       }

   175       return it;

   176     }

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

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

   181     /// Adds a new node to the graph.

   183     /// \todo It adds the nodes in a reversed order.

   184     /// (i.e. the lastly added node becomes the first.)

   185     Node addNode() {

   186       int n;

   188       if(first_free_node==-1)

   189 	{

   190 	  n = nodes.size();

   191 	  nodes.push_back(NodeT());

   192 	}

   193       else {

   194 	n = first_free_node;

   195 	first_free_node = nodes[n].next;

   196       }

   198       nodes[n].next = first_node;

   199       if(first_node != -1) nodes[first_node].prev = n;

   200       first_node = n;

   201       nodes[n].prev = -1;

   203       nodes[n].first_in = nodes[n].first_out = -1;

   205       Node nn; nn.n=n;

   207       //Update dynamic maps

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

   209 	  i!=dyn_node_maps.end(); ++i) (**i).add(nn);

   211       return nn;

   212     }

   214     Edge addEdge(Node u, Node v) {

   215       int n;

   217       if(first_free_edge==-1)

   218 	{

   219 	  n = edges.size();

   220 	  edges.push_back(EdgeT());

   221 	}

   222       else {

   223 	n = first_free_edge;

   224 	first_free_edge = edges[n].next_in;

   225       }

   227       edges[n].tail = u.n; edges[n].head = v.n;

   229       edges[n].next_out = nodes[u.n].first_out;

   230       if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;

   231       edges[n].next_in = nodes[v.n].first_in;

   232       if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;

   233       edges[n].prev_in = edges[n].prev_out = -1;

   235       nodes[u.n].first_out = nodes[v.n].first_in = n;

   237       Edge e; e.n=n;

   239       //Update dynamic maps

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

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

   243       return e;

   244     }

   246   private:

   247     void eraseEdge(int n) {

   249       if(edges[n].next_in!=-1)

   250 	edges[edges[n].next_in].prev_in = edges[n].prev_in;

   251       if(edges[n].prev_in!=-1)

   252 	edges[edges[n].prev_in].next_in = edges[n].next_in;

   253       else nodes[edges[n].head].first_in = edges[n].next_in;

   255       if(edges[n].next_out!=-1)

   256 	edges[edges[n].next_out].prev_out = edges[n].prev_out;

   257       if(edges[n].prev_out!=-1)

   258 	edges[edges[n].prev_out].next_out = edges[n].next_out;

   259       else nodes[edges[n].tail].first_out = edges[n].next_out;

   261       edges[n].next_in = first_free_edge;

   262       first_free_edge = -1;

   264       //Update dynamic maps

   265       Edge e; e.n=n;

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

   267 	  i!=dyn_edge_maps.end(); ++i) (**i).erase(e);

   268     }

   270   public:

   272     void erase(Node nn) {

   273       int n=nn.n;

   275       int m;

   276       while((m=nodes[n].first_in)!=-1) eraseEdge(m);

   277       while((m=nodes[n].first_out)!=-1) eraseEdge(m);

   279       if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;

   280       if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;

   281       else first_node = nodes[n].next;

   283       nodes[n].next = first_free_node;

   284       first_free_node = n;

   286       //Update dynamic maps

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

   288 	  i!=dyn_node_maps.end(); ++i) (**i).erase(nn);

   289     }

   291     void erase(Edge e) { eraseEdge(e.n); }

   293     ///\bug Dynamic maps must be updated!

   294     ///

   295     void clear() {

   296       nodes.clear();edges.clear();

   297       first_node=first_free_node=first_free_edge=-1;

   298     }

   300     class Node {

   301       friend class ListGraph;

   302       template <typename T> friend class NodeMap;

   304       friend class Edge;

   305       friend class OutEdgeIt;

   306       friend class InEdgeIt;

   307       friend class SymEdge;

   309     protected:

   310       int n;

   311       friend int ListGraph::id(Node v) const;

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

   313     public:

   314       Node() {}

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

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

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

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

   319     };

   321     class NodeIt : public Node {

   322       friend class ListGraph;

   323     public:

   324       NodeIt(const ListGraph& G) : Node(G.first_node) { }

   325       NodeIt() : Node() { }

   326     };

   328     class Edge {

   329       friend class ListGraph;

   330       template <typename T> friend class EdgeMap;

   332       //template <typename T> friend class SymListGraph::SymEdgeMap;

   333       //friend Edge SymListGraph::opposite(Edge) const;

   335       friend class Node;

   336       friend class NodeIt;

   337     protected:

   338       int n;

   339       friend int ListGraph::id(Edge e) const;

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

   342     public:

   343       Edge() { }

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

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

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

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

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

   349       ///make class \c SymListGraph::SymEdgeMap friend of Edge

   350       int &idref() {return n;}

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

   352     };

   354     class EdgeIt : public Edge {

   355       friend class ListGraph;

   356     public:

   357       EdgeIt(const ListGraph& G) : Edge() {

   358       	int m;

   359 	for(m=G.first_node;

   360 	    m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next);

   361 	n = (m==-1)?-1:G.nodes[m].first_in;

   362       }

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

   364       EdgeIt() : Edge() { }

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

   366       ///make class \c SymListGraph::SymEdgeMap friend of Edge

   367       int &idref() {return n;}

   368     };

   370     class OutEdgeIt : public Edge {

   371       friend class ListGraph;

   372     public:

   373       OutEdgeIt() : Edge() { }

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

   376       OutEdgeIt(const ListGraph& G,const Node v)

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

   378     };

   380     class InEdgeIt : public Edge {

   381       friend class ListGraph;

   382     public:

   383       InEdgeIt() : Edge() { }

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

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

   386     };

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

   389     {

   390       std::vector<T> container;

   392     public:

   393       typedef T ValueType;

   394       typedef Node KeyType;

   396       NodeMap(const ListGraph &_G) :

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

   398       {

   399 	G->dyn_node_maps.push_back(this);

   400       }

   401       NodeMap(const ListGraph &_G,const T &t) :

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

   403       {

   404 	G->dyn_node_maps.push_back(this);

   405       }

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

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

   409       {

   410  	G->dyn_node_maps.push_back(this);

   411       }

   413       template<typename TT> friend class NodeMap;

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

   416       ///

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

   418 	DynMapBase<Node>(*m.G)

   419       {

   420 	G->dyn_node_maps.push_back(this);

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

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

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

   424 	    i++)

   425 	  container.push_back(*i);

   426       }

   427       ~NodeMap()

   428       {

   429 	if(G) {

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

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

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

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

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

   435 	  if(*i==this) {

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

   437 	    G->dyn_node_maps.pop_back();

   438 	  }

   439 	}

   440       }

   442       void add(const Node k)

   443       {

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

   445       }

   447       void erase(const Node) { }

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

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

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

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

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

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

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

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

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

   459       ///cause serious problem.

   460       ///\todo Is this really so?

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

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

   463       {

   464 	container = m.container;

   465 	return *this;

   466       }

   467       template<typename TT>

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

   469       {

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

   471 	return *this;

   472       }

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

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

   476     };

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

   479     {

   480       std::vector<T> container;

   482     public:

   483       typedef T ValueType;

   484       typedef Edge KeyType;

   486       EdgeMap(const ListGraph &_G) :

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

   488       {

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

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

   491 	G->dyn_edge_maps.push_back(this);

   492       }

   493       EdgeMap(const ListGraph &_G,const T &t) :

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

   495       {

   496 	G->dyn_edge_maps.push_back(this);

   497       }

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

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

   500       {

   501  	G->dyn_node_maps.push_back(this);

   502       }

   504       template<typename TT> friend class EdgeMap;

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

   507       ///

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

   509 	DynMapBase<Edge>(*m.G)

   510       {

   511 	G->dyn_node_maps.push_back(this);

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

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

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

   515 	    i++)

   516 	  container.push_back(*i);

   517       }

   518       ~EdgeMap()

   519       {

   520 	if(G) {

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

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

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

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

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

   526 	  if(*i==this) {

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

   528 	    G->dyn_edge_maps.pop_back();

   529 	  }

   530 	}

   531       }

   533       void add(const Edge k)

   534       {

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

   536       }

   537       void erase(const Edge) { }

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

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

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

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

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

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

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

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

   548       ///cause serious problem.

   549       ///\todo Is this really so?

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

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

   552       {

   553 	container = m.container;

   554 	return *this;

   555       }

   556       template<typename TT>

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

   558       {

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

   560 	return *this;

   561       }

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

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

   565     };

   567   };

   569   ///Graph for bidirectional edges.

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

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

   573   ///of oppositely directed edges.

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

   575   ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"

   576   ///that complements this

   577   ///feature by

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

   579   ///\ref GraphSkeleton::EdgeMap "EdgeMap"

   580   ///can be used

   581   ///as well.

   582   ///

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

   584   ///using \ref opposite.

   585   ///

   586   ///Here erase(Edge) deletes a pair of edges.

   587   ///

   588   ///\todo this date structure need some reconsiderations. Maybe it

   589   ///should be implemented independently from ListGraph.

   591   class SymListGraph : public ListGraph

   592   {

   593   public:

   594     template<typename T> class SymEdgeMap;

   595     template<typename T> friend class SymEdgeMap;

   597     SymListGraph() : ListGraph() { }

   598     SymListGraph(const ListGraph &_g) : ListGraph(_g) { }

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

   600     Edge addEdge(Node u, Node v)

   601     {

   602       Edge e = ListGraph::addEdge(u,v);

   603       ListGraph::addEdge(v,u);

   604       return e;

   605     }

   607     void erase(Node n) { ListGraph::erase(n); }

   608     ///The oppositely directed edge.

   610     ///Returns the oppositely directed

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

   612     Edge opposite(Edge e) const

   613     {

   614       Edge f;

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

   616       return f;

   617     }

   619     ///Removes a pair of oppositely directed edges to the graph.

   620     void erase(Edge e) {

   621       ListGraph::erase(opposite(e));

   622       ListGraph::erase(e);

   623     }

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

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

   628     ///directed pairs of edges.

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

   630     {

   631       std::vector<T> container;

   633     public:

   634       typedef T ValueType;

   635       typedef Edge KeyType;

   637       SymEdgeMap(const SymListGraph &_G) :

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

   639       {

   640 	static_cast<const SymListGraph*>(G)->dyn_edge_maps.push_back(this);

   641       }

   642       SymEdgeMap(const SymListGraph &_G,const T &t) :

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

   644       {

   645 	G->dyn_edge_maps.push_back(this);

   646       }

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

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

   650       {

   651  	G->dyn_node_maps.push_back(this);

   652       }

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

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

   657       ///

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

   660 	DynMapBase<SymEdge>(*m.G)

   661       {

   662 	G->dyn_node_maps.push_back(this);

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

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

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

   666 	    i++)

   667 	  container.push_back(*i);

   668       }

   670       ~SymEdgeMap()

   671       {

   672 	if(G) {

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

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

   675 	      i!=static_cast<const SymListGraph*>(G)->dyn_edge_maps.end()

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

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

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

   679 	  if(*i==this) {

   680 	    *i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.back();

   681 	    static_cast<const SymListGraph*>(G)->dyn_edge_maps.pop_back();

   682 	  }

   683 	}

   684       }

   686       void add(const Edge k)

   687       {

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

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

   690       }

   691       void erase(const Edge k) { }

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

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

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

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

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

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

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

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

   702       ///cause serious problem.

   703       ///\todo Is this really so?

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

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

   706       {

   707 	container = m.container;

   708 	return *this;

   709       }

   710       template<typename TT>

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

   712       {

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

   714 	return *this;

   715       }

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

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

   720     };

   722   };

   725 } //namespace hugo

   730 #endif //SMART_GRAPH_H

author	alpar
	Sun, 25 Apr 2004 16:58:05 +0000
changeset 398	ecebcedd8960
parent 396	639c9daed784
child 400	cb377609cf1d
permissions	-rw-r--r--