COIN-OR::LEMON - Graph Library

Changeset 946:c94ef40a22ce in lemon-0.x for src/lemon/smart_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/smart_graph.h

    r937 r946  
    2323
    2424#include <vector>
    25 #include <climits>
    2625
    2726#include <lemon/invalid.h>
    2827
    29 
    30 #include <lemon/array_map.h>
    31 
    32 #include <lemon/map_registry.h>
    33 
    34 #include <lemon/map_defines.h>
     28#include <lemon/erasable_graph_extender.h>
     29#include <lemon/clearable_graph_extender.h>
     30#include <lemon/extendable_graph_extender.h>
     31
     32#include <lemon/idmappable_graph_extender.h>
     33
     34#include <lemon/iterable_graph_extender.h>
     35
     36#include <lemon/alteration_observer_registry.h>
     37#include <lemon/default_map.h>
     38
     39
     40#include <lemon/graph_utils.h>
     41
    3542
    3643namespace lemon {
    3744
    38 /// \addtogroup graphs
    39 /// @{
    40 //  class SymSmartGraph;
     45  /// \addtogroup graphs
     46  /// @{
    4147
    4248  ///A smart graph class.
     
    5763  ///
    5864  ///\author Alpar Juttner
    59   class SmartGraph {
     65  class SmartGraphBase {
    6066
    6167    struct NodeT
     
    7884  public:
    7985
    80     typedef SmartGraph Graph;
     86    typedef SmartGraphBase Graph;
    8187
    8288    class Node;
    8389    class Edge;
    8490
    85     class NodeIt;
    86     class EdgeIt;
    87     class OutEdgeIt;
    88     class InEdgeIt;
    89    
    90     // Create map registries.
    91     CREATE_MAP_REGISTRIES;
    92     // Create node and edge maps.
    93     CREATE_MAPS(ArrayMap);
    9491   
    9592  public:
    9693
    97     SmartGraph() : nodes(), edges() { }
    98     SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
     94    SmartGraphBase() : nodes(), edges() { }
     95    SmartGraphBase(const SmartGraphBase &_g) : nodes(_g.nodes), edges(_g.edges) { }
    9996   
    10097    ///Number of nodes.
     
    116113    Node tail(Edge e) const { return edges[e.n].tail; }
    117114    Node head(Edge e) const { return edges[e.n].head; }
    118 
    119     NodeIt& first(NodeIt& v) const {
    120       v=NodeIt(*this); return v; }
    121     EdgeIt& first(EdgeIt& e) const {
    122       e=EdgeIt(*this); return e; }
    123     OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
    124       e=OutEdgeIt(*this,v); return e; }
    125     InEdgeIt& first(InEdgeIt& e, const Node v) const {
    126       e=InEdgeIt(*this,v); return e; }
    127115
    128116    /// Node ID.
     
    148136      Node n; n.n=nodes.size();
    149137      nodes.push_back(NodeT()); //FIXME: Hmmm...
    150 
    151      
    152       node_maps.add(n);
    153138      return n;
    154139    }
     
    160145      edges[e.n].next_in=nodes[v.n].first_in;
    161146      nodes[u.n].first_out=nodes[v.n].first_in=e.n;
    162 
    163       edge_maps.add(e);
    164147
    165148      return e;
     
    183166   
    184167    void clear() {
    185       edge_maps.clear();
    186168      edges.clear();
    187       node_maps.clear();
    188169      nodes.clear();
    189170    }
    190171
     172
    191173    class Node {
    192       friend class SmartGraph;
    193       template <typename T> friend class NodeMap;
    194      
    195       friend class Edge;
    196       friend class OutEdgeIt;
    197       friend class InEdgeIt;
    198       friend class SymEdge;
     174      friend class SmartGraphBase;
    199175
    200176    protected:
    201177      int n;
    202       friend int SmartGraph::id(Node v);
    203178      Node(int nn) {n=nn;}
    204179    public:
     
    208183      bool operator!=(const Node i) const {return n!=i.n;}
    209184      bool operator<(const Node i) const {return n<i.n;}
    210       //      ///Validity check
    211       //      operator bool() { return n!=-1; }
    212     };
    213    
    214     class NodeIt : public Node {
    215       const SmartGraph *G;
    216       friend class SmartGraph;
    217     public:
    218       NodeIt() : Node() { }
    219       NodeIt(const SmartGraph& _G,Node n) : Node(n), G(&_G) { }
    220       NodeIt(Invalid i) : Node(i) { }
    221       NodeIt(const SmartGraph& _G) : Node(_G.nodes.size()?0:-1), G(&_G) { }
    222       NodeIt &operator++() {
    223         n=(n+2)%(G->nodes.size()+1)-1;
    224         return *this;
    225       }
    226 //       ///Validity check
    227 //       operator bool() { return Node::operator bool(); }     
    228     };
     185    };
     186   
    229187
    230188    class Edge {
    231       friend class SmartGraph;
    232       template <typename T> friend class EdgeMap;
    233 
    234       friend class SymSmartGraph;
    235      
    236       friend class Node;
    237       friend class NodeIt;
     189      friend class SmartGraphBase;
     190
    238191    protected:
    239192      int n;
    240       friend int SmartGraph::id(Edge e);
    241193      Edge(int nn) {n=nn;}
    242194    public:
    243       /// An Edge with id \c n.
    244 
    245195      Edge() { }
    246196      Edge (Invalid) { n=-1; }
     
    248198      bool operator!=(const Edge i) const {return n!=i.n;}
    249199      bool operator<(const Edge i) const {return n<i.n;}
    250 //       ///Validity check
    251 //       operator bool() { return n!=-1; }
    252 
    253       ///Set the edge to that have ID \c ID.
    254       void setToId(int id) { n=id; }
    255    };
    256    
    257     class EdgeIt : public Edge {
    258       const SmartGraph *G;
    259       friend class SmartGraph;
    260     public:
    261       EdgeIt(const SmartGraph& _G) : Edge(_G.edges.size()-1), G(&_G) { }
    262       EdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
    263       EdgeIt (Invalid i) : Edge(i) { }
    264       EdgeIt() : Edge() { }
    265       EdgeIt &operator++() { --n; return *this; }
    266 //       ///Validity check
    267 //       operator bool() { return Edge::operator bool(); }     
    268     };
    269    
    270     class OutEdgeIt : public Edge {
    271       const SmartGraph *G;
    272       friend class SmartGraph;
    273     public:
    274       OutEdgeIt() : Edge() { }
    275       OutEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
    276       OutEdgeIt (Invalid i) : Edge(i) { }
    277 
    278       OutEdgeIt(const SmartGraph& _G,const Node v)
    279         : Edge(_G.nodes[v.n].first_out), G(&_G) {}
    280       OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
    281 //       ///Validity check
    282 //       operator bool() { return Edge::operator bool(); }     
    283     };
    284    
    285     class InEdgeIt : public Edge {
    286       const SmartGraph *G;
    287       friend class SmartGraph;
    288     public:
    289       InEdgeIt() : Edge() { }
    290       InEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
    291       InEdgeIt (Invalid i) : Edge(i) { }
    292       InEdgeIt(const SmartGraph& _G,Node v)
    293         : Edge(_G.nodes[v.n].first_in), G(&_G) { }
    294       InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
    295 //       ///Validity check
    296 //       operator bool() { return Edge::operator bool(); }     
    297     };
     200    };
     201
     202    void first(Node& node) const {
     203      node.n = nodes.size() - 1;
     204    }
     205
     206    static void next(Node& node) {
     207      --node.n;
     208    }
     209
     210    void first(Edge& edge) const {
     211      edge.n = edges.size() - 1;
     212    }
     213
     214    static void next(Edge& edge) {
     215      --edge.n;
     216    }
     217
     218    void firstOut(Edge& edge, const Node& node) const {
     219      edge.n = nodes[node.n].first_out;
     220    }
     221
     222    void nextOut(Edge& edge) const {
     223      edge.n = edges[edge.n].next_out;
     224    }
     225
     226    void firstIn(Edge& edge, const Node& node) const {
     227      edge.n = nodes[node.n].first_in;
     228    }
     229   
     230    void nextIn(Edge& edge) const {
     231      edge.n = edges[edge.n].next_in;
     232    }
    298233
    299234  };
    300235
    301 
    302 
    303   class SymSmartGraph : public SmartGraph {
    304     typedef SmartGraph Parent;
    305   public:
    306 
    307     typedef SymSmartGraph Graph;
    308 
    309     typedef SmartGraph::Node Node;
    310     typedef SmartGraph::NodeIt NodeIt;
    311 
    312     class SymEdge;
    313     class SymEdgeIt;
    314 
    315     class Edge;
    316     class EdgeIt;
    317     class OutEdgeIt;
    318     class InEdgeIt;
    319 
    320     template <typename Value>
    321     class NodeMap : public Parent::NodeMap<Value> {     
    322     public:
    323       NodeMap(const SymSmartGraph& g)
    324         : SymSmartGraph::Parent::NodeMap<Value>(g) {}
    325       NodeMap(const SymSmartGraph& g, Value v)
    326         : SymSmartGraph::Parent::NodeMap<Value>(g, v) {}
    327       template<typename TT>
    328       NodeMap(const NodeMap<TT>& copy)
    329         : SymSmartGraph::Parent::NodeMap<Value>(copy) { }           
    330     };
    331 
    332     template <typename Value>
    333     class SymEdgeMap : public Parent::EdgeMap<Value> {
    334     public:
    335       typedef SymEdge KeyType;
    336 
    337       SymEdgeMap(const SymSmartGraph& g)
    338         : SymSmartGraph::Parent::EdgeMap<Value>(g) {}
    339       SymEdgeMap(const SymSmartGraph& g, Value v)
    340         : SymSmartGraph::Parent::EdgeMap<Value>(g, v) {}
    341       template<typename TT>
    342       SymEdgeMap(const SymEdgeMap<TT>& copy)
    343         : SymSmartGraph::Parent::EdgeMap<Value>(copy) { }
    344      
    345     };
    346 
    347     // Create edge map registry.
    348     CREATE_EDGE_MAP_REGISTRY;
    349     // Create edge maps.
    350     CREATE_EDGE_MAP(ArrayMap);
    351 
    352     class Edge {
    353       friend class SymSmartGraph;
    354       friend class SymSmartGraph::EdgeIt;
    355       friend class SymSmartGraph::OutEdgeIt;
    356       friend class SymSmartGraph::InEdgeIt;
    357      
    358     protected:
    359       int id;
    360 
    361       Edge(int pid) { id = pid; }
    362 
    363     public:
    364       /// An Edge with id \c n.
    365 
    366       Edge() { }
    367       Edge (Invalid) { id = -1; }
    368 
    369       operator SymEdge(){ return SymEdge(id >> 1);}
    370      
    371       bool operator==(const Edge i) const {return id == i.id;}
    372       bool operator!=(const Edge i) const {return id != i.id;}
    373       bool operator<(const Edge i) const {return id < i.id;}
    374       //      ///Validity check
    375       //      operator bool() { return n!=-1; }
    376     };
    377 
    378     class SymEdge : public SmartGraph::Edge {
    379       friend class SymSmartGraph;
    380       friend class SymSmartGraph::Edge;
    381       typedef SmartGraph::Edge Parent;
    382 
    383     protected:     
    384       SymEdge(int pid) : Parent(pid) {}
    385     public:
    386 
    387       SymEdge() { }
    388       SymEdge(const SmartGraph::Edge& i) : Parent(i) {}
    389       SymEdge (Invalid) : Parent(INVALID) {}
    390 
    391     };
    392 
    393     class OutEdgeIt {
    394       Parent::OutEdgeIt out;
    395       Parent::InEdgeIt in;     
    396     public:
    397       OutEdgeIt() {}
    398       OutEdgeIt(const SymSmartGraph& g, Edge e) {
    399         if ((e.id & 1) == 0) { 
    400           out = Parent::OutEdgeIt(g, SymEdge(e));
    401           in = Parent::InEdgeIt(g, g.tail(e));
    402         } else {
    403           out = Parent::OutEdgeIt(INVALID);
    404           in = Parent::InEdgeIt(g, SymEdge(e));
    405         }
    406       }
    407       OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
    408 
    409       OutEdgeIt(const SymSmartGraph& g, const Node v)
    410         : out(g, v), in(g, v) {}
    411       OutEdgeIt &operator++() {
    412         if (out != INVALID) {
    413           ++out;
    414         } else {
    415           ++in;
    416         }
    417         return *this;
    418       }
    419 
    420       operator Edge() const {
    421         if (out == INVALID && in == INVALID) return INVALID;
    422         return out != INVALID ? forward(out) : backward(in);
    423       }
    424 
    425       bool operator==(const Edge i) const {return Edge(*this) == i;}
    426       bool operator!=(const Edge i) const {return Edge(*this) != i;}
    427       bool operator<(const Edge i) const {return Edge(*this) < i;}
    428     };
    429 
    430     class InEdgeIt {
    431       Parent::OutEdgeIt out;
    432       Parent::InEdgeIt in;     
    433     public:
    434       InEdgeIt() {}
    435       InEdgeIt(const SymSmartGraph& g, Edge e) {
    436         if ((e.id & 1) == 0) { 
    437           out = Parent::OutEdgeIt(g, SymEdge(e));
    438           in = Parent::InEdgeIt(g, g.tail(e));
    439         } else {
    440           out = Parent::OutEdgeIt(INVALID);
    441           in = Parent::InEdgeIt(g, SymEdge(e));
    442         }
    443       }
    444       InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
    445 
    446       InEdgeIt(const SymSmartGraph& g, const Node v)
    447         : out(g, v), in(g, v) {}
    448 
    449       InEdgeIt &operator++() {
    450         if (out != INVALID) {
    451           ++out;
    452         } else {
    453           ++in;
    454         }
    455         return *this;
    456       }
    457 
    458       operator Edge() const {
    459         if (out == INVALID && in == INVALID) return INVALID;
    460         return out != INVALID ? backward(out) : forward(in);
    461       }
    462 
    463       bool operator==(const Edge i) const {return Edge(*this) == i;}
    464       bool operator!=(const Edge i) const {return Edge(*this) != i;}
    465       bool operator<(const Edge i) const {return Edge(*this) < i;}
    466     };
    467 
    468     class SymEdgeIt : public Parent::EdgeIt {
    469 
    470     public:
    471       SymEdgeIt() {}
    472 
    473       SymEdgeIt(const SymSmartGraph& g)
    474         : SymSmartGraph::Parent::EdgeIt(g) {}
    475 
    476       SymEdgeIt(const SymSmartGraph& g, SymEdge e)
    477         : SymSmartGraph::Parent::EdgeIt(g, e) {}
    478 
    479       SymEdgeIt(Invalid i)
    480         : SymSmartGraph::Parent::EdgeIt(INVALID) {}
    481 
    482       SymEdgeIt& operator++() {
    483         SymSmartGraph::Parent::EdgeIt::operator++();
    484         return *this;
    485       }
    486 
    487       operator SymEdge() const {
    488         return SymEdge
    489           (static_cast<const SymSmartGraph::Parent::EdgeIt&>(*this));
    490       }
    491       bool operator==(const SymEdge i) const {return SymEdge(*this) == i;}
    492       bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;}
    493       bool operator<(const SymEdge i) const {return SymEdge(*this) < i;}
    494     };
    495 
    496     class EdgeIt {
    497       SymEdgeIt it;
    498       bool fw;
    499     public:
    500       EdgeIt(const SymSmartGraph& g) : it(g), fw(true) {}
    501       EdgeIt (Invalid i) : it(i) { }
    502       EdgeIt(const SymSmartGraph& g, Edge e)
    503         : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { }
    504       EdgeIt() { }
    505       EdgeIt& operator++() {
    506         fw = !fw;
    507         if (fw) ++it;
    508         return *this;
    509       }
    510       operator Edge() const {
    511         if (it == INVALID) return INVALID;
    512         return fw ? forward(it) : backward(it);
    513       }
    514       bool operator==(const Edge i) const {return Edge(*this) == i;}
    515       bool operator!=(const Edge i) const {return Edge(*this) != i;}
    516       bool operator<(const Edge i) const {return Edge(*this) < i;}
    517 
    518     };
    519 
    520     ///Number of nodes.
    521     int nodeNum() const { return Parent::nodeNum(); }
    522     ///Number of edges.
    523     int edgeNum() const { return 2*Parent::edgeNum(); }
    524     ///Number of symmetric edges.
    525     int symEdgeNum() const { return Parent::edgeNum(); }
    526 
    527     /// Maximum node ID.
    528    
    529     /// Maximum node ID.
    530     ///\sa id(Node)
    531     int maxNodeId() const { return Parent::maxNodeId(); }
    532     /// Maximum edge ID.
    533    
    534     /// Maximum edge ID.
    535     ///\sa id(Edge)
    536     int maxEdgeId() const { return 2*Parent::maxEdgeId(); }
    537     /// Maximum symmetric edge ID.
    538    
    539     /// Maximum symmetric edge ID.
    540     ///\sa id(SymEdge)
    541     int maxSymEdgeId() const { return Parent::maxEdgeId(); }
    542 
    543 
    544     Node tail(Edge e) const {
    545       return (e.id & 1) == 0 ?
    546         Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e));
    547     }
    548 
    549     Node head(Edge e) const {
    550       return (e.id & 1) == 0 ?
    551         Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e));
    552     }
    553 
    554     Node tail(SymEdge e) const {
    555       return Parent::tail(e);
    556     }
    557 
    558     Node head(SymEdge e) const {
    559       return Parent::head(e);
    560     }
    561 
    562     NodeIt& first(NodeIt& v) const {
    563       v=NodeIt(*this); return v; }
    564     EdgeIt& first(EdgeIt& e) const {
    565       e=EdgeIt(*this); return e; }
    566     SymEdgeIt& first(SymEdgeIt& e) const {
    567       e=SymEdgeIt(*this); return e; }
    568     OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
    569       e=OutEdgeIt(*this,v); return e; }
    570     InEdgeIt& first(InEdgeIt& e, const Node v) const {
    571       e=InEdgeIt(*this,v); return e; }
    572 
    573     /// Node ID.
    574    
    575     /// The ID of a valid Node is a nonnegative integer not greater than
    576     /// \ref maxNodeId(). The range of the ID's is not surely continuous
    577     /// and the greatest node ID can be actually less then \ref maxNodeId().
    578     ///
    579     /// The ID of the \ref INVALID node is -1.
    580     ///\return The ID of the node \c v.
    581     static int id(Node v) { return Parent::id(v); }
    582     /// Edge ID.
    583    
    584     /// The ID of a valid Edge is a nonnegative integer not greater than
    585     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
    586     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
    587     ///
    588     /// The ID of the \ref INVALID edge is -1.
    589     ///\return The ID of the edge \c e.
    590     static int id(Edge e) { return e.id; }
    591 
    592     /// The ID of a valid SymEdge is a nonnegative integer not greater than
    593     /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous
    594     /// and the greatest edge ID can be actually less then \ref maxSymEdgeId().
    595     ///
    596     /// The ID of the \ref INVALID symmetric edge is -1.
    597     ///\return The ID of the edge \c e.
    598     static int id(SymEdge e) { return Parent::id(e); }
    599 
    600     /// Adds a new node to the graph.
    601 
    602     /// \warning It adds the new node to the front of the list.
    603     /// (i.e. the lastly added node becomes the first.)
    604     Node addNode() {
    605       return Parent::addNode();
    606     }
    607    
    608     SymEdge addEdge(Node u, Node v) {
    609       SymEdge se = Parent::addEdge(u, v);
    610       edge_maps.add(forward(se));
    611       edge_maps.add(backward(se));
    612       return se;
    613     }
    614    
    615     /// Finds an edge between two nodes.
    616 
    617     /// Finds an edge from node \c u to node \c v.
    618     ///
    619     /// If \c prev is \ref INVALID (this is the default value), then
    620     /// It finds the first edge from \c u to \c v. Otherwise it looks for
    621     /// the next edge from \c u to \c v after \c prev.
    622     /// \return The found edge or INVALID if there is no such an edge.
    623     Edge findEdge(Node u, Node v, Edge prev = INVALID)
    624     {     
    625       if (prev == INVALID || id(prev) & 1 == 0) {
    626         SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
    627         if (se != INVALID) return forward(se);
    628       } else {
    629         SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
    630         if (se != INVALID) return backward(se);
    631       }
    632       return INVALID;
    633     }
    634 
    635 //     /// Finds an symmetric edge between two nodes.
    636 
    637 //     /// Finds an symmetric edge from node \c u to node \c v.
    638 //     ///
    639 //     /// If \c prev is \ref INVALID (this is the default value), then
    640 //     /// It finds the first edge from \c u to \c v. Otherwise it looks for
    641 //     /// the next edge from \c u to \c v after \c prev.
    642 //     /// \return The found edge or INVALID if there is no such an edge.
    643 
    644 //     SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID)
    645 //     {     
    646 //       if (prev == INVALID || id(prev) & 1 == 0) {
    647 //      SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
    648 //      if (se != INVALID) return se;
    649 //       } else {
    650 //      SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
    651 //      if (se != INVALID) return se;   
    652 //       }
    653 //       return INVALID;
    654 //     }
    655    
    656   public:
    657 
    658     void clear() {
    659       edge_maps.clear();
    660       Parent::clear();
    661     }
    662 
    663     static Edge opposite(Edge e) {
    664       return Edge(id(e) ^ 1);
    665     }
    666 
    667     static Edge forward(SymEdge e) {
    668       return Edge(id(e) << 1);
    669     }
    670 
    671     static Edge backward(SymEdge e) {
    672       return Edge((id(e) << 1) | 1);
    673     }
    674 
    675   };
    676   ///Graph for bidirectional edges.
    677 
    678   ///The purpose of this graph structure is to handle graphs
    679   ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
    680   ///of oppositely directed edges.
    681   ///There is a new edge map type called
    682   ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
    683   ///that complements this
    684   ///feature by
    685   ///storing shared values for the edge pairs. The usual
    686   ///\ref Graph::EdgeMap "EdgeMap"
    687   ///can be used
    688   ///as well.
    689   ///
    690   ///The oppositely directed edge can also be obtained easily
    691   ///using \ref opposite.
    692   ///\warning It shares the similarity with \ref SmartGraph that
    693   ///it is not possible to delete edges or nodes from the graph.
    694   //\sa SmartGraph.
    695 
    696   /*  class SymSmartGraph : public SmartGraph
    697   {
    698   public:
    699     typedef SymSmartGraph Graph;
    700 
    701     // Create symmetric map registry.
    702     CREATE_SYM_EDGE_MAP_REGISTRY;
    703     // Create symmetric edge map.
    704     CREATE_SYM_EDGE_MAP(ArrayMap);
    705 
    706 
    707     SymSmartGraph() : SmartGraph() { }
    708     SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
    709     ///Adds a pair of oppositely directed edges to the graph.
    710     Edge addEdge(Node u, Node v)
    711     {
    712       Edge e = SmartGraph::addEdge(u,v);
    713       Edge f = SmartGraph::addEdge(v,u);
    714       sym_edge_maps.add(e);
    715       sym_edge_maps.add(f);
    716       return e;
    717     }
    718 
    719     ///The oppositely directed edge.
    720 
    721     ///Returns the oppositely directed
    722     ///pair of the edge \c e.
    723     static Edge opposite(Edge e)
    724     {
    725       Edge f;
    726       f.n = e.n - 2*(e.n%2) + 1;
    727       return f;
    728     }
    729    
    730 
    731     };*/
    732  
     236  typedef AlterableGraphExtender<SmartGraphBase> AlterableSmartGraphBase;
     237  typedef IterableGraphExtender<AlterableSmartGraphBase> IterableSmartGraphBase;
     238  typedef IdMappableGraphExtender<IterableSmartGraphBase> IdMappableSmartGraphBase;
     239  typedef DefaultMappableGraphExtender<IdMappableSmartGraphBase> MappableSmartGraphBase;
     240  typedef ExtendableGraphExtender<MappableSmartGraphBase> ExtendableSmartGraphBase;
     241  typedef ClearableGraphExtender<ExtendableSmartGraphBase> ClearableSmartGraphBase;
     242
     243  typedef ClearableSmartGraphBase SmartGraph;
     244
     245
     246  template <>
     247  int countNodes<SmartGraph>(const SmartGraph& graph) {
     248    return graph.nodeNum();
     249  }
     250
     251  template <>
     252  int countEdges<SmartGraph>(const SmartGraph& graph) {
     253    return graph.edgeNum();
     254  }
     255
    733256  /// @} 
    734257} //namespace lemon
Note: See TracChangeset for help on using the changeset viewer.