COIN-OR::LEMON - Graph Library

Changeset 701:c03e073b8394 in lemon-0.x for src/work/deba/list_graph.h


Ignore:
Timestamp:
07/14/04 12:06:27 (19 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@952
Message:
 
File:
1 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
Note: See TracChangeset for help on using the changeset viewer.