COIN-OR::LEMON - Graph Library

Changeset 946:c94ef40a22ce in lemon-0.x for src/lemon/list_graph.h


Ignore:
Timestamp:
10/28/04 00:38:50 (16 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1322
Message:

The graph_factory branch (@ 1321) has been merged to trunk.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/list_graph.h

    r937 r946  
    1 /* -*- C++ -*-
    2  * src/lemon/list_graph.h - Part of LEMON, a generic C++ optimization library
    3  *
    4  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    5  * (Egervary Combinatorial Optimization Research Group, EGRES).
    6  *
    7  * Permission to use, modify and distribute this software is granted
    8  * provided that this copyright notice appears in all copies. For
    9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
     1// -*- c++ -*-
    162
    173#ifndef LEMON_LIST_GRAPH_H
    184#define LEMON_LIST_GRAPH_H
    195
    20 ///\ingroup graphs
    21 ///\file
    22 ///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes.
    23 
    24 #include <vector>
    25 #include <climits>
    26 
    27 #include <lemon/invalid.h>
    28 
    29 #include <lemon/map_registry.h>
    30 #include <lemon/array_map.h>
    31 
    32 #include <lemon/map_defines.h>
     6#include <lemon/erasable_graph_extender.h>
     7#include <lemon/clearable_graph_extender.h>
     8#include <lemon/extendable_graph_extender.h>
     9
     10#include <lemon/idmappable_graph_extender.h>
     11
     12#include <lemon/iterable_graph_extender.h>
     13
     14#include <lemon/alteration_observer_registry.h>
     15
     16#include <lemon/default_map.h>
    3317
    3418
    3519namespace lemon {
    3620
    37 /// \addtogroup graphs
    38 /// @{
    39 
    40   ///A list graph class.
    41 
    42   ///This is a simple and fast erasable graph implementation.
    43   ///
    44   ///It conforms to the
    45   ///\ref skeleton::ErasableGraph "ErasableGraph" concept.
    46   ///\sa skeleton::ErasableGraph.
    47   class ListGraph {
    48 
    49     //Nodes are double linked.
    50     //The free nodes are only single linked using the "next" field.
    51     struct NodeT
    52     {
     21  class ListGraphBase {
     22
     23    struct NodeT {
    5324      int first_in,first_out;
    5425      int prev, next;
    5526    };
    56     //Edges are double linked.
    57     //The free edges are only single linked using the "next_in" field.
    58     struct EdgeT
    59     {
     27 
     28    struct EdgeT {
    6029      int head, tail;
    6130      int prev_in, prev_out;
     
    6433
    6534    std::vector<NodeT> nodes;
    66     //The first node
     35
    6736    int first_node;
    68     //The first free node
     37
    6938    int first_free_node;
     39
    7040    std::vector<EdgeT> edges;
    71     //The first free edge
     41
    7242    int first_free_edge;
    7343   
    7444  public:
    7545   
    76     typedef ListGraph Graph;
    77    
    78     class Node;
    79     class Edge;
    80 
    81    
    82   public:
    83 
    84     class NodeIt;
    85     class EdgeIt;
    86     class OutEdgeIt;
    87     class InEdgeIt;
    88 
    89     // Create map registries.
    90     CREATE_MAP_REGISTRIES;
    91     // Create node and edge maps.
    92     CREATE_MAPS(ArrayMap);
    93 
    94   public:
    95 
    96     ListGraph()
     46    typedef ListGraphBase Graph;
     47   
     48    class Node {
     49      friend class Graph;
     50    protected:
     51
     52      int id;
     53      Node(int pid) { id = pid;}
     54
     55    public:
     56      Node() {}
     57      Node (Invalid) { id = -1; }
     58      bool operator==(const Node& node) const {return id == node.id;}
     59      bool operator!=(const Node& node) const {return id != node.id;}
     60      bool operator<(const Node& node) const {return id < node.id;}
     61    };
     62
     63    class Edge {
     64      friend class Graph;
     65    protected:
     66
     67      int id;
     68      Edge(int pid) { id = pid;}
     69
     70    public:
     71      Edge() {}
     72      Edge (Invalid) { id = -1; }
     73      bool operator==(const Edge& edge) const {return id == edge.id;}
     74      bool operator!=(const Edge& edge) const {return id != edge.id;}
     75      bool operator<(const Edge& edge) const {return id < edge.id;}
     76    };
     77
     78
     79
     80    ListGraphBase()
    9781      : nodes(), first_node(-1),
    9882        first_free_node(-1), edges(), first_free_edge(-1) {}
    9983
    100     ListGraph(const ListGraph &_g)
    101       : nodes(_g.nodes), first_node(_g.first_node),
    102         first_free_node(_g.first_free_node), edges(_g.edges),
    103         first_free_edge(_g.first_free_edge) {}
    104    
    105     /// \bug In the vector can be hole if a node is erased from the graph.
    106     ///Number of nodes.
    107     int nodeNum() const { return nodes.size(); }
    108     ///Number of edges.
    109     int edgeNum() const { return edges.size(); }
    110 
    111     ///Set the expected maximum number of edges.
    112 
    113     ///With this function, it is possible to set the expected number of edges.
    114     ///The use of this fasten the building of the graph and makes
     84   
    11585    ///it possible to avoid the superfluous memory allocation.
    11686    void reserveEdge(int n) { edges.reserve(n); };
     
    12191    ///\sa id(Node)
    12292    int maxNodeId() const { return nodes.size()-1; }
     93
    12394    /// Maximum edge ID.
    12495   
     
    12798    int maxEdgeId() const { return edges.size()-1; }
    12899
    129     Node tail(Edge e) const { return edges[e.n].tail; }
    130     Node head(Edge e) const { return edges[e.n].head; }
    131 
    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; }
    140 
    141     /// Node ID.
    142    
    143     /// The ID of a valid Node is a nonnegative integer not greater than
    144     /// \ref maxNodeId(). The range of the ID's is not surely continuous
    145     /// and the greatest node ID can be actually less then \ref maxNodeId().
    146     ///
    147     /// The ID of the \ref INVALID node is -1.
    148     ///\return The ID of the node \c v.
    149     static int id(Node v) { return v.n; }
    150     /// Edge ID.
    151    
    152     /// The ID of a valid Edge is a nonnegative integer not greater than
    153     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
    154     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
    155     ///
    156     /// The ID of the \ref INVALID edge is -1.
    157     ///\return The ID of the edge \c e.
    158     static int id(Edge e) { return e.n; }
     100    Node tail(Edge e) const { return edges[e.id].tail; }
     101    Node head(Edge e) const { return edges[e.id].head; }
     102
     103
     104    void first(Node& node) const {
     105      node.id = first_node;
     106    }
     107
     108    void next(Node& node) const {
     109      node.id = nodes[node.id].next;
     110    }
     111
     112
     113    void first(Edge& e) const {
     114      int n;
     115      for(n = first_node;
     116          n!=-1 && nodes[n].first_in == -1;
     117          n = nodes[n].next);
     118      e.id = (n == -1) ? -1 : nodes[n].first_in;
     119    }
     120
     121    void next(Edge& edge) const {
     122      if (edges[edge.id].next_in != -1) {
     123        edge.id = edges[edge.id].next_in;
     124      } else {
     125        int n;
     126        for(n = nodes[edges[edge.id].head].next;
     127          n!=-1 && nodes[n].first_in == -1;
     128          n = nodes[n].next);
     129        edge.id = (n == -1) ? -1 : nodes[n].first_in;
     130      }     
     131    }
     132
     133    void firstOut(Edge &e, const Node& v) const {
     134      e.id = nodes[v.id].first_out;
     135    }
     136    void nextOut(Edge &e) const {
     137      e.id=edges[e.id].next_out;
     138    }
     139
     140    void firstIn(Edge &e, const Node& v) const {
     141      e.id = nodes[v.id].first_in;
     142    }
     143    void nextIn(Edge &e) const {
     144      e.id=edges[e.id].next_in;
     145    }
     146
     147   
     148    static int id(Node v) { return v.id; }
     149    static int id(Edge e) { return e.id; }
    159150
    160151    /// Adds a new node to the graph.
     
    162153    /// \warning It adds the new node to the front of the list.
    163154    /// (i.e. the lastly added node becomes the first.)
    164     Node addNode() {
     155    Node addNode() {     
    165156      int n;
    166157     
    167       if(first_free_node==-1)
    168         {
    169           n = nodes.size();
    170           nodes.push_back(NodeT());
    171         }
    172       else {
     158      if(first_free_node==-1) {
     159        n = nodes.size();
     160        nodes.push_back(NodeT());
     161      } else {
    173162        n = first_free_node;
    174163        first_free_node = nodes[n].next;
     
    182171      nodes[n].first_in = nodes[n].first_out = -1;
    183172     
    184       Node nn; nn.n=n;
    185 
    186       //Update dynamic maps
    187       node_maps.add(nn);
    188 
    189       return nn;
     173      return Node(n);
    190174    }
    191175   
    192176    Edge addEdge(Node u, Node v) {
    193       int n;
    194      
    195       if(first_free_edge==-1)
    196         {
    197           n = edges.size();
    198           edges.push_back(EdgeT());
    199         }
    200       else {
     177      int n;     
     178
     179      if (first_free_edge == -1) {
     180        n = edges.size();
     181        edges.push_back(EdgeT());
     182      } else {
    201183        n = first_free_edge;
    202184        first_free_edge = edges[n].next_in;
    203185      }
    204186     
    205       edges[n].tail = u.n; edges[n].head = v.n;
    206 
    207       edges[n].next_out = nodes[u.n].first_out;
    208       if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
    209       edges[n].next_in = nodes[v.n].first_in;
    210       if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
     187      edges[n].tail = u.id;
     188      edges[n].head = v.id;
     189
     190      edges[n].next_out = nodes[u.id].first_out;
     191      if(nodes[u.id].first_out != -1) {
     192        edges[nodes[u.id].first_out].prev_out = n;
     193      }
     194     
     195      edges[n].next_in = nodes[v.id].first_in;
     196      if(nodes[v.id].first_in != -1) {
     197        edges[nodes[v.id].first_in].prev_in = n;
     198      }
     199     
    211200      edges[n].prev_in = edges[n].prev_out = -1;
    212201       
    213       nodes[u.n].first_out = nodes[v.n].first_in = n;
    214 
    215       Edge e; e.n=n;
    216 
    217       //Update dynamic maps
    218       edge_maps.add(e);
    219 
    220       return e;
    221     }
    222    
    223     /// Finds an edge between two nodes.
    224 
    225     /// Finds an edge from node \c u to node \c v.
    226     ///
    227     /// If \c prev is \ref INVALID (this is the default value), then
    228     /// It finds the first edge from \c u to \c v. Otherwise it looks for
    229     /// the next edge from \c u to \c v after \c prev.
    230     /// \return The found edge or INVALID if there is no such an edge.
    231     Edge findEdge(Node u,Node v, Edge prev = INVALID)
    232     {
    233       int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
    234       while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;
    235       prev.n=e;
    236       return prev;
    237     }
    238    
    239   private:
    240     void eraseEdge(int n) {
    241      
    242       if(edges[n].next_in!=-1)
     202      nodes[u.id].first_out = nodes[v.id].first_in = n;
     203
     204      return Edge(n);
     205    }
     206   
     207    void erase(const Node& node) {
     208      int n = node.id;
     209     
     210      if(nodes[n].next != -1) {
     211        nodes[nodes[n].next].prev = nodes[n].prev;
     212      }
     213     
     214      if(nodes[n].prev != -1) {
     215        nodes[nodes[n].prev].next = nodes[n].next;
     216      } else {
     217        first_node = nodes[n].next;
     218      }
     219     
     220      nodes[n].next = first_free_node;
     221      first_free_node = n;
     222
     223    }
     224   
     225    void erase(const Edge& edge) {
     226      int n = edge.id;
     227     
     228      if(edges[n].next_in!=-1) {
    243229        edges[edges[n].next_in].prev_in = edges[n].prev_in;
    244       if(edges[n].prev_in!=-1)
     230      }
     231
     232      if(edges[n].prev_in!=-1) {
    245233        edges[edges[n].prev_in].next_in = edges[n].next_in;
    246       else nodes[edges[n].head].first_in = edges[n].next_in;
    247      
    248       if(edges[n].next_out!=-1)
     234      } else {
     235        nodes[edges[n].head].first_in = edges[n].next_in;
     236      }
     237
     238     
     239      if(edges[n].next_out!=-1) {
    249240        edges[edges[n].next_out].prev_out = edges[n].prev_out;
    250       if(edges[n].prev_out!=-1)
     241      }
     242
     243      if(edges[n].prev_out!=-1) {
    251244        edges[edges[n].prev_out].next_out = edges[n].next_out;
    252       else nodes[edges[n].tail].first_out = edges[n].next_out;
     245      } else {
     246        nodes[edges[n].tail].first_out = edges[n].next_out;
     247      }
    253248     
    254249      edges[n].next_in = first_free_edge;
    255250      first_free_edge = n;     
    256251
    257       //Update dynamic maps
    258       Edge e; e.n=n;
    259       edge_maps.erase(e);
    260 
    261     }
    262      
    263   public:
    264 
    265     void erase(Node nn) {
    266       int n=nn.n;
    267      
    268       int m;
    269       while((m=nodes[n].first_in)!=-1) eraseEdge(m);
    270       while((m=nodes[n].first_out)!=-1) eraseEdge(m);
    271 
    272       if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
    273       if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
    274       else first_node = nodes[n].next;
    275      
    276       nodes[n].next = first_free_node;
    277       first_free_node = n;
    278 
    279       //Update dynamic maps
    280       node_maps.erase(nn);
    281 
    282     }
    283    
    284     void erase(Edge e) { eraseEdge(e.n); }
     252    }
    285253
    286254    void clear() {
    287       edge_maps.clear();
    288255      edges.clear();
    289       node_maps.clear();
    290256      nodes.clear();
    291       first_node=first_free_node=first_free_edge=-1;
    292     }
    293 
    294     class Node {
    295       friend class ListGraph;
    296       template <typename T> friend class NodeMap;
    297        
    298       friend class Edge;
    299       friend class OutEdgeIt;
    300       friend class InEdgeIt;
    301       friend class SymEdge;
    302 
    303     protected:
    304       int n;
    305       friend int ListGraph::id(Node v);
    306       Node(int nn) {n=nn;}
    307     public:
    308       Node() {}
    309       Node (Invalid) { n=-1; }
    310       bool operator==(const Node i) const {return n==i.n;}
    311       bool operator!=(const Node i) const {return n!=i.n;}
    312       bool operator<(const Node i) const {return n<i.n;}
    313       //      ///Validity check
    314       //      operator bool() { return n!=-1; }
    315     };
    316    
    317     class NodeIt : public Node {
    318       const ListGraph *G;
    319       friend class ListGraph;
    320     public:
    321       NodeIt() : Node() { }
    322       NodeIt(Invalid i) : Node(i) { }
    323       NodeIt(const ListGraph& _G) : Node(_G.first_node), G(&_G) { }
    324       NodeIt(const ListGraph& _G,Node n) : Node(n), G(&_G) { }
    325       NodeIt &operator++() {
    326         n=G->nodes[n].next;
    327         return *this;
    328       }
    329       //      ///Validity check
    330       //      operator bool() { return Node::operator bool(); }     
    331     };
    332 
    333     class Edge {
    334       friend class ListGraph;
    335       template <typename T> friend class EdgeMap;
    336 
    337       friend class SymListGraph;
    338      
    339       friend class Node;
    340       friend class NodeIt;
    341     protected:
    342       int n;
    343       friend int ListGraph::id(Edge e);
    344 
    345     public:
    346       /// An Edge with id \c n.
    347 
    348       /// \bug It should be
    349       /// obtained by a member function of the Graph.
    350       Edge(int nn) {n=nn;}
    351 
    352       Edge() { }
    353       Edge (Invalid) { n=-1; }
    354       bool operator==(const Edge i) const {return n==i.n;}
    355       bool operator!=(const Edge i) const {return n!=i.n;}
    356       bool operator<(const Edge i) const {return n<i.n;}
    357       //      ///Validity check
    358       //      operator bool() { return n!=-1; }
    359    };
    360    
    361     class EdgeIt : public Edge {
    362       const ListGraph *G;
    363       friend class ListGraph;
    364     public:
    365       EdgeIt(const ListGraph& _G) : Edge(), G(&_G) {
    366         int m;
    367         for(m=_G.first_node;
    368             m!=-1 && _G.nodes[m].first_in == -1; m = _G.nodes[m].next);
    369         n = (m==-1)?-1:_G.nodes[m].first_in;
    370       }
    371       EdgeIt (Invalid i) : Edge(i) { }
    372       EdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
    373       EdgeIt() : Edge() { }
    374       EdgeIt &operator++() {
    375         if(G->edges[n].next_in!=-1) n=G->edges[n].next_in;
    376         else {
    377           int nn;
    378           for(nn=G->nodes[G->edges[n].head].next;
    379               nn!=-1 && G->nodes[nn].first_in == -1;
    380               nn = G->nodes[nn].next) ;
    381           n = (nn==-1)?-1:G->nodes[nn].first_in;
    382         }
    383         return *this;
    384       }
    385       //      ///Validity check
    386       //      operator bool() { return Edge::operator bool(); }     
    387     };
    388    
    389     class OutEdgeIt : public Edge {
    390       const ListGraph *G;
    391       friend class ListGraph;
    392     public:
    393       OutEdgeIt() : Edge() { }
    394       OutEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
    395       OutEdgeIt (Invalid i) : Edge(i) { }
    396 
    397       OutEdgeIt(const ListGraph& _G,const Node v)
    398         : Edge(_G.nodes[v.n].first_out), G(&_G) {}
    399       OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
    400       //      ///Validity check
    401       //      operator bool() { return Edge::operator bool(); }     
    402     };
    403    
    404     class InEdgeIt : public Edge {
    405       const ListGraph *G;
    406       friend class ListGraph;
    407     public:
    408       InEdgeIt() : Edge() { }
    409       InEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
    410       InEdgeIt (Invalid i) : Edge(i) { }
    411       InEdgeIt(const ListGraph& _G,Node v)
    412         : Edge(_G.nodes[v.n].first_in), G(&_G) { }
    413       InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
    414       //      ///Validity check
    415       //      operator bool() { return Edge::operator bool(); }     
    416     };
     257      first_node = first_free_node = first_free_edge = -1;
     258    }
     259
    417260  };
    418261
    419   ///Graph for bidirectional edges.
    420 
    421   ///The purpose of this graph structure is to handle graphs
    422   ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
    423   ///of oppositely directed edges.
    424   ///There is a new edge map type called
    425   ///\ref lemon::SymListGraph::SymEdgeMap "SymEdgeMap"
    426   ///that complements this
    427   ///feature by
    428   ///storing shared values for the edge pairs. The usual
    429   ///\ref lemon::skeleton::StaticGraph::EdgeMap "EdgeMap"
    430   ///can be used
    431   ///as well.
    432   ///
    433   ///The oppositely directed edge can also be obtained easily
    434   ///using \ref lemon::SymListGraph::opposite() "opposite()" member function.
    435   ///
    436   ///Here erase(Edge) deletes a pair of edges.
    437   ///
    438   ///\todo this date structure need some reconsiderations. Maybe it
    439   ///should be implemented independently from ListGraph.
    440   /* 
    441   class SymListGraph : public ListGraph
    442   {
    443   public:
    444 
    445     typedef SymListGraph Graph;
    446 
    447     // Create symmetric map registry.
    448     CREATE_SYM_EDGE_MAP_REGISTRY;
    449     // Create symmetric edge map.
    450     CREATE_SYM_EDGE_MAP(ArrayMap);
    451 
    452     SymListGraph() : ListGraph() { }
    453     SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
    454     ///Adds a pair of oppositely directed edges to the graph.
    455     Edge addEdge(Node u, Node v)
    456     {
    457       Edge e = ListGraph::addEdge(u,v);
    458       Edge f = ListGraph::addEdge(v,u);
    459       sym_edge_maps.add(e);
    460       sym_edge_maps.add(f);
    461      
    462       return e;
    463     }
    464 
    465     void erase(Node n) { ListGraph::erase(n);}
    466     ///The oppositely directed edge.
    467 
    468     ///Returns the oppositely directed
    469     ///pair of the edge \c e.
    470     static Edge opposite(Edge e)
    471     {
    472       Edge f;
    473       f.n = e.n - 2*(e.n%2) + 1;
    474       return f;
    475     }
    476    
    477     ///Removes a pair of oppositely directed edges to the graph.
    478     void erase(Edge e) {
    479       Edge f = opposite(e);
    480       sym_edge_maps.erase(e);
    481       sym_edge_maps.erase(f);
    482       ListGraph::erase(f);
    483       ListGraph::erase(e);
    484     }   
    485     };*/
    486 
    487   class SymListGraph : public ListGraph {
    488     typedef ListGraph Parent;
    489   public:
    490 
    491     typedef SymListGraph Graph;
    492 
    493     typedef ListGraph::Node Node;
    494     typedef ListGraph::NodeIt NodeIt;
    495 
    496     class SymEdge;
    497     class SymEdgeIt;
    498 
    499     class Edge;
    500     class EdgeIt;
    501     class OutEdgeIt;
    502     class InEdgeIt;
    503 
    504     template <typename Value>
    505     class NodeMap : public Parent::NodeMap<Value> {     
    506     public:
    507       NodeMap(const SymListGraph& g)
    508         : SymListGraph::Parent::NodeMap<Value>(g) {}
    509       NodeMap(const SymListGraph& g, Value v)
    510         : SymListGraph::Parent::NodeMap<Value>(g, v) {}
    511       template<typename TT>
    512       NodeMap(const NodeMap<TT>& copy)
    513         : SymListGraph::Parent::NodeMap<Value>(copy) { }           
    514     };
    515 
    516     template <typename Value>
    517     class SymEdgeMap : public Parent::EdgeMap<Value> {
    518     public:
    519       typedef SymEdge KeyType;
    520 
    521       SymEdgeMap(const SymListGraph& g)
    522         : SymListGraph::Parent::EdgeMap<Value>(g) {}
    523       SymEdgeMap(const SymListGraph& g, Value v)
    524         : SymListGraph::Parent::EdgeMap<Value>(g, v) {}
    525       template<typename TT>
    526       SymEdgeMap(const SymEdgeMap<TT>& copy)
    527         : SymListGraph::Parent::EdgeMap<Value>(copy) { }
    528      
    529     };
    530 
    531     // Create edge map registry.
    532     CREATE_EDGE_MAP_REGISTRY;
    533     // Create edge maps.
    534     CREATE_EDGE_MAP(ArrayMap);
    535 
    536     class Edge {
    537       friend class SymListGraph;
    538       friend class SymListGraph::EdgeIt;
    539       friend class SymListGraph::OutEdgeIt;
    540       friend class SymListGraph::InEdgeIt;
    541      
    542     protected:
    543       int id;
    544 
    545       Edge(int pid) { id = pid; }
    546 
    547     public:
    548       /// An Edge with id \c n.
    549 
    550       Edge() { }
    551       Edge (Invalid) { id = -1; }
    552 
    553       operator SymEdge(){ return SymEdge(id >> 1);}
    554      
    555       bool operator==(const Edge i) const {return id == i.id;}
    556       bool operator!=(const Edge i) const {return id != i.id;}
    557       bool operator<(const Edge i) const {return id < i.id;}
    558       //      ///Validity check
    559       //      operator bool() { return n!=-1; }
    560     };
    561 
    562     class SymEdge : public ListGraph::Edge {
    563       friend class SymListGraph;
    564       friend class SymListGraph::Edge;
    565       typedef ListGraph::Edge Parent;
    566 
    567     protected:     
    568       SymEdge(int pid) : Parent(pid) {}
    569     public:
    570 
    571       SymEdge() { }
    572       SymEdge(const ListGraph::Edge& i) : Parent(i) {}
    573       SymEdge (Invalid) : Parent(INVALID) {}
    574 
    575     };
    576 
    577     class OutEdgeIt {
    578       Parent::OutEdgeIt out;
    579       Parent::InEdgeIt in;     
    580     public:
    581       OutEdgeIt() {}
    582       OutEdgeIt(const SymListGraph& g, Edge e) {
    583         if ((e.id & 1) == 0) { 
    584           out = Parent::OutEdgeIt(g, SymEdge(e));
    585           in = Parent::InEdgeIt(g, g.tail(e));
    586         } else {
    587           out = Parent::OutEdgeIt(INVALID);
    588           in = Parent::InEdgeIt(g, SymEdge(e));
    589         }
    590       }
    591       OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
    592 
    593       OutEdgeIt(const SymListGraph& g, const Node v)
    594         : out(g, v), in(g, v) {}
    595       OutEdgeIt &operator++() {
    596         if (out != INVALID) {
    597           ++out;
    598         } else {
    599           ++in;
    600         }
    601         return *this;
    602       }
    603 
    604       operator Edge() const {
    605         if (out == INVALID && in == INVALID) return INVALID;
    606         return out != INVALID ? forward(out) : backward(in);
    607       }
    608 
    609       bool operator==(const Edge i) const {return Edge(*this) == i;}
    610       bool operator!=(const Edge i) const {return Edge(*this) != i;}
    611       bool operator<(const Edge i) const {return Edge(*this) < i;}
    612     };
    613 
    614     class InEdgeIt {
    615       Parent::OutEdgeIt out;
    616       Parent::InEdgeIt in;     
    617     public:
    618       InEdgeIt() {}
    619       InEdgeIt(const SymListGraph& g, Edge e) {
    620         if ((e.id & 1) == 0) { 
    621           out = Parent::OutEdgeIt(g, SymEdge(e));
    622           in = Parent::InEdgeIt(g, g.tail(e));
    623         } else {
    624           out = Parent::OutEdgeIt(INVALID);
    625           in = Parent::InEdgeIt(g, SymEdge(e));
    626         }
    627       }
    628       InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
    629 
    630       InEdgeIt(const SymListGraph& g, const Node v)
    631         : out(g, v), in(g, v) {}
    632 
    633       InEdgeIt &operator++() {
    634         if (out != INVALID) {
    635           ++out;
    636         } else {
    637           ++in;
    638         }
    639         return *this;
    640       }
    641 
    642       operator Edge() const {
    643         if (out == INVALID && in == INVALID) return INVALID;
    644         return out != INVALID ? backward(out) : forward(in);
    645       }
    646 
    647       bool operator==(const Edge i) const {return Edge(*this) == i;}
    648       bool operator!=(const Edge i) const {return Edge(*this) != i;}
    649       bool operator<(const Edge i) const {return Edge(*this) < i;}
    650     };
    651 
    652     class SymEdgeIt : public Parent::EdgeIt {
    653 
    654     public:
    655       SymEdgeIt() {}
    656 
    657       SymEdgeIt(const SymListGraph& g)
    658         : SymListGraph::Parent::EdgeIt(g) {}
    659 
    660       SymEdgeIt(const SymListGraph& g, SymEdge e)
    661         : SymListGraph::Parent::EdgeIt(g, e) {}
    662 
    663       SymEdgeIt(Invalid i)
    664         : SymListGraph::Parent::EdgeIt(INVALID) {}
    665 
    666       SymEdgeIt& operator++() {
    667         SymListGraph::Parent::EdgeIt::operator++();
    668         return *this;
    669       }
    670 
    671       operator SymEdge() const {
    672         return SymEdge
    673           (static_cast<const SymListGraph::Parent::EdgeIt&>(*this));
    674       }
    675       bool operator==(const SymEdge i) const {return SymEdge(*this) == i;}
    676       bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;}
    677       bool operator<(const SymEdge i) const {return SymEdge(*this) < i;}
    678     };
    679 
    680     class EdgeIt {
    681       SymEdgeIt it;
    682       bool fw;
    683     public:
    684       EdgeIt(const SymListGraph& g) : it(g), fw(true) {}
    685       EdgeIt (Invalid i) : it(i) { }
    686       EdgeIt(const SymListGraph& g, Edge e)
    687         : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { }
    688       EdgeIt() { }
    689       EdgeIt& operator++() {
    690         fw = !fw;
    691         if (fw) ++it;
    692         return *this;
    693       }
    694       operator Edge() const {
    695         if (it == INVALID) return INVALID;
    696         return fw ? forward(it) : backward(it);
    697       }
    698       bool operator==(const Edge i) const {return Edge(*this) == i;}
    699       bool operator!=(const Edge i) const {return Edge(*this) != i;}
    700       bool operator<(const Edge i) const {return Edge(*this) < i;}
    701 
    702     };
    703 
    704     ///Number of nodes.
    705     int nodeNum() const { return Parent::nodeNum(); }
    706     ///Number of edges.
    707     int edgeNum() const { return 2*Parent::edgeNum(); }
    708     ///Number of symmetric edges.
    709     int symEdgeNum() const { return Parent::edgeNum(); }
    710 
    711     ///Set the expected maximum number of edges.
    712 
    713     ///With this function, it is possible to set the expected number of edges.
    714     ///The use of this fasten the building of the graph and makes
    715     ///it possible to avoid the superfluous memory allocation.
    716     void reserveSymEdge(int n) { Parent::reserveEdge(n); };
    717    
    718     /// Maximum node ID.
    719    
    720     /// Maximum node ID.
    721     ///\sa id(Node)
    722     int maxNodeId() const { return Parent::maxNodeId(); }
    723     /// Maximum edge ID.
    724    
    725     /// Maximum edge ID.
    726     ///\sa id(Edge)
    727     int maxEdgeId() const { return 2*Parent::maxEdgeId(); }
    728     /// Maximum symmetric edge ID.
    729    
    730     /// Maximum symmetric edge ID.
    731     ///\sa id(SymEdge)
    732     int maxSymEdgeId() const { return Parent::maxEdgeId(); }
    733 
    734 
    735     Node tail(Edge e) const {
    736       return (e.id & 1) == 0 ?
    737         Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e));
    738     }
    739 
    740     Node head(Edge e) const {
    741       return (e.id & 1) == 0 ?
    742         Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e));
    743     }
    744 
    745     Node tail(SymEdge e) const {
    746       return Parent::tail(e);
    747     }
    748 
    749     Node head(SymEdge e) const {
    750       return Parent::head(e);
    751     }
    752 
    753     NodeIt& first(NodeIt& v) const {
    754       v=NodeIt(*this); return v; }
    755     EdgeIt& first(EdgeIt& e) const {
    756       e=EdgeIt(*this); return e; }
    757     SymEdgeIt& first(SymEdgeIt& e) const {
    758       e=SymEdgeIt(*this); return e; }
    759     OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
    760       e=OutEdgeIt(*this,v); return e; }
    761     InEdgeIt& first(InEdgeIt& e, const Node v) const {
    762       e=InEdgeIt(*this,v); return e; }
    763 
    764     /// Node ID.
    765    
    766     /// The ID of a valid Node is a nonnegative integer not greater than
    767     /// \ref maxNodeId(). The range of the ID's is not surely continuous
    768     /// and the greatest node ID can be actually less then \ref maxNodeId().
    769     ///
    770     /// The ID of the \ref INVALID node is -1.
    771     ///\return The ID of the node \c v.
    772     static int id(Node v) { return Parent::id(v); }
    773     /// Edge ID.
    774    
    775     /// The ID of a valid Edge is a nonnegative integer not greater than
    776     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
    777     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
    778     ///
    779     /// The ID of the \ref INVALID edge is -1.
    780     ///\return The ID of the edge \c e.
    781     static int id(Edge e) { return e.id; }
    782 
    783     /// The ID of a valid SymEdge is a nonnegative integer not greater than
    784     /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous
    785     /// and the greatest edge ID can be actually less then \ref maxSymEdgeId().
    786     ///
    787     /// The ID of the \ref INVALID symmetric edge is -1.
    788     ///\return The ID of the edge \c e.
    789     static int id(SymEdge e) { return Parent::id(e); }
    790 
    791     /// Adds a new node to the graph.
    792 
    793     /// \warning It adds the new node to the front of the list.
    794     /// (i.e. the lastly added node becomes the first.)
    795     Node addNode() {
    796       return Parent::addNode();
    797     }
    798    
    799     SymEdge addEdge(Node u, Node v) {
    800       SymEdge se = Parent::addEdge(u, v);
    801       edge_maps.add(forward(se));
    802       edge_maps.add(backward(se));
    803       return se;
    804     }
    805    
    806     /// Finds an edge between two nodes.
    807 
    808     /// Finds an edge from node \c u to node \c v.
    809     ///
    810     /// If \c prev is \ref INVALID (this is the default value), then
    811     /// It finds the first edge from \c u to \c v. Otherwise it looks for
    812     /// the next edge from \c u to \c v after \c prev.
    813     /// \return The found edge or INVALID if there is no such an edge.
    814     Edge findEdge(Node u, Node v, Edge prev = INVALID)
    815     {     
    816       if (prev == INVALID || id(prev) & 1 == 0) {
    817         SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
    818         if (se != INVALID) return forward(se);
    819       } else {
    820         SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
    821         if (se != INVALID) return backward(se);
    822       }
    823       return INVALID;
    824     }
    825 
    826 //     /// Finds an symmetric edge between two nodes.
    827 
    828 //     /// Finds an symmetric edge from node \c u to node \c v.
    829 //     ///
    830 //     /// If \c prev is \ref INVALID (this is the default value), then
    831 //     /// It finds the first edge from \c u to \c v. Otherwise it looks for
    832 //     /// the next edge from \c u to \c v after \c prev.
    833 //     /// \return The found edge or INVALID if there is no such an edge.
    834 
    835 //     SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID)
    836 //     {     
    837 //       if (prev == INVALID || id(prev) & 1 == 0) {
    838 //      SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
    839 //      if (se != INVALID) return se;
    840 //       } else {
    841 //      SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
    842 //      if (se != INVALID) return se;   
    843 //       }
    844 //       return INVALID;
    845 //     }
    846    
    847   public:
    848 
    849     void erase(Node n) {     
    850       for (OutEdgeIt it(*this, n); it != INVALID; ++it) {
    851         edge_maps.erase(it);
    852         edge_maps.erase(opposite(it));
    853       }
    854       Parent::erase(n);
    855     }
    856    
    857     void erase(SymEdge e) {
    858       edge_maps.erase(forward(e));
    859       edge_maps.erase(backward(e));
    860       Parent::erase(e);
    861     };
    862 
    863     void clear() {
    864       edge_maps.clear();
    865       Parent::clear();
    866     }
    867 
    868     static Edge opposite(Edge e) {
    869       return Edge(id(e) ^ 1);
    870     }
    871 
    872     static Edge forward(SymEdge e) {
    873       return Edge(id(e) << 1);
    874     }
    875 
    876     static Edge backward(SymEdge e) {
    877       return Edge((id(e) << 1) | 1);
    878     }
    879 
    880   };
    881 
    882   ///A graph class containing only nodes.
    883 
    884   ///This class implements a graph structure without edges.
    885   ///The most useful application of this class is to be the node set of an
    886   ///\ref EdgeSet class.
    887   ///
    888   ///It conforms to
    889   ///the \ref skeleton::ExtendableGraph "ExtendableGraph" concept
    890   ///with the exception that you cannot
    891   ///add (or delete) edges. The usual edge iterators are exists, but they are
    892   ///always \ref INVALID.
    893   ///\sa skeleton::ExtendableGraph
    894   ///\sa EdgeSet
    895   class NodeSet {
    896 
    897     //Nodes are double linked.
    898     //The free nodes are only single linked using the "next" field.
    899     struct NodeT
    900     {
    901       int first_in,first_out;
    902       int prev, next;
    903       //      NodeT() {}
    904     };
    905 
    906     std::vector<NodeT> nodes;
    907     //The first node
    908     int first_node;
    909     //The first free node
    910     int first_free_node;
    911    
    912   public:
    913 
    914     typedef NodeSet Graph;
    915    
    916     class Node;
    917     class Edge;
    918 
    919   public:
    920 
    921     class NodeIt;
    922     class EdgeIt;
    923     class OutEdgeIt;
    924     class InEdgeIt;
    925    
    926     // Create node map registry.
    927     CREATE_NODE_MAP_REGISTRY;
    928     // Create node maps.
    929     CREATE_NODE_MAP(ArrayMap);
    930 
    931     /// Creating empty map structure for edges.
    932     template <typename Value>
    933     class EdgeMap {
    934     public:
    935       EdgeMap(const Graph&) {}
    936       EdgeMap(const Graph&, const Value&) {}
    937 
    938       EdgeMap(const EdgeMap&) {}
    939       template <typename CMap> EdgeMap(const CMap&) {}
    940 
    941       EdgeMap& operator=(const EdgeMap&) {}
    942       template <typename CMap> EdgeMap& operator=(const CMap&) {}
    943      
    944       class ConstIterator {
    945       public:
    946         bool operator==(const ConstIterator&) {return true;}
    947         bool operator!=(const ConstIterator&) {return false;}
    948       };
    949 
    950       typedef ConstIterator Iterator;
    951      
    952       Iterator begin() { return Iterator();}
    953       Iterator end() { return Iterator();}
    954 
    955       ConstIterator begin() const { return ConstIterator();}
    956       ConstIterator end() const { return ConstIterator();}
    957 
    958     };
    959    
    960   public:
    961 
    962     ///Default constructor
    963     NodeSet()
    964       : nodes(), first_node(-1), first_free_node(-1) {}
    965     ///Copy constructor
    966     NodeSet(const NodeSet &_g)
    967       : nodes(_g.nodes), first_node(_g.first_node),
    968         first_free_node(_g.first_free_node) {}
    969    
    970     ///Number of nodes.
    971     int nodeNum() const { return nodes.size(); }
    972     ///Number of edges.
    973     int edgeNum() const { return 0; }
    974 
    975     /// Maximum node ID.
    976    
    977     /// Maximum node ID.
    978     ///\sa id(Node)
    979     int maxNodeId() const { return nodes.size()-1; }
    980     /// Maximum edge ID.
    981    
    982     /// Maximum edge ID.
    983     ///\sa id(Edge)
    984     int maxEdgeId() const { return 0; }
    985 
    986     Node tail(Edge e) const { return INVALID; }
    987     Node head(Edge e) const { return INVALID; }
    988 
    989     NodeIt& first(NodeIt& v) const {
    990       v=NodeIt(*this); return v; }
    991     EdgeIt& first(EdgeIt& e) const {
    992       e=EdgeIt(*this); return e; }
    993     OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
    994       e=OutEdgeIt(*this,v); return e; }
    995     InEdgeIt& first(InEdgeIt& e, const Node v) const {
    996       e=InEdgeIt(*this,v); return e; }
    997 
    998     /// Node ID.
    999    
    1000     /// The ID of a valid Node is a nonnegative integer not greater than
    1001     /// \ref maxNodeId(). The range of the ID's is not surely continuous
    1002     /// and the greatest node ID can be actually less then \ref maxNodeId().
    1003     ///
    1004     /// The ID of the \ref INVALID node is -1.
    1005     ///\return The ID of the node \c v.
    1006     static int id(Node v) { return v.n; }
    1007     /// Edge ID.
    1008    
    1009     /// The ID of a valid Edge is a nonnegative integer not greater than
    1010     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
    1011     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
    1012     ///
    1013     /// The ID of the \ref INVALID edge is -1.
    1014     ///\return The ID of the edge \c e.
    1015     static int id(Edge e) { return -1; }
    1016 
    1017     /// Adds a new node to the graph.
    1018 
    1019     /// \warning It adds the new node to the front of the list.
    1020     /// (i.e. the lastly added node becomes the first.)
    1021     Node addNode() {
    1022       int n;
    1023      
    1024       if(first_free_node==-1)
    1025         {
    1026           n = nodes.size();
    1027           nodes.push_back(NodeT());
    1028         }
    1029       else {
    1030         n = first_free_node;
    1031         first_free_node = nodes[n].next;
    1032       }
    1033      
    1034       nodes[n].next = first_node;
    1035       if(first_node != -1) nodes[first_node].prev = n;
    1036       first_node = n;
    1037       nodes[n].prev = -1;
    1038      
    1039       nodes[n].first_in = nodes[n].first_out = -1;
    1040      
    1041       Node nn; nn.n=n;
    1042 
    1043       //Update dynamic maps
    1044       node_maps.add(nn);
    1045 
    1046       return nn;
    1047     }
    1048    
    1049     void erase(Node nn) {
    1050       int n=nn.n;
    1051      
    1052       if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
    1053       if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
    1054       else first_node = nodes[n].next;
    1055      
    1056       nodes[n].next = first_free_node;
    1057       first_free_node = n;
    1058 
    1059       //Update dynamic maps
    1060       node_maps.erase(nn);
    1061     }
    1062    
    1063        
    1064     Edge findEdge(Node u,Node v, Edge prev = INVALID)
    1065     {
    1066       return INVALID;
    1067     }
    1068    
    1069     void clear() {
    1070       node_maps.clear();
    1071       nodes.clear();
    1072       first_node = first_free_node = -1;
    1073     }
    1074 
    1075     class Node {
    1076       friend class NodeSet;
    1077       template <typename T> friend class NodeMap;
    1078      
    1079       friend class Edge;
    1080       friend class OutEdgeIt;
    1081       friend class InEdgeIt;
    1082 
    1083     protected:
    1084       int n;
    1085       friend int NodeSet::id(Node v);
    1086       Node(int nn) {n=nn;}
    1087     public:
    1088       Node() {}
    1089       Node (Invalid i) { n=-1; }
    1090       bool operator==(const Node i) const {return n==i.n;}
    1091       bool operator!=(const Node i) const {return n!=i.n;}
    1092       bool operator<(const Node i) const {return n<i.n;}
    1093     };
    1094    
    1095     class NodeIt : public Node {
    1096       const NodeSet *G;
    1097       friend class NodeSet;
    1098     public:
    1099       NodeIt() : Node() { }
    1100       NodeIt(const NodeSet& _G,Node n) : Node(n), G(&_G) { }
    1101       NodeIt(Invalid i) : Node(i) { }
    1102       NodeIt(const NodeSet& _G) : Node(_G.first_node), G(&_G) { }
    1103       NodeIt &operator++() {
    1104         n=G->nodes[n].next;
    1105         return *this;
    1106       }
    1107     };
    1108 
    1109     class Edge {
    1110     public:
    1111       Edge() { }
    1112       Edge (Invalid) { }
    1113       bool operator==(const Edge i) const {return true;}
    1114       bool operator!=(const Edge i) const {return false;}
    1115       bool operator<(const Edge i) const {return false;}
    1116     };
    1117    
    1118     class EdgeIt : public Edge {
    1119     public:
    1120       EdgeIt(const NodeSet& G) : Edge() { }
    1121       EdgeIt(const NodeSet&, Edge) : Edge() { }
    1122       EdgeIt (Invalid i) : Edge(i) { }
    1123       EdgeIt() : Edge() { }
    1124       EdgeIt operator++() { return INVALID; }
    1125     };
    1126    
    1127     class OutEdgeIt : public Edge {
    1128       friend class NodeSet;
    1129     public:
    1130       OutEdgeIt() : Edge() { }
    1131       OutEdgeIt(const NodeSet&, Edge) : Edge() { }
    1132       OutEdgeIt (Invalid i) : Edge(i) { }
    1133       OutEdgeIt(const NodeSet& G,const Node v)  : Edge() {}
    1134       OutEdgeIt operator++() { return INVALID; }
    1135     };
    1136    
    1137     class InEdgeIt : public Edge {
    1138       friend class NodeSet;
    1139     public:
    1140       InEdgeIt() : Edge() { }
    1141       InEdgeIt(const NodeSet&, Edge) : Edge() { }
    1142       InEdgeIt (Invalid i) : Edge(i) { }
    1143       InEdgeIt(const NodeSet& G,Node v) :Edge() {}
    1144       InEdgeIt operator++() { return INVALID; }
    1145     };
    1146 
    1147   };
    1148 
    1149 
    1150 
    1151   ///Graph structure using a node set of another graph.
    1152 
    1153   ///This structure can be used to establish another graph over a node set
    1154   /// of an existing one. The node iterator will go through the nodes of the
    1155   /// original graph, and the NodeMap's of both graphs will convert to
    1156   /// each other.
    1157   ///
    1158   ///\warning Adding or deleting nodes from the graph is not safe if an
    1159   ///\ref EdgeSet is currently attached to it!
    1160   ///
    1161   ///\todo Make it possible to add/delete edges from the base graph
    1162   ///(and from \ref EdgeSet, as well)
    1163   ///
    1164   ///\param GG The type of the graph which shares its node set with this class.
    1165   ///Its interface must conform to the
    1166   ///\ref skeleton::StaticGraph "StaticGraph" concept.
    1167   ///
    1168   ///It conforms to the
    1169   ///\ref skeleton::ExtendableGraph "ExtendableGraph" concept.
    1170   ///\sa skeleton::ExtendableGraph.
    1171   ///\sa NodeSet.
    1172   template<typename GG>
    1173   class EdgeSet {
    1174 
    1175     typedef GG NodeGraphType;
    1176 
    1177     NodeGraphType &G;
    1178 
    1179   public:
    1180 
    1181     class Node;
    1182     class Edge;
    1183     class OutEdgeIt;
    1184     class InEdgeIt;
    1185     class SymEdge;
    1186 
    1187     typedef EdgeSet Graph;
    1188 
    1189     int id(Node v) const;
    1190 
    1191     class Node : public NodeGraphType::Node {
    1192       friend class EdgeSet;
    1193      
    1194       friend class Edge;
    1195       friend class OutEdgeIt;
    1196       friend class InEdgeIt;
    1197       friend class SymEdge;
    1198 
    1199     public:
    1200       friend int EdgeSet::id(Node v) const;
    1201     public:
    1202       Node() : NodeGraphType::Node() {}
    1203       Node (Invalid i) : NodeGraphType::Node(i) {}
    1204       Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
    1205     };
    1206    
    1207     class NodeIt : public NodeGraphType::NodeIt {
    1208       friend class EdgeSet;
    1209     public:
    1210       NodeIt() : NodeGraphType::NodeIt() { }
    1211       NodeIt(const EdgeSet& _G,Node n) : NodeGraphType::NodeIt(_G.G,n) { }
    1212       NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
    1213       NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
    1214       NodeIt(const typename NodeGraphType::NodeIt &n)
    1215         : NodeGraphType::NodeIt(n) {}
    1216 
    1217       operator Node() { return Node(*this);}
    1218       NodeIt &operator++()
    1219       { this->NodeGraphType::NodeIt::operator++(); return *this;}
    1220     };
    1221 
    1222   private:
    1223     //Edges are double linked.
    1224     //The free edges are only single linked using the "next_in" field.
    1225     struct NodeT
    1226     {
    1227       int first_in,first_out;
    1228       NodeT() : first_in(-1), first_out(-1) { }
    1229     };
    1230 
    1231     struct EdgeT
    1232     {
    1233       Node head, tail;
    1234       int prev_in, prev_out;
    1235       int next_in, next_out;
    1236     };
    1237 
    1238    
    1239     typename NodeGraphType::template NodeMap<NodeT> nodes;
    1240    
    1241     std::vector<EdgeT> edges;
    1242     //The first free edge
    1243     int first_free_edge;
    1244    
    1245   public:
    1246    
    1247     class Node;
    1248     class Edge;
    1249 
    1250     class NodeIt;
    1251     class EdgeIt;
    1252     class OutEdgeIt;
    1253     class InEdgeIt;
    1254 
    1255 
    1256     // Create edge map registry.
    1257     CREATE_EDGE_MAP_REGISTRY;
    1258     // Create edge maps.
    1259     CREATE_EDGE_MAP(ArrayMap);
    1260 
    1261     // Import node maps from the NodeGraphType.
    1262     IMPORT_NODE_MAP(NodeGraphType, graph.G, EdgeSet, graph);
    1263    
    1264    
    1265   public:
    1266 
    1267     ///Constructor
    1268    
    1269     ///Construates a new graph based on the nodeset of an existing one.
    1270     ///\param _G the base graph.
    1271     explicit EdgeSet(NodeGraphType &_G)
    1272       : G(_G), nodes(_G), edges(),
    1273         first_free_edge(-1) {}
    1274     ///Copy constructor
    1275 
    1276     ///Makes a copy of an EdgeSet.
    1277     ///It will be based on the same graph.
    1278     explicit EdgeSet(const EdgeSet &_g)
    1279       : G(_g.G), nodes(_g.G), edges(_g.edges),
    1280         first_free_edge(_g.first_free_edge) {}
    1281    
    1282     ///Number of nodes.
    1283     int nodeNum() const { return G.nodeNum(); }
    1284     ///Number of edges.
    1285     int edgeNum() const { return edges.size(); }
    1286 
    1287     /// Maximum node ID.
    1288    
    1289     /// Maximum node ID.
    1290     ///\sa id(Node)
    1291     int maxNodeId() const { return G.maxNodeId(); }
    1292     /// Maximum edge ID.
    1293    
    1294     /// Maximum edge ID.
    1295     ///\sa id(Edge)
    1296     int maxEdgeId() const { return edges.size()-1; }
    1297 
    1298     Node tail(Edge e) const { return edges[e.n].tail; }
    1299     Node head(Edge e) const { return edges[e.n].head; }
    1300 
    1301     NodeIt& first(NodeIt& v) const {
    1302       v=NodeIt(*this); return v; }
    1303     EdgeIt& first(EdgeIt& e) const {
    1304       e=EdgeIt(*this); return e; }
    1305     OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
    1306       e=OutEdgeIt(*this,v); return e; }
    1307     InEdgeIt& first(InEdgeIt& e, const Node v) const {
    1308       e=InEdgeIt(*this,v); return e; }
    1309 
    1310     /// Node ID.
    1311    
    1312     /// The ID of a valid Node is a nonnegative integer not greater than
    1313     /// \ref maxNodeId(). The range of the ID's is not surely continuous
    1314     /// and the greatest node ID can be actually less then \ref maxNodeId().
    1315     ///
    1316     /// The ID of the \ref INVALID node is -1.
    1317     ///\return The ID of the node \c v.
    1318     int id(Node v) { return G.id(v); }
    1319     /// Edge ID.
    1320    
    1321     /// The ID of a valid Edge is a nonnegative integer not greater than
    1322     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
    1323     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
    1324     ///
    1325     /// The ID of the \ref INVALID edge is -1.
    1326     ///\return The ID of the edge \c e.
    1327     static int id(Edge e) { return e.n; }
    1328 
    1329     /// Adds a new node to the graph.
    1330     Node addNode() { return G.addNode(); }
    1331    
    1332     Edge addEdge(Node u, Node v) {
    1333       int n;
    1334      
    1335       if(first_free_edge==-1)
    1336         {
    1337           n = edges.size();
    1338           edges.push_back(EdgeT());
    1339         }
    1340       else {
    1341         n = first_free_edge;
    1342         first_free_edge = edges[n].next_in;
    1343       }
    1344      
    1345       edges[n].tail = u; edges[n].head = v;
    1346 
    1347       edges[n].next_out = nodes[u].first_out;
    1348       if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n;
    1349       edges[n].next_in = nodes[v].first_in;
    1350       if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n;
    1351       edges[n].prev_in = edges[n].prev_out = -1;
    1352        
    1353       nodes[u].first_out = nodes[v].first_in = n;
    1354 
    1355       Edge e; e.n=n;
    1356 
    1357       //Update dynamic maps
    1358       edge_maps.add(e);
    1359 
    1360       return e;
    1361     }
    1362 
    1363     /// Finds an edge between two nodes.
    1364 
    1365     /// Finds an edge from node \c u to node \c v.
    1366     ///
    1367     /// If \c prev is \ref INVALID (this is the default value), then
    1368     /// It finds the first edge from \c u to \c v. Otherwise it looks for
    1369     /// the next edge from \c u to \c v after \c prev.
    1370     /// \return The found edge or INVALID if there is no such an edge.
    1371     Edge findEdge(Node u,Node v, Edge prev = INVALID)
    1372     {
    1373       int e = (prev.n==-1)? nodes[u].first_out : edges[prev.n].next_out;
    1374       while(e!=-1 && edges[e].tail!=v) e = edges[e].next_out;
    1375       prev.n=e;
    1376       return prev;
    1377     }
    1378    
    1379   private:
    1380     void eraseEdge(int n) {
    1381      
    1382       if(edges[n].next_in!=-1)
    1383         edges[edges[n].next_in].prev_in = edges[n].prev_in;
    1384       if(edges[n].prev_in!=-1)
    1385         edges[edges[n].prev_in].next_in = edges[n].next_in;
    1386       else nodes[edges[n].head].first_in = edges[n].next_in;
    1387      
    1388       if(edges[n].next_out!=-1)
    1389         edges[edges[n].next_out].prev_out = edges[n].prev_out;
    1390       if(edges[n].prev_out!=-1)
    1391         edges[edges[n].prev_out].next_out = edges[n].next_out;
    1392       else nodes[edges[n].tail].first_out = edges[n].next_out;
    1393      
    1394       edges[n].next_in = first_free_edge;
    1395       first_free_edge = -1;     
    1396 
    1397       //Update dynamic maps
    1398       Edge e; e.n = n;
    1399       edge_maps.erase(e);
    1400     }
    1401      
    1402   public:
    1403 
    1404     void erase(Edge e) { eraseEdge(e.n); }
    1405 
    1406     ///Clear all edges. (Doesn't clear the nodes!)
    1407     void clear() {
    1408       edge_maps.clear();
    1409       edges.clear();
    1410       first_free_edge=-1;
    1411     }
    1412 
    1413 
    1414     class Edge {
    1415     public:
    1416       friend class EdgeSet;
    1417       template <typename T> friend class EdgeMap;
    1418 
    1419       friend class Node;
    1420       friend class NodeIt;
    1421     protected:
    1422       int n;
    1423       friend int EdgeSet::id(Edge e) const;
    1424 
    1425       Edge(int nn) {n=nn;}
    1426     public:
    1427       Edge() { }
    1428       Edge (Invalid) { n=-1; }
    1429       bool operator==(const Edge i) const {return n==i.n;}
    1430       bool operator!=(const Edge i) const {return n!=i.n;}
    1431       bool operator<(const Edge i) const {return n<i.n;}
    1432     };
    1433    
    1434     class EdgeIt : public Edge {
    1435       friend class EdgeSet;
    1436       template <typename T> friend class EdgeMap;
    1437    
    1438       const EdgeSet *G;
    1439     public:
    1440       EdgeIt(const EdgeSet& _G) : Edge(), G(&_G) {
    1441         NodeIt m;
    1442         for(G->first(m);
    1443             m!=INVALID && G->nodes[m].first_in == -1;  ++m);
    1444         ///\bug AJJAJ! This is a non sense!!!!!!!
    1445         this->n = m!=INVALID?-1:G->nodes[m].first_in;
    1446       }
    1447       EdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
    1448       EdgeIt (Invalid i) : Edge(i) { }
    1449       EdgeIt() : Edge() { }
    1450       ///.
    1451      
    1452       ///\bug UNIMPLEMENTED!!!!!
    1453       //
    1454       EdgeIt &operator++() {
    1455         return *this;
    1456       }
    1457     };
    1458    
    1459     class OutEdgeIt : public Edge {
    1460       const EdgeSet *G;
    1461       friend class EdgeSet;
    1462     public:
    1463       OutEdgeIt() : Edge() { }
    1464       OutEdgeIt (Invalid i) : Edge(i) { }
    1465       OutEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
    1466 
    1467       OutEdgeIt(const EdgeSet& _G,const Node v) :
    1468         Edge(_G.nodes[v].first_out), G(&_G) { }
    1469       OutEdgeIt &operator++() {
    1470         Edge::n = G->edges[Edge::n].next_out;
    1471         return *this;
    1472       }
    1473     };
    1474    
    1475     class InEdgeIt : public Edge {
    1476       const EdgeSet *G;
    1477       friend class EdgeSet;
    1478     public:
    1479       InEdgeIt() : Edge() { }
    1480       InEdgeIt (Invalid i) : Edge(i) { }
    1481       InEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
    1482       InEdgeIt(const EdgeSet& _G,Node v)
    1483         : Edge(_G.nodes[v].first_in), G(&_G) { }
    1484       InEdgeIt &operator++() {
    1485         Edge::n = G->edges[Edge::n].next_in;
    1486         return *this;
    1487       }
    1488     };
    1489    
    1490   };
    1491 
    1492   template<typename GG>
    1493   inline int EdgeSet<GG>::id(Node v) const { return G.id(v); }
    1494 
    1495 /// @} 
    1496 
    1497 } //namespace lemon
    1498 
    1499 #endif //LEMON_LIST_GRAPH_H
     262  typedef AlterableGraphExtender<ListGraphBase> AlterableListGraphBase;
     263  typedef IterableGraphExtender<AlterableListGraphBase> IterableListGraphBase;
     264  typedef IdMappableGraphExtender<IterableListGraphBase> IdMappableListGraphBase;
     265  typedef DefaultMappableGraphExtender<IdMappableListGraphBase> MappableListGraphBase;
     266  typedef ExtendableGraphExtender<MappableListGraphBase> ExtendableListGraphBase;
     267  typedef ClearableGraphExtender<ExtendableListGraphBase> ClearableListGraphBase;
     268  typedef ErasableGraphExtender<ClearableListGraphBase> ErasableListGraphBase;
     269
     270  typedef ErasableListGraphBase ListGraph;
     271
     272}
     273
     274
     275 
     276
     277#endif
Note: See TracChangeset for help on using the changeset viewer.