COIN-OR::LEMON - Graph Library

Changeset 701:c03e073b8394 in lemon-0.x


Ignore:
Timestamp:
07/14/04 12:06:27 (15 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@952
Message:
 
Location:
src/work/deba
Files:
1 added
4 edited

Legend:

Unmodified
Added
Removed
  • src/work/deba/list_graph.h

    r698 r701  
    396396  ///should be implemented independently from ListGraph.
    397397
    398   };
    399  
    400 
    401   ///A graph class containing only nodes.
    402 
    403   ///This class implements a graph structure without edges.
    404   ///The most useful application of this class is to be the node set of an
    405   ///\ref EdgeSet class.
    406   ///
    407   ///It conforms to the graph interface documented under
    408   ///the description of \ref GraphSkeleton with the exception that you cannot
    409   ///add (or delete) edges. The usual edge iterators are exists, but they are
    410   ///always \ref INVALID.
    411   ///\sa \ref GraphSkeleton
    412   ///\sa \ref EdgeSet
    413   class NodeSet {
    414 
    415     //Nodes are double linked.
    416     //The free nodes are only single linked using the "next" field.
    417     struct NodeT
    418     {
    419       int first_in,first_out;
    420       int prev, next;
    421       //      NodeT() {}
    422     };
    423 
    424     std::vector<NodeT> nodes;
    425     //The first node
    426     int first_node;
    427     //The first free node
    428     int first_free_node;
    429    
    430   protected:
    431    
    432     template <typename Key> class DynMapBase
    433     {
    434     protected:
    435       const NodeSet* G;
    436     public:
    437       virtual void add(const Key k) = 0;
    438       virtual void erase(const Key k) = 0;
    439       DynMapBase(const NodeSet &_G) : G(&_G) {}
    440       virtual ~DynMapBase() {}
    441       friend class NodeSet;
    442     };
    443    
    444   public:
    445     template <typename T> class EdgeMap;
    446     template <typename T> class NodeMap;
    447    
    448     class Node;
    449     class Edge;
    450 
    451     //  protected:
    452     // HELPME:
    453   protected:
    454     ///\bug It must be public because of SymEdgeMap.
    455     ///
    456     mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
    457     //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
    458    
    459   public:
    460 
    461     class NodeIt;
    462     class EdgeIt;
    463     class OutEdgeIt;
    464     class InEdgeIt;
    465    
    466     template <typename T> class NodeMap;
    467     template <typename T> class EdgeMap;
    468    
    469   public:
    470 
    471     ///Default constructor
    472     NodeSet() : nodes(), first_node(-1),
    473                   first_free_node(-1) {}
    474     ///Copy constructor
    475     NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node),
    476                                      first_free_node(_g.first_free_node) {}
    477    
    478     ~NodeSet()
    479     {
    480       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
    481           i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
    482       //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
    483       //          i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
    484     }
    485 
    486     int nodeNum() const { return nodes.size(); }  //FIXME: What is this?
    487     int edgeNum() const { return 0; }  //FIXME: What is this?
    488 
    489     ///\bug This function does something different than
    490     ///its name would suggests...
    491     int maxNodeId() const { return nodes.size(); }  //FIXME: What is this?
    492     ///\bug This function does something different than
    493     ///its name would suggests...
    494     int maxEdgeId() const { return 0; }  //FIXME: What is this?
    495 
    496     Node tail(Edge e) const { return INVALID; }
    497     Node head(Edge e) const { return INVALID; }
    498 
    499     Node aNode(OutEdgeIt e) const { return INVALID; }
    500     Node aNode(InEdgeIt e) const { return INVALID; }
    501 
    502     Node bNode(OutEdgeIt e) const { return INVALID; }
    503     Node bNode(InEdgeIt e) const { return INVALID; }
    504 
    505     NodeIt& first(NodeIt& v) const {
    506       v=NodeIt(*this); return v; }
    507     EdgeIt& first(EdgeIt& e) const {
    508       e=EdgeIt(*this); return e; }
    509     OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
    510       e=OutEdgeIt(*this,v); return e; }
    511     InEdgeIt& first(InEdgeIt& e, const Node v) const {
    512       e=InEdgeIt(*this,v); return e; }
    513 
    514 //     template< typename It >
    515 //     It first() const { It e; first(e); return e; }
    516 
    517 //     template< typename It >
    518 //     It first(Node v) const { It e; first(e,v); return e; }
    519 
    520     bool valid(Edge e) const { return false; }
    521     bool valid(Node n) const { return n.n!=-1; }
    522    
    523     void setInvalid(Edge &e) { }
    524     void setInvalid(Node &n) { n.n=-1; }
    525    
    526     template <typename It> It getNext(It it) const
    527     { It tmp(it); return next(tmp); }
    528 
    529     NodeIt& next(NodeIt& it) const {
    530       it.n=nodes[it.n].next;
    531       return it;
    532     }
    533     OutEdgeIt& next(OutEdgeIt& it) const { return it; }
    534     InEdgeIt& next(InEdgeIt& it) const { return it; }
    535     EdgeIt& next(EdgeIt& it) const { return it; }
    536 
    537     int id(Node v) const { return v.n; }
    538     int id(Edge e) const { return -1; }
    539 
    540     /// Adds a new node to the graph.
    541 
    542     /// \todo It adds the nodes in a reversed order.
    543     /// (i.e. the lastly added node becomes the first.)
    544     Node addNode() {
    545       int n;
    546      
    547       if(first_free_node==-1)
    548         {
    549           n = nodes.size();
    550           nodes.push_back(NodeT());
    551         }
    552       else {
    553         n = first_free_node;
    554         first_free_node = nodes[n].next;
    555       }
    556      
    557       nodes[n].next = first_node;
    558       if(first_node != -1) nodes[first_node].prev = n;
    559       first_node = n;
    560       nodes[n].prev = -1;
    561      
    562       nodes[n].first_in = nodes[n].first_out = -1;
    563      
    564       Node nn; nn.n=n;
    565 
    566       //Update dynamic maps
    567       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
    568           i!=dyn_node_maps.end(); ++i) (**i).add(nn);
    569 
    570       return nn;
    571     }
    572    
    573     void erase(Node nn) {
    574       int n=nn.n;
    575      
    576       if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
    577       if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
    578       else first_node = nodes[n].next;
    579      
    580       nodes[n].next = first_free_node;
    581       first_free_node = n;
    582 
    583       //Update dynamic maps
    584       for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
    585           i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
    586     }
    587    
    588     ///\bug Dynamic maps must be updated!
    589     ///
    590     void clear() {
    591       nodes.clear();
    592       first_node = first_free_node = -1;
    593     }
    594 
    595     class Node {
    596       friend class NodeSet;
    597       template <typename T> friend class NodeMap;
    598      
    599       friend class Edge;
    600       friend class OutEdgeIt;
    601       friend class InEdgeIt;
    602 
    603     protected:
    604       int n;
    605       friend int NodeSet::id(Node v) const;
    606       Node(int nn) {n=nn;}
    607     public:
    608       Node() {}
    609       Node (Invalid i) { n=-1; }
    610       bool operator==(const Node i) const {return n==i.n;}
    611       bool operator!=(const Node i) const {return n!=i.n;}
    612       bool operator<(const Node i) const {return n<i.n;}
    613     };
    614    
    615     class NodeIt : public Node {
    616       friend class NodeSet;
    617     public:
    618       NodeIt() : Node() { }
    619       NodeIt(Invalid i) : Node(i) { }
    620       NodeIt(const NodeSet& G) : Node(G.first_node) { }
    621       ///\todo Undocumented conversion Node -\> NodeIt.
    622       NodeIt(const NodeSet& G, const Node &n) : Node(n) { }
    623 
    624     };
    625 
    626     class Edge {
    627       //friend class NodeSet;
    628       //template <typename T> friend class EdgeMap;
    629 
    630       //template <typename T> friend class SymNodeSet::SymEdgeMap;     
    631       //friend Edge SymNodeSet::opposite(Edge) const;
    632      
    633       //      friend class Node;
    634       //      friend class NodeIt;
    635     protected:
    636       //friend int NodeSet::id(Edge e) const;
    637       //      Edge(int nn) {}
    638     public:
    639       Edge() { }
    640       Edge (Invalid) { }
    641       bool operator==(const Edge i) const {return true;}
    642       bool operator!=(const Edge i) const {return false;}
    643       bool operator<(const Edge i) const {return false;}
    644       ///\bug This is a workaround until somebody tells me how to
    645       ///make class \c SymNodeSet::SymEdgeMap friend of Edge
    646       //      int idref() {return -1;}
    647       //      int idref() const {return -1;}
    648     };
    649    
    650     class EdgeIt : public Edge {
    651       //friend class NodeSet;
    652     public:
    653       EdgeIt(const NodeSet& G) : Edge() { }
    654       EdgeIt (Invalid i) : Edge(i) { }
    655       EdgeIt() : Edge() { }
    656       ///\bug This is a workaround until somebody tells me how to
    657       ///make class \c SymNodeSet::SymEdgeMap friend of Edge
    658       //      int idref() {return -1;}
    659     };
    660    
    661     class OutEdgeIt : public Edge {
    662       friend class NodeSet;
    663     public:
    664       OutEdgeIt() : Edge() { }
    665       OutEdgeIt (Invalid i) : Edge(i) { }
    666       OutEdgeIt(const NodeSet& G,const Node v)  : Edge() {}
    667     };
    668    
    669     class InEdgeIt : public Edge {
    670       friend class NodeSet;
    671     public:
    672       InEdgeIt() : Edge() { }
    673       InEdgeIt (Invalid i) : Edge(i) { }
    674       InEdgeIt(const NodeSet& G,Node v) :Edge() {}
    675     };
    676 
    677     template <typename T> class NodeMap : public DynMapBase<Node>
    678     {
    679       std::vector<T> container;
    680 
    681     public:
    682       typedef T ValueType;
    683       typedef Node KeyType;
    684 
    685       NodeMap(const NodeSet &_G) :
    686         DynMapBase<Node>(_G), container(_G.maxNodeId())
    687       {
    688         G->dyn_node_maps.push_back(this);
    689       }
    690       NodeMap(const NodeSet &_G,const T &t) :
    691         DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
    692       {
    693         G->dyn_node_maps.push_back(this);
    694       }
    695      
    696       NodeMap(const NodeMap<T> &m) :
    697         DynMapBase<Node>(*m.G), container(m.container)
    698       {
    699         G->dyn_node_maps.push_back(this);
    700       }
    701 
    702       template<typename TT> friend class NodeMap;
    703  
    704       ///\todo It can copy between different types.
    705       ///
    706       template<typename TT> NodeMap(const NodeMap<TT> &m) :
    707         DynMapBase<Node>(*m.G), container(m.container.size())
    708       {
    709         G->dyn_node_maps.push_back(this);
    710         typename std::vector<TT>::const_iterator i;
    711         for(typename std::vector<TT>::const_iterator i=m.container.begin();
    712             i!=m.container.end();
    713             i++)
    714           container.push_back(*i);
    715       }
    716       ~NodeMap()
    717       {
    718         if(G) {
    719           std::vector<DynMapBase<Node>* >::iterator i;
    720           for(i=G->dyn_node_maps.begin();
    721               i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
    722           //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
    723           //A better way to do that: (Is this really important?)
    724           if(*i==this) {
    725             *i=G->dyn_node_maps.back();
    726             G->dyn_node_maps.pop_back();
    727           }
    728         }
    729       }
    730 
    731       void add(const Node k)
    732       {
    733         if(k.n>=int(container.size())) container.resize(k.n+1);
    734       }
    735 
    736       void erase(const Node) { }
    737      
    738       void set(Node n, T a) { container[n.n]=a; }
    739       //'T& operator[](Node n)' would be wrong here
    740       typename std::vector<T>::reference
    741       operator[](Node n) { return container[n.n]; }
    742       //'const T& operator[](Node n)' would be wrong here
    743       typename std::vector<T>::const_reference
    744       operator[](Node n) const { return container[n.n]; }
    745 
    746       ///\warning There is no safety check at all!
    747       ///Using operator = between maps attached to different graph may
    748       ///cause serious problem.
    749       ///\todo Is this really so?
    750       ///\todo It can copy between different types.
    751       const NodeMap<T>& operator=(const NodeMap<T> &m)
    752       {
    753         container = m.container;
    754         return *this;
    755       }
    756       template<typename TT>
    757       const NodeMap<T>& operator=(const NodeMap<TT> &m)
    758       {
    759         std::copy(m.container.begin(), m.container.end(), container.begin());
    760         return *this;
    761       }
    762      
    763       void update() {}    //Useless for Dynamic Maps
    764       void update(T a) {}  //Useless for Dynamic Maps
    765     };
    766    
    767     template <typename T> class EdgeMap
    768     {
    769     public:
    770       typedef T ValueType;
    771       typedef Edge KeyType;
    772 
    773       EdgeMap(const NodeSet &) { }
    774       EdgeMap(const NodeSet &,const T &) { }
    775       EdgeMap(const EdgeMap<T> &) { }
    776       //      template<typename TT> friend class EdgeMap;
    777 
    778       ///\todo It can copy between different types.
    779       ///
    780       template<typename TT> EdgeMap(const EdgeMap<TT> &) { }
    781       ~EdgeMap() { }
    782 
    783       void add(const Edge  ) { }
    784       void erase(const Edge) { }
    785      
    786       void set(Edge, T) { }
    787       //T get(Edge n) const { return container[n.n]; }
    788       ValueType &operator[](Edge) { return *((T*)(NULL)); }
    789       const ValueType &operator[](Edge) const { return *((T*)(NULL)); }
    790 
    791       const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; }
    792    
    793       template<typename TT>
    794       const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; }
    795      
    796       void update() {}
    797       void update(T a) {}
    798     };
    799   };
    800 
    801 
    802 
    803   ///Graph structure using a node set of another graph.
    804 
    805   ///This structure can be used to establish another graph over a node set
    806   /// of an existing one. The node iterator will go through the nodes of the
    807   /// original graph, and the NodeMap's of both graphs will convert to
    808   /// each other.
    809   ///
    810   ///\warning Adding or deleting nodes from the graph is not safe if an
    811   ///\ref EdgeSet is currently attached to it!
    812   ///
    813   ///\todo Make it possible to add/delete edges from the base graph
    814   ///(and from \ref EdgeSet, as well)
    815   ///
    816   ///\param GG The type of the graph which shares its node set with this class.
    817   ///Its interface must conform with \ref GraphSkeleton.
    818   ///
    819   ///It conforms to the graph interface documented under
    820   ///the description of \ref GraphSkeleton.
    821   ///\sa \ref GraphSkeleton.
    822   ///\sa \ref NodeSet.
    823   template<typename GG>
    824   class EdgeSet {
    825 
    826     typedef GG NodeGraphType;
    827 
    828     NodeGraphType &G;
    829 
    830   public:
    831     class Node;
    832     int id(Node v) const;
    833 
    834     class Node : public NodeGraphType::Node {
    835       friend class EdgeSet;
    836       //      template <typename T> friend class NodeMap;
    837      
    838       friend class Edge;
    839       friend class OutEdgeIt;
    840       friend class InEdgeIt;
    841       friend class SymEdge;
    842 
    843     public:
    844       friend int EdgeSet::id(Node v) const;
    845       //      Node(int nn) {n=nn;}
    846     public:
    847       Node() : NodeGraphType::Node() {}
    848       Node (Invalid i) : NodeGraphType::Node(i) {}
    849       Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
    850     };
    851    
    852     class NodeIt : public NodeGraphType::NodeIt {
    853       friend class EdgeSet;
    854     public:
    855       NodeIt() : NodeGraphType::NodeIt() { }
    856       NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
    857       NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
    858       NodeIt(const typename NodeGraphType::NodeIt &n)
    859         : NodeGraphType::NodeIt(n) {}
    860       ///\todo Undocumented conversion Node -\> NodeIt.
    861       NodeIt(const EdgeSet& _G, const Node &n)
    862         : NodeGraphType::NodeIt(_G.G,n) { }
    863 
    864       operator Node() { return Node(*this);}
    865     };
    866 
    867   private:
    868     //Edges are double linked.
    869     //The free edges are only single linked using the "next_in" field.
    870     struct NodeT
    871     {
    872       int first_in,first_out;
    873       NodeT() : first_in(-1), first_out(-1) { }
    874     };
    875 
    876     struct EdgeT
    877     {
    878       Node head, tail;
    879       int prev_in, prev_out;
    880       int next_in, next_out;
    881     };
    882 
    883    
    884     typename NodeGraphType::template NodeMap<NodeT> nodes;
    885    
    886     std::vector<EdgeT> edges;
    887     //The first free edge
    888     int first_free_edge;
    889    
    890   protected:
    891    
    892     template <typename Key> class DynMapBase
    893     {
    894     protected:
    895       const EdgeSet* G;
    896     public:
    897       virtual void add(const Key k) = 0;
    898       virtual void erase(const Key k) = 0;
    899       DynMapBase(const EdgeSet &_G) : G(&_G) {}
    900       virtual ~DynMapBase() {}
    901       friend class EdgeSet;
    902     };
    903    
    904   public:
    905     //template <typename T> class NodeMap;
    906     template <typename T> class EdgeMap;
    907    
    908     class Node;
    909     class Edge;
    910 
    911     //  protected:
    912     // HELPME:
    913   protected:
    914     // mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
    915     ///\bug It must be public because of SymEdgeMap.
    916     ///
    917     mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
    918    
    919   public:
    920 
    921     class NodeIt;
    922     class EdgeIt;
    923     class OutEdgeIt;
    924     class InEdgeIt;
    925    
    926     template <typename T> class NodeMap;
    927     template <typename T> class EdgeMap;
    928    
    929   public:
    930 
    931     ///Constructor
    932    
    933     ///Construates a new graph based on the nodeset of an existing one.
    934     ///\param _G the base graph.
    935     ///\todo It looks like a copy constructor, but it isn't.
    936     EdgeSet(NodeGraphType &_G) : G(_G),
    937                                  nodes(_G), edges(),
    938                                  first_free_edge(-1) { }
    939     ///Copy constructor
    940 
    941     ///Makes a copy of an EdgeSet.
    942     ///It will be based on the same graph.
    943     EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges),
    944                                  first_free_edge(_g.first_free_edge) { }
    945    
    946     ~EdgeSet()
    947     {
    948       // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
    949       //  i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
    950       for(typename std::vector<DynMapBase<Edge> * >::iterator
    951             i=dyn_edge_maps.begin();
    952           i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
    953     }
    954 
    955     int nodeNum() const { return G.nodeNum(); }  //FIXME: What is this?
    956     int edgeNum() const { return edges.size(); }  //FIXME: What is this?
    957 
    958     ///\bug This function does something different than
    959     ///its name would suggests...
    960     int maxNodeId() const { return G.maxNodeId(); }  //FIXME: What is this?
    961     ///\bug This function does something different than
    962     ///its name would suggests...
    963     int maxEdgeId() const { return edges.size(); }  //FIXME: What is this?
    964 
    965     Node tail(Edge e) const { return edges[e.n].tail; }
    966     Node head(Edge e) const { return edges[e.n].head; }
    967 
    968     Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
    969     Node aNode(InEdgeIt e) const { return edges[e.n].head; }
    970 
    971     Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
    972     Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
    973 
    974     NodeIt& first(NodeIt& v) const {
    975       v=NodeIt(*this); return v; }
    976     EdgeIt& first(EdgeIt& e) const {
    977       e=EdgeIt(*this); return e; }
    978     OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
    979       e=OutEdgeIt(*this,v); return e; }
    980     InEdgeIt& first(InEdgeIt& e, const Node v) const {
    981       e=InEdgeIt(*this,v); return e; }
    982 
    983 //     template< typename It >
    984 //     It first() const { It e; first(e); return e; }
    985 
    986 //     template< typename It >
    987 //     It first(Node v) const { It e; first(e,v); return e; }
    988 
    989     bool valid(Edge e) const { return e.n!=-1; }
    990     bool valid(Node n) const { return G.valid(n); }
    991    
    992     void setInvalid(Edge &e) { e.n=-1; }
    993     void setInvalid(Node &n) { G.setInvalid(n); }
    994    
    995     template <typename It> It getNext(It it) const
    996     { It tmp(it); return next(tmp); }
    997 
    998     NodeIt& next(NodeIt& it) const { G.next(it); return it; }
    999     OutEdgeIt& next(OutEdgeIt& it) const
    1000     { it.n=edges[it.n].next_out; return it; }
    1001     InEdgeIt& next(InEdgeIt& it) const
    1002     { it.n=edges[it.n].next_in; return it; }
    1003     EdgeIt& next(EdgeIt& it) const {
    1004       if(edges[it.n].next_in!=-1) {
    1005         it.n=edges[it.n].next_in;
    1006       }
    1007       else {
    1008         NodeIt n(*this,edges[it.n].head);
    1009         for(n=next(n);
    1010             valid(n) && nodes[n].first_in == -1;
    1011             next(n)) ;
    1012         it.n = (valid(n))?-1:nodes[n].first_in;
    1013       }
    1014       return it;
    1015     }
    1016 
    1017     int id(Edge e) const { return e.n; }
    1018 
    1019     /// Adds a new node to the graph.
    1020     Node addNode() { return G.addNode(); }
    1021    
    1022     Edge addEdge(Node u, Node v) {
    1023       int n;
    1024      
    1025       if(first_free_edge==-1)
    1026         {
    1027           n = edges.size();
    1028           edges.push_back(EdgeT());
    1029         }
    1030       else {
    1031         n = first_free_edge;
    1032         first_free_edge = edges[n].next_in;
    1033       }
    1034      
    1035       edges[n].tail = u; edges[n].head = v;
    1036 
    1037       edges[n].next_out = nodes[u].first_out;
    1038       if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n;
    1039       edges[n].next_in = nodes[v].first_in;
    1040       if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n;
    1041       edges[n].prev_in = edges[n].prev_out = -1;
    1042        
    1043       nodes[u].first_out = nodes[v].first_in = n;
    1044 
    1045       Edge e; e.n=n;
    1046 
    1047       //Update dynamic maps
    1048       for(typename std::vector<DynMapBase<Edge> * >::iterator
    1049             i=dyn_edge_maps.begin();
    1050           i!=dyn_edge_maps.end(); ++i) (**i).add(e);
    1051 
    1052       return e;
    1053     }
    1054 
    1055   private:
    1056     void eraseEdge(int n) {
    1057      
    1058       if(edges[n].next_in!=-1)
    1059         edges[edges[n].next_in].prev_in = edges[n].prev_in;
    1060       if(edges[n].prev_in!=-1)
    1061         edges[edges[n].prev_in].next_in = edges[n].next_in;
    1062       else nodes[edges[n].head].first_in = edges[n].next_in;
    1063      
    1064       if(edges[n].next_out!=-1)
    1065         edges[edges[n].next_out].prev_out = edges[n].prev_out;
    1066       if(edges[n].prev_out!=-1)
    1067         edges[edges[n].prev_out].next_out = edges[n].next_out;
    1068       else nodes[edges[n].tail].first_out = edges[n].next_out;
    1069      
    1070       edges[n].next_in = first_free_edge;
    1071       first_free_edge = -1;     
    1072 
    1073       //Update dynamic maps
    1074       Edge e; e.n=n;
    1075       for(typename std::vector<DynMapBase<Edge> * >::iterator
    1076             i=dyn_edge_maps.begin();
    1077           i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
    1078     }
    1079      
    1080   public:
    1081 
    1082 //     void erase(Node nn) {
    1083 //       int n=nn.n;
    1084 //       int m;
    1085 //       while((m=nodes[n].first_in)!=-1) eraseEdge(m);
    1086 //       while((m=nodes[n].first_out)!=-1) eraseEdge(m);
    1087 //     }
    1088    
    1089     void erase(Edge e) { eraseEdge(e.n); }
    1090 
    1091     ///Clear all edges. (Doesn't clear the nodes!)
    1092     void clear() {
    1093       edges.clear();
    1094       first_free_edge=-1;
    1095     }
    1096 
    1097 
    1098 //     //\bug Dynamic maps must be updated!
    1099 //     //
    1100 //     void clear() {
    1101 //       nodes.clear();edges.clear();
    1102 //       first_node=first_free_node=first_free_edge=-1;
    1103 //     }
    1104 
    1105   public:
    1106     template <typename T> class EdgeMap;
    1107    
    1108     ///
    1109     class Edge {
    1110     public:
    1111       friend class EdgeSet;
    1112       template <typename T> friend class EdgeMap;
    1113 
    1114       friend class Node;
    1115       friend class NodeIt;
    1116     public:
    1117       ///\bug It shoud be at least protected
    1118       ///
    1119       int n;
    1120     protected:
    1121       friend int EdgeSet::id(Edge e) const;
    1122 
    1123       Edge(int nn) {n=nn;}
    1124     public:
    1125       Edge() { }
    1126       Edge (Invalid) { n=-1; }
    1127       bool operator==(const Edge i) const {return n==i.n;}
    1128       bool operator!=(const Edge i) const {return n!=i.n;}
    1129       bool operator<(const Edge i) const {return n<i.n;}
    1130       ///\bug This is a workaround until somebody tells me how to
    1131       ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
    1132       int &idref() {return n;}
    1133       const int &idref() const {return n;}
    1134     };
    1135    
    1136     class EdgeIt : public Edge {
    1137       friend class EdgeSet;
    1138       template <typename T> friend class EdgeMap;
    1139    
    1140      
    1141     public:
    1142       EdgeIt(const EdgeSet& G) : Edge() {
    1143         //              typename NodeGraphType::Node m;
    1144         NodeIt m;
    1145         for(G.first(m);
    1146             G.valid(m) && G.nodes[m].first_in == -1;  G.next(m));
    1147         //AJJAJ! This is a non sense!!!!!!!
    1148         this->n = G.valid(m)?-1:G.nodes[m].first_in;
    1149       }
    1150       EdgeIt (Invalid i) : Edge(i) { }
    1151       EdgeIt() : Edge() { }
    1152       ///\bug This is a workaround until somebody tells me how to
    1153       ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
    1154       int &idref() {return this->n;}
    1155     };
    1156    
    1157     class OutEdgeIt : public Edge {
    1158       friend class EdgeSet;
    1159     public:
    1160       OutEdgeIt() : Edge() { }
    1161       OutEdgeIt (Invalid i) : Edge(i) { }
    1162 
    1163       OutEdgeIt(const EdgeSet& G,const Node v) : Edge(G.nodes[v].first_out) { }
    1164     };
    1165    
    1166     class InEdgeIt : public Edge {
    1167       friend class EdgeSet;
    1168     public:
    1169       InEdgeIt() : Edge() { }
    1170       InEdgeIt (Invalid i) : Edge(i) { }
    1171       InEdgeIt(const EdgeSet& G,Node v) :Edge(G.nodes[v].first_in) { }
    1172     };
    1173 
    1174     template <typename T> class NodeMap :
    1175       public NodeGraphType::template NodeMap<T>
    1176     {
    1177       //This is a must, the constructors need it.
    1178       typedef typename NodeGraphType::template NodeMap<T> ParentNodeMap;
    1179     public:
    1180       NodeMap(const EdgeSet &_G) : ParentNodeMap(_G.G) { }
    1181       NodeMap(const EdgeSet &_G,const T &t) : ParentNodeMap(_G.G,t) { }
    1182       //It is unnecessary
    1183       NodeMap(const typename NodeGraphType::template NodeMap<T> &m) :
    1184         ParentNodeMap(m) { }
    1185 
    1186       ///\todo It can copy between different types.
    1187       ///
    1188       template<typename TT>
    1189       NodeMap(const typename NodeGraphType::template NodeMap<TT> &m)
    1190         : ParentNodeMap(m) { }
    1191     };
    1192    
    1193     ///
    1194     template <typename T> class EdgeMap : public DynMapBase<Edge>
    1195     {
    1196     protected:
    1197     public:
    1198       ///\bug It should be at least protected
    1199       ///
    1200       std::vector<T> container;
    1201 
    1202     public:
    1203       typedef T ValueType;
    1204       typedef Edge KeyType;
    1205 
    1206       EdgeMap(const EdgeSet &_G) :
    1207         DynMapBase<Edge>(_G), container(_G.maxEdgeId())
    1208       {
    1209         //FIXME: What if there are empty Id's?
    1210         //FIXME: Can I use 'this' in a constructor?
    1211         G->dyn_edge_maps.push_back(this);
    1212       }
    1213       EdgeMap(const EdgeSet &_G,const T &t) :
    1214         DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
    1215       {
    1216         G->dyn_edge_maps.push_back(this);
    1217       }
    1218       EdgeMap(const EdgeMap<T> &m) :
    1219         DynMapBase<Edge>(*m.G), container(m.container)
    1220       {
    1221         G->dyn_edge_maps.push_back(this);
    1222       }
    1223 
    1224       template<typename TT> friend class EdgeMap;
    1225 
    1226       ///\todo It can copy between different types.
    1227       ///
    1228       template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
    1229         DynMapBase<Edge>(*m.G), container(m.container.size())
    1230       {
    1231         G->dyn_edge_maps.push_back(this);
    1232         typename std::vector<TT>::const_iterator i;
    1233         for(typename std::vector<TT>::const_iterator i=m.container.begin();
    1234             i!=m.container.end();
    1235             i++)
    1236           container.push_back(*i);
    1237       }
    1238       ~EdgeMap()
    1239       {
    1240         if(G) {
    1241           typename std::vector<DynMapBase<Edge>* >::iterator i;
    1242           for(i=G->dyn_edge_maps.begin();
    1243               i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
    1244           //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
    1245           //A better way to do that: (Is this really important?)
    1246           if(*i==this) {
    1247             *i=G->dyn_edge_maps.back();
    1248             G->dyn_edge_maps.pop_back();
    1249           }
    1250         }
    1251       }
    1252      
    1253       void add(const Edge k)
    1254       {
    1255         if(k.n>=int(container.size())) container.resize(k.n+1);
    1256       }
    1257       void erase(const Edge) { }
    1258      
    1259       ///\bug This doesn't work. Why?
    1260       ///      void set(Edge n, T a) { container[n.n]=a; }
    1261       void set(Edge n, T a) { container[G->id(n)]=a; }
    1262       //T get(Edge n) const { return container[n.n]; }
    1263       typename std::vector<T>::reference
    1264       ///\bug This doesn't work. Why?
    1265       ///      operator[](Edge n) { return container[n.n]; }
    1266       operator[](Edge n) { return container[G->id(n)]; }
    1267       typename std::vector<T>::const_reference
    1268       ///\bug This doesn't work. Why?
    1269       ///      operator[](Edge n) const { return container[n.n]; }
    1270       operator[](Edge n) const { return container[G->id(n)]; }
    1271 
    1272       ///\warning There is no safety check at all!
    1273       ///Using operator = between maps attached to different graph may
    1274       ///cause serious problem.
    1275       ///\todo Is this really so?
    1276       ///\todo It can copy between different types.
    1277       const EdgeMap<T>& operator=(const EdgeMap<T> &m)
    1278       {
    1279         container = m.container;
    1280         return *this;
    1281       }
    1282      
    1283       template<typename TT> friend class EdgeMap;
    1284 
    1285       template<typename TT>
    1286       const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
    1287       {
    1288         std::copy(m.container.begin(), m.container.end(), container.begin());
    1289         return *this;
    1290       }
    1291      
    1292       void update() {}    //Useless for DynMaps
    1293       void update(T a) {}  //Useless for DynMaps
    1294     };
    1295 
    1296   };
    1297 
    1298   template<typename GG>
    1299   inline int EdgeSet<GG>::id(Node v) const { return G.id(v); }
    1300 
    1301 /// @} 
    1302 
    1303 } //namespace hugo
     398}
    1304399
    1305400#endif //HUGO_LIST_GRAPH_H
  • src/work/deba/main.cpp

    r698 r701  
    1212    ListGraph::Node node = g.addNode();
    1313  }
    14   ListGraph::NodeMap<int> map(g);
     14  ListGraph::NodeMap<int> map(g, 10);
    1515  for (int i = 0; i < 10; ++i) {
    1616    ListGraph::Node node = g.addNode();
     
    2020    cout << map[it] << endl;
    2121  }
     22  ListGraph::NodeMap<int>::iterator pit;
     23  for (pit = map.begin(); pit != map.end(); ++pit) {
     24    cout << g.id(pit->first) << ' ' << pit->second << endl;
     25  }
     26  ListGraph::NodeMap<double> ot_map = map;
     27  for (ListGraph::NodeIt it(g); g.valid(it); g.next(it)) {
     28    ot_map[it] *= 2.1;
     29    cout << ot_map[it] << endl;
     30  }
     31  ot_map = map;
     32  for (ListGraph::NodeIt it(g); g.valid(it); g.next(it)) {
     33    ot_map[it] *= 3.1;
     34    cout << ot_map[it] << endl;
     35  }
    2236  return 0;
    2337}
  • src/work/deba/map_defines.h

    r676 r701  
    33#define MAP_DEFINES_H
    44
     5/** Creates the EdgeMapRegistry type an declare a mutable instance
     6 *  named edge_maps.
     7 */
    58#define CREATE_EDGE_MAP_REGISTRY \
    69typedef MapRegistry<Graph, Edge, EdgeIt> EdgeMapRegistry; \
    7 EdgeMapRegistry edge_maps;
     10mutable EdgeMapRegistry edge_maps;
    811
     12/** Creates the NodeMapRegistry type an declare a mutable instance
     13 *  named node_maps.
     14 */
    915#define CREATE_NODE_MAP_REGISTRY \
    1016typedef MapRegistry<Graph, Node, NodeIt> NodeMapRegistry; \
    11 NodeMapRegistry node_maps;
     17mutable NodeMapRegistry node_maps;
    1218
     19/** Creates both map registries.
     20 */
    1321#define CREATE_MAP_REGISTRIES \
    1422CREATE_NODE_MAP_REGISTRY \
    1523CREATE_EDGE_MAP_REGISTRY
    1624
     25/** Creates a map a concrete factory type from a template map
     26 *  factory to use as node map factory.
     27 */
    1728#define CREATE_NODE_MAP_FACTORY(TemplateFactory) \
    1829typedef TemplateFactory<NodeMapRegistry> NodeMapFactory;
    1930
     31/** Creates a map a concrete factory type from a template map
     32 *  factory to use as edge map factory.
     33 */
    2034#define CREATE_EDGE_MAP_FACTORY(TemplateFactory) \
    2135typedef TemplateFactory<EdgeMapRegistry> EdgeMapFactory;
    2236
     37/** Creates both map factories.
     38 */
    2339#define CREATE_MAP_FACTORIES(TemplateFactory) \
    2440CREATE_NODE_MAP_FACTORY(TemplateFactory) \
    2541CREATE_EDGE_MAP_FACTORY(TemplateFactory)
    2642
     43/** Import a map from a concrete map factory. The import method is
     44 *  an overloading of the map type.
     45 *  The reason to use these macro is that the c++ does not support
     46 *  the template typedefs. If a future release of the c++
     47 *  supports this feature it should be fixed.
     48 */
    2749#define IMPORT_NODE_MAP(Factory) \
    2850template <typename V> \
     
    3052public: \
    3153NodeMap() {} \
    32 NodeMap(Graph& g) : Factory::Map<V>(g, g.node_maps) {} \
     54NodeMap(const Graph& g) : Factory::Map<V>(&g, &(g.node_maps)) {} \
     55NodeMap(const Graph& g, const V& v) : Factory::Map<V>(g, g.node_maps, v) {} \
     56NodeMap(const NodeMap& copy) : Factory::Map<V>(copy) {} \
     57template <typename CMap> NodeMap(const CMap& copy) : Factory::Map<V>(copy) {} \
     58NodeMap& operator=(const NodeMap& copy) { \
     59  this->Factory::Map<V>::operator=(copy); \
     60  return *this; \
     61} \
     62template <typename CMap>NodeMap& operator=(const CMap& copy) { \
     63  this->Factory::Map<V>::operator=<CMap>(copy); \
     64  return *this; \
     65} \
    3366};
    3467
     68/** Import a map from a concrete map factory. The import method is
     69 *  an overloading of the map type.
     70 *  The reason to use these macro is that the c++ does not support
     71 *  the template typedefs. If a future release of the c++
     72 *  supports this feature it should be fixed.
     73 */
    3574#define IMPORT_EDGE_MAP(Factory) \
    3675template <typename V> \
     
    3877public: \
    3978EdgeMap() {} \
    40 EdgeMap(Graph& g) : Factory::Map<V>(g, g.edge_maps) {} \
     79EdgeMap(const Graph& g) : Factory::Map<V>(g, g.edge_maps) {} \
     80EdgeMap(const Graph& g, const V& v) : Factory::Map<V>(g, g.node_maps, v) {} \
     81EdgeMap(const EdgeMap& copy) : Factory::Map<V>(copy) {} \
     82template <typename CMap> EdgeMap(const CMap& copy) : Factory::Map<V>(copy) {} \
     83EdgeMap& operator=(const EdgeMap& copy) { \
     84  this->Factory::Map<V>::operator=(copy); \
     85  return *this; \
     86} \
     87template <typename CMap>EdgeMap& operator=(const CMap& copy) { \
     88  this->Factory::Map<V>::operator=<CMap>(copy); \
     89  return *this; \
     90} \
    4191};
    4292
     93/** This macro creates both map factories and imports both maps.
     94 */
    4395#define CREATE_MAPS(TemplateFactory) \
    4496CREATE_MAP_FACTORIES(TemplateFactory) \
  • src/work/deba/map_registry.h

    r676 r701  
    99
    1010/**
    11     Registry class to register edge or node maps in the graph. The
    12    registry helps you to implement an observer pattern. If you add
    13    or erase an edge or node you must notify all the maps about the
    14    event.
     11 * Registry class to register edge or node maps into the graph. The
     12 * registry helps you to implement an observer pattern. If you add
     13 * or erase an edge or node you must notify all the maps about the
     14 * event.
    1515*/
    1616  template <typename G, typename K, typename KIt>
     
    2323
    2424
    25     ///.
    26 
    27     ///.
    28     ///
     25    /**
     26     * MapBase is the base class of the registered maps.
     27     * It defines the core modification operations on the maps and
     28     * implements some helper functions.
     29     */
    2930    class MapBase {
    3031    public:
     
    3536       
    3637      friend class Registry;
    37                
    38       /** 
    39           Default constructor.
    40       */       
    41                
     38
     39      /**
     40       * Default constructor for MapBase.
     41       */
     42
    4243      MapBase() : graph(0), registry(0) {}
    43 
    44       /**
    45           Simple constructor to register into a graph registry.
    46       */
    47        
    48       MapBase(Graph& g, Registry& r) : graph(&g), registry(0) {
     44               
     45      /**
     46       * Simple constructor to register into a graph registry.
     47      */
     48       
     49      MapBase(const Graph& g, Registry& r) : graph(&g), registry(0) {
    4950        r.attach(*this);
    5051      }
    5152
    5253      /**
    53           Copy constructor with registering into the map.
     54       * Copy constructor to register into the registry.
    5455      */       
    5556       
     
    6162       
    6263      /**
    63           Assign operator.
     64       * Assign operator.
    6465      */       
    6566
     
    7677
    7778      /**
    78           Destructor.
     79       * Destructor.
    7980      */               
    8081
     
    8485        }
    8586      }
    86        
     87
     88      /*
     89       * Returns the graph that the map belongs to.
     90      */
     91
     92      const Graph* getGraph() const { return graph; }
     93       
     94    private:
     95               
     96      const Graph* graph;
     97      Registry* registry;
     98
     99      int registry_index;
     100
    87101    protected:
    88                
    89       Graph* graph;
    90       Registry* registry;
    91 
    92       int registry_index;
    93102       
    94103      /**
     
    107116       
    108117      virtual void destroy() {
    109         for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
     118        for (KeyIt it(*getGraph()); getGraph()->valid(it); getGraph()->next(it)) {
    110119          erase(it);
    111120        }
     
    135144  protected:
    136145       
     146    /**
     147     * The container type of the maps.
     148     */
    137149    typedef std::vector<MapBase*> Container;
     150
     151    /**
     152     * The container of the registered maps.
     153     */
    138154    Container container;
    139155
    140156               
    141     public:
    142        
    143     ///.
     157  public:
     158       
     159    /**
     160     * Default Constructor of the MapRegistry. It creates an empty registry.
     161     */
    144162    MapRegistry() {}
    145163       
    146     ///.
     164    /**
     165     * Copy Constructor of the MapRegistry. The new registry does not steal
     166     * the maps from the right value. The new registry will be an empty.
     167     */
    147168    MapRegistry(const MapRegistry&) {}
    148169               
    149     ///.
     170    /**
     171     * Assign operator. The left value does not steal the maps
     172     * from the right value. The left value will be an empty registry.
     173     */
    150174    MapRegistry& operator=(const MapRegistry&) {
    151175      for (it = container.begin(); it != container.end(); ++it) {
     
    156180    }
    157181                               
    158     ///.
     182    /**
     183     * Destructor of the MapRegistry.
     184     */
    159185    ~MapRegistry() {
    160186      typename Container::iterator it;
     
    169195    public:
    170196       
    171     ///.
     197    /**
     198     * Attach a map into thr registry. If the map has been attached
     199     * into an other registry it is detached from that automaticly.
     200     */
    172201    void attach(MapBase& map) {
    173202      if (map.registry) {
     
    179208    }
    180209       
    181     ///.
     210    /**
     211     * Detach the map from the registry.
     212     */
    182213    void detach(MapBase& map) {
    183214      container.back()->registry_index = map.registry_index;
     
    189220       
    190221               
    191     ///.
     222    /**
     223     * Notify all the registered maps about a Key added.
     224     */
    192225    virtual void add(Key& key) {
    193226      typename Container::iterator it;
     
    197230    }   
    198231               
    199     ///.
     232    /**
     233     * Notify all the registered maps about a Key erased.
     234     */
    200235    virtual void erase(Key& key) {
    201236      typename Container::iterator it;
Note: See TracChangeset for help on using the changeset viewer.