COIN-OR::LEMON - Graph Library

Changeset 1979:c2992fd74dad in lemon-0.x


Ignore:
Timestamp:
02/22/06 19:26:56 (18 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2569
Message:

Mergeing extendermerge branch
Changes:

the extender system
resize for static size graph
UGraphExtender => UndirectGraphExtender?

UGraphExtenders with changed meaning

Some UGraphExtender /SubUGraphExtenders, DirectUGraphExtender/
GridGraph? => GridUGraph
radix sort to ansi compatible

Files:
6 added
7 deleted
25 edited

Legend:

Unmodified
Added
Removed
  • demo/Makefile.am

    r1971 r1979  
    1717        descriptor_map_demo \
    1818        coloring \
    19         grid_graph_demo \
     19        grid_ugraph_demo \
    2020        topology_demo \
    2121        simann_maxcut_demo
     
    4444graph_to_eps_demo_SOURCES = graph_to_eps_demo.cc
    4545
    46 grid_graph_demo_SOURCES = grid_graph_demo.cc
     46grid_ugraph_demo_SOURCES = grid_ugraph_demo.cc
    4747
    4848graph_orientation_SOURCES = graph_orientation.cc
  • lemon/Makefile.am

    r1977 r1979  
    4141        fredman_tarjan.h \
    4242        full_graph.h \
    43         grid_graph.h \
     43        grid_ugraph.h \
    4444        graph_adaptor.h \
    4545        graph_utils.h \
     
    7676        topology.h \
    7777        traits.h \
     78        ugraph_adaptor.h \
    7879        unionfind.h \
    7980        xy.h \
     
    8889        bits/array_map.h \
    8990        bits/default_map.h \
     91        bits/static_map.h \
    9092        bits/vector_map.h \
    91         bits/iterable_graph_extender.h \
    92         bits/extendable_graph_extender.h \
    93         bits/clearable_graph_extender.h \
    94         bits/erasable_graph_extender.h \
     93        bits/map_extender.h \
    9594        bits/graph_extender.h \
    96         bits/map_extender.h \
    97         bits/static_map.h \
     95        bits/graph_adaptor_extender.h \
     96        bits/edge_set_extender.h \
    9897        bits/item_reader.h \
    9998        bits/item_writer.h \
  • lemon/bits/alteration_notifier.h

    r1956 r1979  
    266266    void add(const Item& item) {
    267267      typename Container::iterator it;
    268       for (it = container.begin(); it != container.end(); ++it) {
    269         (*it)->add(item);
     268      try {
     269        for (it = container.begin(); it != container.end(); ++it) {
     270          (*it)->add(item);
     271        }
     272      } catch (...) {
     273        typename Container::iterator jt;
     274        for (jt = container.begin(); jt != it; ++it) {
     275          (*it)->erase(item);
     276        }
     277        throw;
    270278      }
    271279    }   
     
    279287    void add(const std::vector<Item>& items) {
    280288      typename Container::iterator it;
    281       for (it = container.begin(); it != container.end(); ++it) {
    282         (*it)->add(items);
     289      try {
     290        for (it = container.begin(); it != container.end(); ++it) {
     291          (*it)->add(items);
     292        }
     293      } catch (...) {
     294        typename Container::iterator jt;
     295        for (jt = container.begin(); jt != it; ++it) {
     296          (*it)->erase(items);
     297        }
     298        throw;
    283299      }
    284300    }   
     
    317333    void build() {
    318334      typename Container::iterator it;
    319       for (it = container.begin(); it != container.end(); ++it) {
    320         (*it)->build();
     335      try {
     336        for (it = container.begin(); it != container.end(); ++it) {
     337          (*it)->build();
     338        }
     339      } catch (...) {
     340        typename Container::iterator jt;
     341        for (jt = container.begin(); jt != it; ++it) {
     342          (*it)->clear();
     343        }
     344        throw;
    321345      }
    322346    }
     
    336360  };
    337361
    338 
    339   /// \brief Class to extend a graph with the functionality of alteration
    340   /// observing.
    341   ///
    342   /// AlterableGraphExtender extends the _Base graphs functionality with
    343   /// the possibility of alteration observing. It defines two observer
    344   /// registrys for the nodes and mapes.
    345   ///
    346   /// \todo Document what "alteration observing" is. And probably find a
    347   /// better (shorter) name.
    348   ///
    349   /// \param _Base is the base class to extend.
    350   ///
    351   /// \pre _Base is conform to the BaseGraphComponent concept.
    352   ///
    353   /// \post AlterableGraphExtender<_Base> is conform to the
    354   /// AlterableGraphComponent concept.
    355   ///
    356   /// \author Balazs Dezso
    357 
    358   template <typename _Base>
    359   class AlterableGraphExtender : public _Base {
    360   public:
    361 
    362     typedef AlterableGraphExtender Graph;
    363     typedef _Base Parent;
    364 
    365     typedef typename Parent::Node Node;
    366     typedef typename Parent::Edge Edge;
    367 
    368     /// The edge observer registry.
    369     typedef AlterationNotifier<Edge> EdgeNotifier;
    370     /// The node observer registry.
    371     typedef AlterationNotifier<Node> NodeNotifier;
    372 
    373 
    374   protected:
    375 
    376     mutable EdgeNotifier edge_notifier;
    377 
    378     mutable NodeNotifier node_notifier;
    379 
    380   public:
    381 
    382     /// \brief Gives back the edge alteration notifier.
    383     ///
    384     /// Gives back the edge alteration notifier.
    385     EdgeNotifier& getNotifier(Edge) const {
    386       return edge_notifier;
    387     }
    388 
    389     /// \brief Gives back the node alteration notifier.
    390     ///
    391     /// Gives back the node alteration notifier.
    392     NodeNotifier& getNotifier(Node) const {
    393       return node_notifier;
    394     }
    395 
    396     ~AlterableGraphExtender() {
    397       node_notifier.clear();
    398       edge_notifier.clear();
    399     }
    400    
    401   };
    402 
    403 
    404   template <typename _Base>
    405   class AlterableEdgeSetExtender : public _Base {
    406   public:
    407 
    408     typedef AlterableEdgeSetExtender Graph;
    409     typedef _Base Parent;
    410 
    411     typedef typename Parent::Edge Edge;
    412 
    413     /// The edge observer registry.
    414     typedef AlterationNotifier<Edge> EdgeNotifier;
    415 
    416   protected:
    417 
    418     mutable EdgeNotifier edge_notifier;
    419 
    420   public:
    421 
    422     /// \brief Gives back the edge alteration notifier.
    423     ///
    424     /// Gives back the edge alteration notifier.
    425     EdgeNotifier& getNotifier(Edge) const {
    426       return edge_notifier;
    427     }
    428 
    429     ~AlterableEdgeSetExtender() {
    430       edge_notifier.clear();
    431     }
    432    
    433   };
    434 
    435   /// \brief Class to extend an undirected graph with the functionality of
    436   /// alteration observing.
    437   ///
    438   /// \todo Document.
    439   ///
    440   /// \sa AlterableGraphExtender
    441   ///
    442   /// \bug This should be done some other way. Possibilities: template
    443   /// specialization (not very easy, if at all possible); some kind of
    444   /// enable_if boost technique?
    445 
    446   template <typename _Base>
    447   class AlterableUGraphExtender
    448     : public AlterableGraphExtender<_Base> {
    449   public:
    450 
    451     typedef AlterableUGraphExtender Graph;
    452     typedef AlterableGraphExtender<_Base> Parent;
    453 
    454     typedef typename Parent::UEdge UEdge;
    455 
    456     /// The edge observer registry.
    457     typedef AlterationNotifier<UEdge> UEdgeNotifier;
    458 
    459   protected:
    460 
    461     mutable UEdgeNotifier u_edge_notifier;
    462 
    463   public:
    464 
    465     using Parent::getNotifier;
    466     UEdgeNotifier& getNotifier(UEdge) const {
    467       return u_edge_notifier;
    468     }
    469 
    470     ~AlterableUGraphExtender() {
    471       u_edge_notifier.clear();
    472     }
    473   };
    474 
    475   template <typename _Base>
    476   class AlterableUEdgeSetExtender
    477     : public AlterableEdgeSetExtender<_Base> {
    478   public:
    479 
    480     typedef AlterableUEdgeSetExtender Graph;
    481     typedef AlterableEdgeSetExtender<_Base> Parent;
    482 
    483     typedef typename Parent::UEdge UEdge;
    484 
    485     typedef AlterationNotifier<UEdge> UEdgeNotifier;
    486 
    487   protected:
    488 
    489     mutable UEdgeNotifier u_edge_notifier;
    490 
    491   public:
    492 
    493     using Parent::getNotifier;
    494     UEdgeNotifier& getNotifier(UEdge) const {
    495       return u_edge_notifier;
    496     }
    497 
    498     ~AlterableUEdgeSetExtender() {
    499       u_edge_notifier.clear();
    500     }
    501   };
    502 
    503 
    504 
    505   template <typename _Base>
    506   class AlterableBpUGraphExtender : public _Base {
    507   public:
    508 
    509     typedef _Base Parent;
    510     typedef AlterableBpUGraphExtender Graph;
    511  
    512     typedef typename Parent::Node Node;
    513     typedef typename Parent::BNode BNode;
    514     typedef typename Parent::ANode ANode;
    515     typedef typename Parent::Edge Edge;
    516     typedef typename Parent::UEdge UEdge;
    517  
    518  
    519     typedef AlterationNotifier<Node> NodeNotifier;
    520     typedef AlterationNotifier<BNode> BNodeNotifier;
    521     typedef AlterationNotifier<ANode> ANodeNotifier;
    522     typedef AlterationNotifier<Edge> EdgeNotifier;
    523     typedef AlterationNotifier<UEdge> UEdgeNotifier;
    524 
    525   protected:
    526 
    527     mutable NodeNotifier nodeNotifier;
    528     mutable BNodeNotifier bNodeNotifier;
    529     mutable ANodeNotifier aNodeNotifier;
    530     mutable EdgeNotifier edgeNotifier;
    531     mutable UEdgeNotifier uEdgeNotifier;
    532 
    533   public:
    534 
    535     NodeNotifier& getNotifier(Node) const {
    536       return nodeNotifier;
    537     }
    538 
    539     BNodeNotifier& getNotifier(BNode) const {
    540       return bNodeNotifier;
    541     }
    542 
    543     ANodeNotifier& getNotifier(ANode) const {
    544       return aNodeNotifier;
    545     }
    546 
    547     EdgeNotifier& getNotifier(Edge) const {
    548       return edgeNotifier;
    549     }
    550 
    551     UEdgeNotifier& getNotifier(UEdge) const {
    552       return uEdgeNotifier;
    553     }
    554 
    555     ~AlterableBpUGraphExtender() {
    556       nodeNotifier.clear();
    557       bNodeNotifier.clear();
    558       aNodeNotifier.clear();
    559       edgeNotifier.clear();
    560       uEdgeNotifier.clear();
    561     }
    562 
    563   };
    564362 
    565363/// @}
  • lemon/bits/default_map.h

    r1966 r1979  
    2323#include <lemon/bits/array_map.h>
    2424#include <lemon/bits/vector_map.h>
     25#include <lemon/bits/static_map.h>
    2526
    2627///\ingroup graphmapfactory
     
    3132namespace lemon {
    3233 
    33 #ifndef GLIBCXX_DEBUG
     34 
     35#ifndef _GLIBCXX_DEBUG
    3436
    3537  template <typename _Graph, typename _Item, typename _Value>
     
    168170  };
    169171
    170 
    171   /// \e
    172   template <typename _Base>
    173   class MappableGraphExtender : public _Base {
    174   public:
    175 
    176     typedef MappableGraphExtender<_Base> Graph;
    177     typedef _Base Parent;
    178 
    179     typedef typename Parent::Node Node;
    180     typedef typename Parent::NodeIt NodeIt;
    181 
    182     typedef typename Parent::Edge Edge;
    183     typedef typename Parent::EdgeIt EdgeIt;
    184 
    185    
    186     template <typename _Value>
    187     class NodeMap
    188       : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > {
    189     public:
    190       typedef MappableGraphExtender Graph;
    191       typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent;
    192 
    193       NodeMap(const Graph& _g)
    194         : Parent(_g) {}
    195       NodeMap(const Graph& _g, const _Value& _v)
    196         : Parent(_g, _v) {}
    197 
    198       NodeMap& operator=(const NodeMap& cmap) {
    199         return operator=<NodeMap>(cmap);
    200       }
    201 
    202 
    203       /// \brief Template assign operator.
    204       ///
    205       /// The given parameter should be conform to the ReadMap
    206       /// concecpt and could be indiced by the current item set of
    207       /// the NodeMap. In this case the value for each item
    208       /// is assigned by the value of the given ReadMap.
    209       template <typename CMap>
    210       NodeMap& operator=(const CMap& cmap) {
    211         checkConcept<concept::ReadMap<Node, _Value>, CMap>();
    212         const typename Parent::Graph* graph = Parent::getGraph();
    213         Node it;
    214         for (graph->first(it); it != INVALID; graph->next(it)) {
    215           Parent::set(it, cmap[it]);
    216         }
    217         return *this;
    218       }
    219 
    220     };
    221 
    222     template <typename _Value>
    223     class EdgeMap
    224       : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
    225     public:
    226       typedef MappableGraphExtender Graph;
    227       typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    228 
    229       EdgeMap(const Graph& _g)
    230         : Parent(_g) {}
    231       EdgeMap(const Graph& _g, const _Value& _v)
    232         : Parent(_g, _v) {}
    233 
    234       EdgeMap& operator=(const EdgeMap& cmap) {
    235         return operator=<EdgeMap>(cmap);
    236       }
    237 
    238       template <typename CMap>
    239       EdgeMap& operator=(const CMap& cmap) {
    240         checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
    241         const typename Parent::Graph* graph = Parent::getGraph();
    242         Edge it;
    243         for (graph->first(it); it != INVALID; graph->next(it)) {
    244           Parent::set(it, cmap[it]);
    245         }
    246         return *this;
    247       }
    248     };
    249    
    250   };
    251 
    252   /// \e
    253   template <typename _Base>
    254   class MappableEdgeSetExtender : public _Base {
    255   public:
    256 
    257     typedef MappableEdgeSetExtender<_Base> Graph;
    258     typedef _Base Parent;
    259 
    260     typedef typename Parent::Edge Edge;
    261     typedef typename Parent::EdgeIt EdgeIt;
    262 
    263     template <typename _Value>
    264     class EdgeMap
    265       : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
    266     public:
    267       typedef MappableEdgeSetExtender Graph;
    268       typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    269 
    270       EdgeMap(const Graph& _g)
    271         : Parent(_g) {}
    272       EdgeMap(const Graph& _g, const _Value& _v)
    273         : Parent(_g, _v) {}
    274 
    275       EdgeMap& operator=(const EdgeMap& cmap) {
    276         return operator=<EdgeMap>(cmap);
    277       }
    278 
    279       template <typename CMap>
    280       EdgeMap& operator=(const CMap& cmap) {
    281         checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
    282         const typename Parent::Graph* graph = Parent::getGraph();
    283         Edge it;
    284         for (graph->first(it); it != INVALID; graph->next(it)) {
    285           Parent::set(it, cmap[it]);
    286         }
    287         return *this;
    288       }
    289     };
    290    
    291   };
    292 
    293   /// \e
    294   template <typename _Base>
    295   class MappableUGraphExtender :
    296     public MappableGraphExtender<_Base> {
    297   public:
    298 
    299     typedef MappableUGraphExtender Graph;
    300     typedef MappableGraphExtender<_Base> Parent;
    301 
    302     typedef typename Parent::UEdge UEdge;
    303 
    304     template <typename _Value>
    305     class UEdgeMap
    306       : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
    307     public:
    308       typedef MappableUGraphExtender Graph;
    309       typedef IterableMapExtender<
    310         DefaultMap<Graph, UEdge, _Value> > Parent;
    311 
    312       UEdgeMap(const Graph& _g)
    313         : Parent(_g) {}
    314       UEdgeMap(const Graph& _g, const _Value& _v)
    315         : Parent(_g, _v) {}
    316 
    317       UEdgeMap& operator=(const UEdgeMap& cmap) {
    318         return operator=<UEdgeMap>(cmap);
    319       }
    320 
    321       template <typename CMap>
    322       UEdgeMap& operator=(const CMap& cmap) {
    323         checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
    324         const typename Parent::Graph* graph = Parent::getGraph();
    325         UEdge it;
    326         for (graph->first(it); it != INVALID; graph->next(it)) {
    327           Parent::set(it, cmap[it]);
    328         }
    329         return *this;
    330       }
    331     };
    332 
    333 
    334   };
    335 
    336   /// \e
    337   template <typename _Base>
    338   class MappableUEdgeSetExtender :
    339     public MappableEdgeSetExtender<_Base> {
    340   public:
    341 
    342     typedef MappableUEdgeSetExtender Graph;
    343     typedef MappableEdgeSetExtender<_Base> Parent;
    344 
    345     typedef typename Parent::UEdge UEdge;
    346 
    347     template <typename _Value>
    348     class UEdgeMap
    349       : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
    350     public:
    351       typedef MappableUEdgeSetExtender Graph;
    352       typedef IterableMapExtender<
    353         DefaultMap<Graph, UEdge, _Value> > Parent;
    354 
    355       UEdgeMap(const Graph& _g)
    356         : Parent(_g) {}
    357       UEdgeMap(const Graph& _g, const _Value& _v)
    358         : Parent(_g, _v) {}
    359 
    360       UEdgeMap& operator=(const UEdgeMap& cmap) {
    361         return operator=<UEdgeMap>(cmap);
    362       }
    363 
    364       template <typename CMap>
    365       UEdgeMap& operator=(const CMap& cmap) {
    366         checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
    367         const typename Parent::Graph* graph = Parent::getGraph();
    368         UEdge it;
    369         for (graph->first(it); it != INVALID; graph->next(it)) {
    370           Parent::set(it, cmap[it]);
    371         }
    372         return *this;
    373       }
    374     };
    375 
    376 
    377   };
    378 
    379 
    380   template <typename _Base>
    381   class MappableBpUGraphExtender : public _Base {
    382   public:
    383 
    384     typedef _Base Parent;
    385     typedef MappableBpUGraphExtender Graph;
    386 
    387     typedef typename Parent::Node Node;
    388     typedef typename Parent::ANode ANode;
    389     typedef typename Parent::BNode BNode;
    390     typedef typename Parent::Edge Edge;
    391     typedef typename Parent::UEdge UEdge;
    392    
    393     template <typename _Value>
    394     class ANodeMap
    395       : public IterableMapExtender<DefaultMap<Graph, ANode, _Value> > {
    396     public:
    397       typedef MappableBpUGraphExtender Graph;
    398       typedef IterableMapExtender<DefaultMap<Graph, ANode, _Value> >
    399       Parent;
    400    
    401       ANodeMap(const Graph& _g)
    402         : Parent(_g) {}
    403       ANodeMap(const Graph& _g, const _Value& _v)
    404         : Parent(_g, _v) {}
    405    
    406       ANodeMap& operator=(const ANodeMap& cmap) {
    407         return operator=<ANodeMap>(cmap);
    408       }
    409    
    410 
    411       /// \brief Template assign operator.
    412       ///
    413       /// The given parameter should be conform to the ReadMap
    414       /// concept and could be indiced by the current item set of
    415       /// the ANodeMap. In this case the value for each item
    416       /// is assigned by the value of the given ReadMap.
    417       template <typename CMap>
    418       ANodeMap& operator=(const CMap& cmap) {
    419         checkConcept<concept::ReadMap<ANode, _Value>, CMap>();
    420         const typename Parent::Graph* graph = Parent::getGraph();
    421         ANode it;
    422         for (graph->first(it); it != INVALID; graph->next(it)) {
    423           Parent::set(it, cmap[it]);
    424         }
    425         return *this;
    426       }
    427    
    428     };
    429 
    430     template <typename _Value>
    431     class BNodeMap
    432       : public IterableMapExtender<DefaultMap<Graph, BNode, _Value> > {
    433     public:
    434       typedef MappableBpUGraphExtender Graph;
    435       typedef IterableMapExtender<DefaultMap<Graph, BNode, _Value> >
    436       Parent;
    437    
    438       BNodeMap(const Graph& _g)
    439         : Parent(_g) {}
    440       BNodeMap(const Graph& _g, const _Value& _v)
    441         : Parent(_g, _v) {}
    442    
    443       BNodeMap& operator=(const BNodeMap& cmap) {
    444         return operator=<BNodeMap>(cmap);
    445       }
    446    
    447 
    448       /// \brief Template assign operator.
    449       ///
    450       /// The given parameter should be conform to the ReadMap
    451       /// concept and could be indiced by the current item set of
    452       /// the BNodeMap. In this case the value for each item
    453       /// is assigned by the value of the given ReadMap.
    454       template <typename CMap>
    455       BNodeMap& operator=(const CMap& cmap) {
    456         checkConcept<concept::ReadMap<BNode, _Value>, CMap>();
    457         const typename Parent::Graph* graph = Parent::getGraph();
    458         BNode it;
    459         for (graph->first(it); it != INVALID; graph->next(it)) {
    460           Parent::set(it, cmap[it]);
    461         }
    462         return *this;
    463       }
    464    
    465     };
    466 
    467   protected:
    468 
    469     template <typename _Value>
    470     class NodeMapBase : public Parent::NodeNotifier::ObserverBase {
    471     public:
    472       typedef MappableBpUGraphExtender Graph;
    473 
    474       typedef Node Key;
    475       typedef _Value Value;
    476 
    477       /// The reference type of the map;
    478       typedef typename BNodeMap<_Value>::Reference Reference;
    479       /// The pointer type of the map;
    480       typedef typename BNodeMap<_Value>::Pointer Pointer;
    481      
    482       /// The const value type of the map.
    483       typedef const Value ConstValue;
    484       /// The const reference type of the map;
    485       typedef typename BNodeMap<_Value>::ConstReference ConstReference;
    486       /// The pointer type of the map;
    487       typedef typename BNodeMap<_Value>::ConstPointer ConstPointer;
    488 
    489       typedef True ReferenceMapTag;
    490 
    491       NodeMapBase(const Graph& _g)
    492         : graph(&_g), bNodeMap(_g), aNodeMap(_g) {
    493         Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
    494       }
    495       NodeMapBase(const Graph& _g, const _Value& _v)
    496         : graph(&_g), bNodeMap(_g, _v),
    497           aNodeMap(_g, _v) {
    498         Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
    499       }
    500 
    501       virtual ~NodeMapBase() {     
    502         if (Parent::NodeNotifier::ObserverBase::attached()) {
    503           Parent::NodeNotifier::ObserverBase::detach();
    504         }
    505       }
    506    
    507       ConstReference operator[](const Key& node) const {
    508         if (Parent::aNode(node)) {
    509           return aNodeMap[node];
    510         } else {
    511           return bNodeMap[node];
    512         }
    513       }
    514 
    515       Reference operator[](const Key& node) {
    516         if (Parent::aNode(node)) {
    517           return aNodeMap[node];
    518         } else {
    519           return bNodeMap[node];
    520         }
    521       }
    522 
    523       void set(const Key& node, const Value& value) {
    524         if (Parent::aNode(node)) {
    525           aNodeMap.set(node, value);
    526         } else {
    527           bNodeMap.set(node, value);
    528         }
    529       }
    530 
    531     protected:
    532      
    533       virtual void add(const Node&) {}
    534       virtual void add(const std::vector<Node>&) {}
    535       virtual void erase(const Node&) {}
    536       virtual void erase(const std::vector<Node>&) {}
    537       virtual void clear() {}
    538       virtual void build() {}
    539 
    540       const Graph* getGraph() const { return graph; }
    541      
    542     private:
    543       const Graph* graph;
    544       BNodeMap<_Value> bNodeMap;
    545       ANodeMap<_Value> aNodeMap;
    546     };
    547    
    548   public:
    549 
    550     template <typename _Value>
    551     class NodeMap
    552       : public IterableMapExtender<NodeMapBase<_Value> > {
    553     public:
    554       typedef MappableBpUGraphExtender Graph;
    555       typedef IterableMapExtender< NodeMapBase<_Value> > Parent;
    556    
    557       NodeMap(const Graph& _g)
    558         : Parent(_g) {}
    559       NodeMap(const Graph& _g, const _Value& _v)
    560         : Parent(_g, _v) {}
    561    
    562       NodeMap& operator=(const NodeMap& cmap) {
    563         return operator=<NodeMap>(cmap);
    564       }
    565    
    566 
    567       /// \brief Template assign operator.
    568       ///
    569       /// The given parameter should be conform to the ReadMap
    570       /// concept and could be indiced by the current item set of
    571       /// the NodeMap. In this case the value for each item
    572       /// is assigned by the value of the given ReadMap.
    573       template <typename CMap>
    574       NodeMap& operator=(const CMap& cmap) {
    575         checkConcept<concept::ReadMap<Node, _Value>, CMap>();
    576         const typename Parent::Graph* graph = Parent::getGraph();
    577         Node it;
    578         for (graph->first(it); it != INVALID; graph->next(it)) {
    579           Parent::set(it, cmap[it]);
    580         }
    581         return *this;
    582       }
    583    
    584     };
    585 
    586 
    587 
    588     template <typename _Value>
    589     class EdgeMap
    590       : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
    591     public:
    592       typedef MappableBpUGraphExtender Graph;
    593       typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    594    
    595       EdgeMap(const Graph& _g)
    596         : Parent(_g) {}
    597       EdgeMap(const Graph& _g, const _Value& _v)
    598         : Parent(_g, _v) {}
    599    
    600       EdgeMap& operator=(const EdgeMap& cmap) {
    601         return operator=<EdgeMap>(cmap);
    602       }
    603    
    604       template <typename CMap>
    605       EdgeMap& operator=(const CMap& cmap) {
    606         checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
    607         const typename Parent::Graph* graph = Parent::getGraph();
    608         Edge it;
    609         for (graph->first(it); it != INVALID; graph->next(it)) {
    610           Parent::set(it, cmap[it]);
    611         }
    612         return *this;
    613       }
    614     };
    615 
    616     template <typename _Value>
    617     class UEdgeMap
    618       : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
    619     public:
    620       typedef MappableBpUGraphExtender Graph;
    621       typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> >
    622       Parent;
    623    
    624       UEdgeMap(const Graph& _g)
    625         : Parent(_g) {}
    626       UEdgeMap(const Graph& _g, const _Value& _v)
    627         : Parent(_g, _v) {}
    628    
    629       UEdgeMap& operator=(const UEdgeMap& cmap) {
    630         return operator=<UEdgeMap>(cmap);
    631       }
    632    
    633       template <typename CMap>
    634       UEdgeMap& operator=(const CMap& cmap) {
    635         checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
    636         const typename Parent::Graph* graph = Parent::getGraph();
    637         UEdge it;
    638         for (graph->first(it); it != INVALID; graph->next(it)) {
    639           Parent::set(it, cmap[it]);
    640         }
    641         return *this;
    642       }
    643     };
    644  
    645   };
    646 
    647172}
    648173
  • lemon/bits/graph_extender.h

    r1956 r1979  
    2323#include <lemon/error.h>
    2424
     25#include <lemon/bits/default_map.h>
     26
    2527namespace lemon {
    2628
    27   template <typename _Base>
    28   class GraphExtender : public _Base {
     29  template <typename Base>
     30  class GraphExtender : public Base {
    2931  public:
    3032
    31     typedef _Base Parent;
     33    typedef Base Parent;
    3234    typedef GraphExtender Graph;
     35
     36    // Base extensions
    3337
    3438    typedef typename Parent::Node Node;
     
    6064    }
    6165
     66    // Alterable extension
     67
     68    typedef AlterationNotifier<Node> NodeNotifier;
     69    typedef AlterationNotifier<Edge> EdgeNotifier;
     70
     71
     72  protected:
     73
     74    mutable NodeNotifier node_notifier;
     75    mutable EdgeNotifier edge_notifier;
     76
     77  public:
     78
     79    NodeNotifier& getNotifier(Node) const {
     80      return node_notifier;
     81    }
     82   
     83    EdgeNotifier& getNotifier(Edge) const {
     84      return edge_notifier;
     85    }
     86
     87    class NodeIt : public Node {
     88      const Graph* graph;
     89    public:
     90
     91      NodeIt() {}
     92
     93      NodeIt(Invalid i) : Node(i) { }
     94
     95      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
     96        _graph.first(*static_cast<Node*>(this));
     97      }
     98
     99      NodeIt(const Graph& _graph, const Node& node)
     100        : Node(node), graph(&_graph) {}
     101
     102      NodeIt& operator++() {
     103        graph->next(*this);
     104        return *this;
     105      }
     106
     107    };
     108
     109
     110    class EdgeIt : public Edge {
     111      const Graph* graph;
     112    public:
     113
     114      EdgeIt() { }
     115
     116      EdgeIt(Invalid i) : Edge(i) { }
     117
     118      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
     119        _graph.first(*static_cast<Edge*>(this));
     120      }
     121
     122      EdgeIt(const Graph& _graph, const Edge& e) :
     123        Edge(e), graph(&_graph) { }
     124
     125      EdgeIt& operator++() {
     126        graph->next(*this);
     127        return *this;
     128      }
     129
     130    };
     131
     132
     133    class OutEdgeIt : public Edge {
     134      const Graph* graph;
     135    public:
     136
     137      OutEdgeIt() { }
     138
     139      OutEdgeIt(Invalid i) : Edge(i) { }
     140
     141      OutEdgeIt(const Graph& _graph, const Node& node)
     142        : graph(&_graph) {
     143        _graph.firstOut(*this, node);
     144      }
     145
     146      OutEdgeIt(const Graph& _graph, const Edge& edge)
     147        : Edge(edge), graph(&_graph) {}
     148
     149      OutEdgeIt& operator++() {
     150        graph->nextOut(*this);
     151        return *this;
     152      }
     153
     154    };
     155
     156
     157    class InEdgeIt : public Edge {
     158      const Graph* graph;
     159    public:
     160
     161      InEdgeIt() { }
     162
     163      InEdgeIt(Invalid i) : Edge(i) { }
     164
     165      InEdgeIt(const Graph& _graph, const Node& node)
     166        : graph(&_graph) {
     167        _graph.firstIn(*this, node);
     168      }
     169
     170      InEdgeIt(const Graph& _graph, const Edge& edge) :
     171        Edge(edge), graph(&_graph) {}
     172
     173      InEdgeIt& operator++() {
     174        graph->nextIn(*this);
     175        return *this;
     176      }
     177
     178    };
     179
     180    /// \brief Base node of the iterator
     181    ///
     182    /// Returns the base node (ie. the source in this case) of the iterator
     183    Node baseNode(const OutEdgeIt &e) const {
     184      return Parent::source(e);
     185    }
     186    /// \brief Running node of the iterator
     187    ///
     188    /// Returns the running node (ie. the target in this case) of the
     189    /// iterator
     190    Node runningNode(const OutEdgeIt &e) const {
     191      return Parent::target(e);
     192    }
     193
     194    /// \brief Base node of the iterator
     195    ///
     196    /// Returns the base node (ie. the target in this case) of the iterator
     197    Node baseNode(const InEdgeIt &e) const {
     198      return Parent::target(e);
     199    }
     200    /// \brief Running node of the iterator
     201    ///
     202    /// Returns the running node (ie. the source in this case) of the
     203    /// iterator
     204    Node runningNode(const InEdgeIt &e) const {
     205      return Parent::source(e);
     206    }
     207
     208   
     209    template <typename _Value>
     210    class NodeMap
     211      : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > {
     212    public:
     213      typedef GraphExtender Graph;
     214      typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent;
     215
     216      NodeMap(const Graph& _g)
     217        : Parent(_g) {}
     218      NodeMap(const Graph& _g, const _Value& _v)
     219        : Parent(_g, _v) {}
     220
     221      NodeMap& operator=(const NodeMap& cmap) {
     222        return operator=<NodeMap>(cmap);
     223      }
     224
     225
     226      /// \brief Template assign operator.
     227      ///
     228      /// The given parameter should be conform to the ReadMap
     229      /// concecpt and could be indiced by the current item set of
     230      /// the NodeMap. In this case the value for each item
     231      /// is assigned by the value of the given ReadMap.
     232      template <typename CMap>
     233      NodeMap& operator=(const CMap& cmap) {
     234        checkConcept<concept::ReadMap<Node, _Value>, CMap>();
     235        const typename Parent::Graph* graph = Parent::getGraph();
     236        Node it;
     237        for (graph->first(it); it != INVALID; graph->next(it)) {
     238          Parent::set(it, cmap[it]);
     239        }
     240        return *this;
     241      }
     242
     243    };
     244
     245    template <typename _Value>
     246    class EdgeMap
     247      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
     248    public:
     249      typedef GraphExtender Graph;
     250      typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
     251
     252      EdgeMap(const Graph& _g)
     253        : Parent(_g) {}
     254      EdgeMap(const Graph& _g, const _Value& _v)
     255        : Parent(_g, _v) {}
     256
     257      EdgeMap& operator=(const EdgeMap& cmap) {
     258        return operator=<EdgeMap>(cmap);
     259      }
     260
     261      template <typename CMap>
     262      EdgeMap& operator=(const CMap& cmap) {
     263        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
     264        const typename Parent::Graph* graph = Parent::getGraph();
     265        Edge it;
     266        for (graph->first(it); it != INVALID; graph->next(it)) {
     267          Parent::set(it, cmap[it]);
     268        }
     269        return *this;
     270      }
     271    };
     272
     273
     274    Node addNode() {
     275      Node node = Parent::addNode();
     276      getNotifier(Node()).add(node);
     277      return node;
     278    }
     279   
     280    Edge addEdge(const Node& from, const Node& to) {
     281      Edge edge = Parent::addEdge(from, to);
     282      getNotifier(Edge()).add(edge);
     283      return edge;
     284    }
     285
     286    void clear() {
     287      getNotifier(Edge()).clear();
     288      getNotifier(Node()).clear();
     289      Parent::clear();
     290    }
     291
     292
     293    void erase(const Node& node) {
     294      Edge edge;
     295      Parent::firstOut(edge, node);
     296      while (edge != INVALID ) {
     297        erase(edge);
     298        Parent::firstOut(edge, node);
     299      }
     300
     301      Parent::firstIn(edge, node);
     302      while (edge != INVALID ) {
     303        erase(edge);
     304        Parent::firstIn(edge, node);
     305      }
     306
     307      getNotifier(Node()).erase(node);
     308      Parent::erase(node);
     309    }
     310   
     311    void erase(const Edge& edge) {
     312      getNotifier(Edge()).erase(edge);
     313      Parent::erase(edge);
     314    }
     315
     316
     317    ~GraphExtender() {
     318      getNotifier(Edge()).clear();
     319      getNotifier(Node()).clear();
     320    }
    62321  };
    63322
    64   template <typename _Base>
    65   class UGraphExtender : public _Base {
    66     typedef _Base Parent;
    67     typedef UGraphExtender Graph;
     323  template <typename Base>
     324  class UGraphBaseExtender : public Base {
    68325
    69326  public:
    70327
     328    typedef Base Parent;
    71329    typedef typename Parent::Edge UEdge;
    72330    typedef typename Parent::Node Node;
    73331
     332    typedef True UndirectedTag;
     333
    74334    class Edge : public UEdge {
    75       friend class UGraphExtender;
     335      friend class UGraphBaseExtender;
    76336
    77337    protected:
    78       // FIXME: Marci use opposite logic in his graph adaptors. It would
    79       // be reasonable to syncronize...
    80338      bool forward;
    81339
     
    102360
    103361
    104     /// \brief Edge of opposite direction.
    105     ///
    106     /// Returns the Edge of opposite direction.
    107     Edge oppositeEdge(const Edge &e) const {
    108       return Edge(e,!e.forward);
    109     }
    110 
    111   public:
    112     /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
    113     /// or something???
     362
    114363    using Parent::source;
    115364
     
    119368    }
    120369
    121     /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
    122     /// or something???
    123370    using Parent::target;
    124371
     
    126373    Node target(const Edge &e) const {
    127374      return e.forward ? Parent::target(e) : Parent::source(e);
    128     }
    129 
    130     Node oppositeNode(const Node &n, const UEdge &e) const {
    131       if( n == Parent::source(e))
    132         return Parent::target(e);
    133       else if( n == Parent::target(e))
    134         return Parent::source(e);
    135       else
    136         return INVALID;
    137     }
    138 
    139     /// \brief Directed edge from an undirected edge and a source node.
    140     ///
    141     /// Returns a (directed) Edge corresponding to the specified UEdge
    142     /// and source Node.
    143     ///
    144     Edge direct(const UEdge &ue, const Node &s) const {
    145       return Edge(ue, s == source(ue));
    146375    }
    147376
     
    164393
    165394    using Parent::first;
     395    using Parent::next;
     396
    166397    void first(Edge &e) const {
    167398      Parent::first(e);
     
    169400    }
    170401
    171     using Parent::next;
    172402    void next(Edge &e) const {
    173403      if( e.forward ) {
     
    179409      }
    180410    }
    181 
    182   public:
    183411
    184412    void firstOut(Edge &e, const Node &n) const {
     
    230458    }
    231459
    232     void firstInc(UEdge &e, const Node &n) const {
    233       Parent::firstOut(e, n);
    234       if (e != INVALID) return;
    235       Parent::firstIn(e, n);
    236     }
    237     void nextInc(UEdge &e, const Node &n) const {
    238       if (Parent::source(e) == n) {
    239         Parent::nextOut(e);
    240         if (e != INVALID) return;
    241         Parent::firstIn(e, n);
    242       } else {
    243         Parent::nextIn(e);
    244       }
    245     }
    246 
    247460    void firstInc(UEdge &e, bool &d, const Node &n) const {
    248461      d = true;
     
    252465      Parent::firstIn(e, n);
    253466    }
     467
    254468    void nextInc(UEdge &e, bool &d) const {
    255469      if (d) {
     
    264478    }
    265479
    266     // Miscellaneous stuff:
    267 
    268     /// \todo these methods (id, maxEdgeId) should be moved into separate
    269     /// Extender
    270 
    271     // using Parent::id;
    272     // Using "using" is not a good idea, cause it could be that there is
    273     // no "id" in Parent...
     480    Node nodeFromId(int id) const {
     481      return Parent::nodeFromId(id);
     482    }
     483
     484    Edge edgeFromId(int id) const {
     485      return direct(Parent::edgeFromId(id >> 1), bool(id & 1));
     486    }
     487
     488    UEdge uEdgeFromId(int id) const {
     489      return Parent::edgeFromId(id >> 1);
     490    }
    274491
    275492    int id(const Node &n) const {
     
    297514    }
    298515
    299     int maxId(Node) const {
    300       return maxNodeId();
    301     }
    302 
    303     int maxId(Edge) const {
    304       return maxEdgeId();
    305     }
    306     int maxId(UEdge) const {
    307       return maxUEdgeId();
    308     }
    309516
    310517    int edgeNum() const {
     
    315522      return Parent::edgeNum();
    316523    }
    317 
    318     Node nodeFromId(int id) const {
    319       return Parent::nodeFromId(id);
    320     }
    321 
    322     Edge edgeFromId(int id) const {
    323       return direct(Parent::edgeFromId(id >> 1), bool(id & 1));
    324     }
    325 
    326     UEdge uEdgeFromId(int id) const {
    327       return Parent::edgeFromId(id >> 1);
    328     }
    329 
    330     Node fromId(int id, Node) const {
    331       return nodeFromId(id);
    332     }
    333 
    334     Edge fromId(int id, Edge) const {
    335       return edgeFromId(id);
    336     }
    337 
    338     UEdge fromId(int id, UEdge) const {
    339       return uEdgeFromId(id);
    340     }
    341 
    342524
    343525    Edge findEdge(Node source, Node target, Edge prev) const {
     
    376558      return INVALID;
    377559    }
    378 
    379560  };
    380561
    381562
    382   template <typename _Base>
    383   class BpUGraphExtender : public _Base {
     563  template <typename Base>
     564  class UGraphExtender : public Base {
    384565  public:
    385     typedef _Base Parent;
    386     typedef BpUGraphExtender Graph;
     566   
     567    typedef Base Parent;
     568    typedef UGraphExtender Graph;
     569
     570    typedef typename Parent::Node Node;
     571    typedef typename Parent::Edge Edge;
     572    typedef typename Parent::UEdge UEdge;
     573
     574    // UGraph extension   
     575
     576    int maxId(Node) const {
     577      return Parent::maxNodeId();
     578    }
     579
     580    int maxId(Edge) const {
     581      return Parent::maxEdgeId();
     582    }
     583
     584    int maxId(UEdge) const {
     585      return Parent::maxUEdgeId();
     586    }
     587
     588    Node fromId(int id, Node) const {
     589      return Parent::nodeFromId(id);
     590    }
     591
     592    Edge fromId(int id, Edge) const {
     593      return Parent::edgeFromId(id);
     594    }
     595
     596    UEdge fromId(int id, UEdge) const {
     597      return Parent::uEdgeFromId(id);
     598    }
     599
     600    Node oppositeNode(const Node &n, const UEdge &e) const {
     601      if( n == Parent::source(e))
     602        return Parent::target(e);
     603      else if( n == Parent::target(e))
     604        return Parent::source(e);
     605      else
     606        return INVALID;
     607    }
     608
     609    Edge oppositeEdge(const Edge &e) const {
     610      return Parent::direct(e, !Parent::direction(e));
     611    }
     612
     613    using Parent::direct;
     614    Edge direct(const UEdge &ue, const Node &s) const {
     615      return Parent::direct(ue, Parent::source(ue) == s);
     616    }
     617
     618    // Alterable extension
     619
     620    typedef AlterationNotifier<Node> NodeNotifier;
     621    typedef AlterationNotifier<Edge> EdgeNotifier;
     622    typedef AlterationNotifier<UEdge> UEdgeNotifier;
     623
     624
     625  protected:
     626
     627    mutable NodeNotifier node_notifier;
     628    mutable EdgeNotifier edge_notifier;
     629    mutable UEdgeNotifier uedge_notifier;
     630
     631  public:
     632
     633    NodeNotifier& getNotifier(Node) const {
     634      return node_notifier;
     635    }
     636   
     637    EdgeNotifier& getNotifier(Edge) const {
     638      return edge_notifier;
     639    }
     640
     641    UEdgeNotifier& getNotifier(UEdge) const {
     642      return uedge_notifier;
     643    }
     644
     645
     646
     647    class NodeIt : public Node {
     648      const Graph* graph;
     649    public:
     650
     651      NodeIt() {}
     652
     653      NodeIt(Invalid i) : Node(i) { }
     654
     655      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
     656        _graph.first(*static_cast<Node*>(this));
     657      }
     658
     659      NodeIt(const Graph& _graph, const Node& node)
     660        : Node(node), graph(&_graph) {}
     661
     662      NodeIt& operator++() {
     663        graph->next(*this);
     664        return *this;
     665      }
     666
     667    };
     668
     669
     670    class EdgeIt : public Edge {
     671      const Graph* graph;
     672    public:
     673
     674      EdgeIt() { }
     675
     676      EdgeIt(Invalid i) : Edge(i) { }
     677
     678      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
     679        _graph.first(*static_cast<Edge*>(this));
     680      }
     681
     682      EdgeIt(const Graph& _graph, const Edge& e) :
     683        Edge(e), graph(&_graph) { }
     684
     685      EdgeIt& operator++() {
     686        graph->next(*this);
     687        return *this;
     688      }
     689
     690    };
     691
     692
     693    class OutEdgeIt : public Edge {
     694      const Graph* graph;
     695    public:
     696
     697      OutEdgeIt() { }
     698
     699      OutEdgeIt(Invalid i) : Edge(i) { }
     700
     701      OutEdgeIt(const Graph& _graph, const Node& node)
     702        : graph(&_graph) {
     703        _graph.firstOut(*this, node);
     704      }
     705
     706      OutEdgeIt(const Graph& _graph, const Edge& edge)
     707        : Edge(edge), graph(&_graph) {}
     708
     709      OutEdgeIt& operator++() {
     710        graph->nextOut(*this);
     711        return *this;
     712      }
     713
     714    };
     715
     716
     717    class InEdgeIt : public Edge {
     718      const Graph* graph;
     719    public:
     720
     721      InEdgeIt() { }
     722
     723      InEdgeIt(Invalid i) : Edge(i) { }
     724
     725      InEdgeIt(const Graph& _graph, const Node& node)
     726        : graph(&_graph) {
     727        _graph.firstIn(*this, node);
     728      }
     729
     730      InEdgeIt(const Graph& _graph, const Edge& edge) :
     731        Edge(edge), graph(&_graph) {}
     732
     733      InEdgeIt& operator++() {
     734        graph->nextIn(*this);
     735        return *this;
     736      }
     737
     738    };
     739
     740
     741    class UEdgeIt : public Parent::UEdge {
     742      const Graph* graph;
     743    public:
     744
     745      UEdgeIt() { }
     746
     747      UEdgeIt(Invalid i) : UEdge(i) { }
     748
     749      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
     750        _graph.first(*static_cast<UEdge*>(this));
     751      }
     752
     753      UEdgeIt(const Graph& _graph, const UEdge& e) :
     754        UEdge(e), graph(&_graph) { }
     755
     756      UEdgeIt& operator++() {
     757        graph->next(*this);
     758        return *this;
     759      }
     760
     761    };
     762
     763    class IncEdgeIt : public Parent::UEdge {
     764      friend class UGraphExtender;
     765      const Graph* graph;
     766      bool direction;
     767    public:
     768
     769      IncEdgeIt() { }
     770
     771      IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
     772
     773      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
     774        _graph.firstInc(*this, direction, n);
     775      }
     776
     777      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
     778        : graph(&_graph), UEdge(ue) {
     779        direction = (_graph.source(ue) == n);
     780      }
     781
     782      IncEdgeIt& operator++() {
     783        graph->nextInc(*this, direction);
     784        return *this;
     785      }
     786    };
     787
     788    /// \brief Base node of the iterator
     789    ///
     790    /// Returns the base node (ie. the source in this case) of the iterator
     791    Node baseNode(const OutEdgeIt &e) const {
     792      return Parent::source((Edge)e);
     793    }
     794    /// \brief Running node of the iterator
     795    ///
     796    /// Returns the running node (ie. the target in this case) of the
     797    /// iterator
     798    Node runningNode(const OutEdgeIt &e) const {
     799      return Parent::target((Edge)e);
     800    }
     801
     802    /// \brief Base node of the iterator
     803    ///
     804    /// Returns the base node (ie. the target in this case) of the iterator
     805    Node baseNode(const InEdgeIt &e) const {
     806      return Parent::target((Edge)e);
     807    }
     808    /// \brief Running node of the iterator
     809    ///
     810    /// Returns the running node (ie. the source in this case) of the
     811    /// iterator
     812    Node runningNode(const InEdgeIt &e) const {
     813      return Parent::source((Edge)e);
     814    }
     815
     816    /// Base node of the iterator
     817    ///
     818    /// Returns the base node of the iterator
     819    Node baseNode(const IncEdgeIt &e) const {
     820      return e.direction ? source(e) : target(e);
     821    }
     822    /// Running node of the iterator
     823    ///
     824    /// Returns the running node of the iterator
     825    Node runningNode(const IncEdgeIt &e) const {
     826      return e.direction ? target(e) : source(e);
     827    }
     828
     829    // Mappable extension
     830
     831    template <typename _Value>
     832    class NodeMap
     833      : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > {
     834    public:
     835      typedef UGraphExtender Graph;
     836      typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent;
     837
     838      NodeMap(const Graph& _g)
     839        : Parent(_g) {}
     840      NodeMap(const Graph& _g, const _Value& _v)
     841        : Parent(_g, _v) {}
     842
     843      NodeMap& operator=(const NodeMap& cmap) {
     844        return operator=<NodeMap>(cmap);
     845      }
     846
     847
     848      /// \brief Template assign operator.
     849      ///
     850      /// The given parameter should be conform to the ReadMap
     851      /// concecpt and could be indiced by the current item set of
     852      /// the NodeMap. In this case the value for each item
     853      /// is assigned by the value of the given ReadMap.
     854      template <typename CMap>
     855      NodeMap& operator=(const CMap& cmap) {
     856        checkConcept<concept::ReadMap<Node, _Value>, CMap>();
     857        const typename Parent::Graph* graph = Parent::getGraph();
     858        Node it;
     859        for (graph->first(it); it != INVALID; graph->next(it)) {
     860          Parent::set(it, cmap[it]);
     861        }
     862        return *this;
     863      }
     864
     865    };
     866
     867    template <typename _Value>
     868    class EdgeMap
     869      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
     870    public:
     871      typedef UGraphExtender Graph;
     872      typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
     873
     874      EdgeMap(const Graph& _g)
     875        : Parent(_g) {}
     876      EdgeMap(const Graph& _g, const _Value& _v)
     877        : Parent(_g, _v) {}
     878
     879      EdgeMap& operator=(const EdgeMap& cmap) {
     880        return operator=<EdgeMap>(cmap);
     881      }
     882
     883      template <typename CMap>
     884      EdgeMap& operator=(const CMap& cmap) {
     885        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
     886        const typename Parent::Graph* graph = Parent::getGraph();
     887        Edge it;
     888        for (graph->first(it); it != INVALID; graph->next(it)) {
     889          Parent::set(it, cmap[it]);
     890        }
     891        return *this;
     892      }
     893    };
     894
     895
     896    template <typename _Value>
     897    class UEdgeMap
     898      : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
     899    public:
     900      typedef UGraphExtender Graph;
     901      typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
     902
     903      UEdgeMap(const Graph& _g)
     904        : Parent(_g) {}
     905      UEdgeMap(const Graph& _g, const _Value& _v)
     906        : Parent(_g, _v) {}
     907
     908      UEdgeMap& operator=(const UEdgeMap& cmap) {
     909        return operator=<UEdgeMap>(cmap);
     910      }
     911
     912      template <typename CMap>
     913      UEdgeMap& operator=(const CMap& cmap) {
     914        checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
     915        const typename Parent::Graph* graph = Parent::getGraph();
     916        UEdge it;
     917        for (graph->first(it); it != INVALID; graph->next(it)) {
     918          Parent::set(it, cmap[it]);
     919        }
     920        return *this;
     921      }
     922    };
     923
     924    // Alteration extension
     925
     926    Node addNode() {
     927      Node node = Parent::addNode();
     928      getNotifier(Node()).add(node);
     929      return node;
     930    }
     931
     932    UEdge addEdge(const Node& from, const Node& to) {
     933      UEdge uedge = Parent::addEdge(from, to);
     934      getNotifier(UEdge()).add(uedge);
     935      getNotifier(Edge()).add(Parent::direct(uedge, true));
     936      getNotifier(Edge()).add(Parent::direct(uedge, false));
     937      return uedge;
     938    }
     939   
     940    void clear() {
     941      getNotifier(Edge()).clear();
     942      getNotifier(UEdge()).clear();
     943      getNotifier(Node()).clear();
     944      Parent::clear();
     945    }
     946
     947    void erase(const Node& node) {
     948      Edge edge;
     949      Parent::firstOut(edge, node);
     950      while (edge != INVALID ) {
     951        erase(edge);
     952        Parent::firstOut(edge, node);
     953      }
     954
     955      Parent::firstIn(edge, node);
     956      while (edge != INVALID ) {
     957        erase(edge);
     958        Parent::firstIn(edge, node);
     959      }
     960
     961      getNotifier(Node()).erase(node);
     962      Parent::erase(node);
     963    }
     964
     965    void erase(const UEdge& uedge) {
     966      getNotifier(Edge()).erase(Parent::direct(uedge, true));
     967      getNotifier(Edge()).erase(Parent::direct(uedge, false));
     968      getNotifier(UEdge()).erase(uedge);
     969      Parent::erase(uedge);
     970    }
     971
     972    ~UGraphExtender() {
     973      getNotifier(Edge()).clear();
     974      getNotifier(UEdge()).clear();
     975      getNotifier(Node()).clear();
     976    }
     977
     978  };
     979
     980
     981  template <typename Base>
     982  class BpUGraphBaseExtender : public Base {
     983  public:
     984    typedef Base Parent;
     985    typedef BpUGraphBaseExtender Graph;
    387986
    388987    typedef typename Parent::Node Node;
    389988    typedef typename Parent::Edge UEdge;
    390989
     990
    391991    using Parent::first;
    392992    using Parent::next;
    393993
    394994    using Parent::id;
     995
     996    class ANode : public Node {
     997      friend class BpUGraphBaseExtender;
     998    public:
     999      ANode() {}
     1000      ANode(const Node& node) : Node(node) {
     1001        LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
     1002                     typename Parent::NodeSetError());
     1003      }
     1004      ANode(Invalid) : Node(INVALID) {}
     1005    };
     1006
     1007    void first(ANode& node) const {
     1008      Parent::firstANode(static_cast<Node&>(node));
     1009    }
     1010    void next(ANode& node) const {
     1011      Parent::nextANode(static_cast<Node&>(node));
     1012    }
     1013
     1014    int id(const ANode& node) const {
     1015      return Parent::aNodeId(node);
     1016    }
     1017
     1018    class BNode : public Node {
     1019      friend class BpUGraphBaseExtender;
     1020    public:
     1021      BNode() {}
     1022      BNode(const Node& node) : Node(node) {
     1023        LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
     1024                     typename Parent::NodeSetError());
     1025      }
     1026      BNode(Invalid) : Node(INVALID) {}
     1027    };
     1028
     1029    void first(BNode& node) const {
     1030      Parent::firstBNode(static_cast<Node&>(node));
     1031    }
     1032    void next(BNode& node) const {
     1033      Parent::nextBNode(static_cast<Node&>(node));
     1034    }
     1035 
     1036    int id(const BNode& node) const {
     1037      return Parent::aNodeId(node);
     1038    }
    3951039
    3961040    Node source(const UEdge& edge) const {
     
    4281072
    4291073    class Edge : public UEdge {
    430       friend class BpUGraphExtender;
     1074      friend class BpUGraphBaseExtender;
    4311075    protected:
    4321076      bool forward;
     
    5051149    }
    5061150
     1151    int id(const Edge& edge) const {
     1152      return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1);
     1153    }
     1154    Edge edgeFromId(int id) const {
     1155      return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0);
     1156    }
     1157    int maxEdgeId() const {
     1158      return (Parent::maxId(UEdge()) << 1) + 1;
     1159    }
     1160
    5071161    bool direction(const Edge& edge) const {
    5081162      return edge.forward;
    5091163    }
    5101164
    511     Edge direct(const UEdge& edge, const Node& node) const {
    512       return Edge(edge, node == Parent::source(edge));
    513     }
    514 
    5151165    Edge direct(const UEdge& edge, bool direction) const {
    5161166      return Edge(edge, direction);
    5171167    }
     1168  };
     1169
     1170  template <typename Base>
     1171  class BpUGraphExtender : public Base {
     1172  public:
     1173    typedef Base Parent;
     1174    typedef BpUGraphExtender Graph;
     1175
     1176    typedef typename Parent::Node Node;
     1177    typedef typename Parent::BNode BNode;
     1178    typedef typename Parent::ANode ANode;
     1179    typedef typename Parent::Edge Edge;
     1180    typedef typename Parent::UEdge UEdge;
    5181181
    5191182    Node oppositeNode(const UEdge& edge, const Node& node) const {
     
    5221185    }
    5231186
     1187    using Parent::direct;
     1188    Edge direct(const UEdge& edge, const Node& node) const {
     1189      return Edge(edge, node == Parent::source(edge));
     1190    }
     1191
    5241192    Edge oppositeEdge(const Edge& edge) const {
    525       return Edge(edge, !edge.forward);
    526     }
    527 
    528     int id(const Edge& edge) const {
    529       return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1);
    530     }
    531     Edge edgeFromId(int id) const {
    532       return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0);
    533     }
    534     int maxEdgeId() const {
    535       return (Parent::maxId(UEdge()) << 1) + 1;
    536     }
    537 
    538     class ANode : public Node {
    539       friend class BpUGraphExtender;
    540     public:
    541       ANode() {}
    542       ANode(const Node& node) : Node(node) {
    543         LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
    544                      typename Parent::NodeSetError());
    545       }
    546       ANode(Invalid) : Node(INVALID) {}
    547     };
    548 
    549     void first(ANode& node) const {
    550       Parent::firstANode(static_cast<Node&>(node));
    551     }
    552     void next(ANode& node) const {
    553       Parent::nextANode(static_cast<Node&>(node));
    554     }
    555 
    556     int id(const ANode& node) const {
    557       return Parent::aNodeId(node);
    558     }
    559 
    560     class BNode : public Node {
    561       friend class BpUGraphExtender;
    562     public:
    563       BNode() {}
    564       BNode(const Node& node) : Node(node) {
    565         LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
    566                      typename Parent::NodeSetError());
    567       }
    568       BNode(Invalid) : Node(INVALID) {}
    569     };
    570 
    571     void first(BNode& node) const {
    572       Parent::firstBNode(static_cast<Node&>(node));
    573     }
    574     void next(BNode& node) const {
    575       Parent::nextBNode(static_cast<Node&>(node));
    576     }
    577  
    578     int id(const BNode& node) const {
    579       return Parent::aNodeId(node);
    580     }
    581 
     1193      return Parent::direct(edge, !Parent::direction(edge));
     1194    }
    5821195
    5831196
     
    5921205    }
    5931206    int maxId(Edge) const {
    594       return maxEdgeId();
     1207      return Parent::maxEdgeId();
    5951208    }
    5961209    int maxId(UEdge) const {
    597       return maxUEdgeId();
     1210      return Parent::maxUEdgeId();
    5981211    }
    5991212
     
    6091222    }
    6101223    Edge fromId(int id, Edge) const {
    611       return edgeFromId(id);
     1224      return Parent::edgeFromId(id);
    6121225    }
    6131226    UEdge fromId(int id, UEdge) const {
    614       return uEdgeFromId(id);
    615     }
     1227      return Parent::uEdgeFromId(id);
     1228    } 
     1229 
     1230    typedef AlterationNotifier<Node> NodeNotifier;
     1231    typedef AlterationNotifier<BNode> BNodeNotifier;
     1232    typedef AlterationNotifier<ANode> ANodeNotifier;
     1233    typedef AlterationNotifier<Edge> EdgeNotifier;
     1234    typedef AlterationNotifier<UEdge> UEdgeNotifier;
     1235
     1236  protected:
     1237
     1238    mutable NodeNotifier nodeNotifier;
     1239    mutable BNodeNotifier bNodeNotifier;
     1240    mutable ANodeNotifier aNodeNotifier;
     1241    mutable EdgeNotifier edgeNotifier;
     1242    mutable UEdgeNotifier uEdgeNotifier;
     1243
     1244  public:
     1245
     1246    NodeNotifier& getNotifier(Node) const {
     1247      return nodeNotifier;
     1248    }
     1249
     1250    BNodeNotifier& getNotifier(BNode) const {
     1251      return bNodeNotifier;
     1252    }
     1253
     1254    ANodeNotifier& getNotifier(ANode) const {
     1255      return aNodeNotifier;
     1256    }
     1257
     1258    EdgeNotifier& getNotifier(Edge) const {
     1259      return edgeNotifier;
     1260    }
     1261
     1262    UEdgeNotifier& getNotifier(UEdge) const {
     1263      return uEdgeNotifier;
     1264    }
     1265
     1266    ~BpUGraphExtender() {
     1267      getNotifier(UEdge()).clear();
     1268      getNotifier(Edge()).clear();
     1269      getNotifier(ANode()).clear();
     1270      getNotifier(BNode()).clear();
     1271      getNotifier(Node()).clear();
     1272    }
     1273
     1274 
     1275    class NodeIt : public Node {
     1276      const Graph* graph;
     1277    public:
     1278   
     1279      NodeIt() { }
     1280   
     1281      NodeIt(Invalid i) : Node(INVALID) { }
     1282   
     1283      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
     1284        graph->first(static_cast<Node&>(*this));
     1285      }
     1286
     1287      NodeIt(const Graph& _graph, const Node& node)
     1288        : Node(node), graph(&_graph) { }
     1289   
     1290      NodeIt& operator++() {
     1291        graph->next(*this);
     1292        return *this;
     1293      }
     1294
     1295    };
     1296
     1297    class ANodeIt : public Node {
     1298      friend class BpUGraphExtender;
     1299      const Graph* graph;
     1300    public:
     1301   
     1302      ANodeIt() { }
     1303   
     1304      ANodeIt(Invalid i) : Node(INVALID) { }
     1305   
     1306      explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
     1307        graph->firstANode(static_cast<Node&>(*this));
     1308      }
     1309
     1310      ANodeIt(const Graph& _graph, const Node& node)
     1311        : Node(node), graph(&_graph) {}
     1312   
     1313      ANodeIt& operator++() {
     1314        graph->nextANode(*this);
     1315        return *this;
     1316      }
     1317    };
     1318
     1319    class BNodeIt : public Node {
     1320      friend class BpUGraphExtender;
     1321      const Graph* graph;
     1322    public:
     1323   
     1324      BNodeIt() { }
     1325   
     1326      BNodeIt(Invalid i) : Node(INVALID) { }
     1327   
     1328      explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
     1329        graph->firstBNode(static_cast<Node&>(*this));
     1330      }
     1331
     1332      BNodeIt(const Graph& _graph, const Node& node)
     1333        : Node(node), graph(&_graph) {}
     1334   
     1335      BNodeIt& operator++() {
     1336        graph->nextBNode(*this);
     1337        return *this;
     1338      }
     1339    };
     1340
     1341    class EdgeIt : public Edge {
     1342      friend class BpUGraphExtender;
     1343      const Graph* graph;
     1344    public:
     1345   
     1346      EdgeIt() { }
     1347   
     1348      EdgeIt(Invalid i) : Edge(INVALID) { }
     1349   
     1350      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
     1351        graph->first(static_cast<Edge&>(*this));
     1352      }
     1353
     1354      EdgeIt(const Graph& _graph, const Edge& edge)
     1355        : Edge(edge), graph(&_graph) { }
     1356   
     1357      EdgeIt& operator++() {
     1358        graph->next(*this);
     1359        return *this;
     1360      }
     1361
     1362    };
     1363
     1364    class UEdgeIt : public UEdge {
     1365      friend class BpUGraphExtender;
     1366      const Graph* graph;
     1367    public:
     1368   
     1369      UEdgeIt() { }
     1370   
     1371      UEdgeIt(Invalid i) : UEdge(INVALID) { }
     1372   
     1373      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
     1374        graph->first(static_cast<UEdge&>(*this));
     1375      }
     1376
     1377      UEdgeIt(const Graph& _graph, const UEdge& edge)
     1378        : UEdge(edge), graph(&_graph) { }
     1379   
     1380      UEdgeIt& operator++() {
     1381        graph->next(*this);
     1382        return *this;
     1383      }
     1384    };
     1385
     1386    class OutEdgeIt : public Edge {
     1387      friend class BpUGraphExtender;
     1388      const Graph* graph;
     1389    public:
     1390   
     1391      OutEdgeIt() { }
     1392   
     1393      OutEdgeIt(Invalid i) : Edge(i) { }
     1394   
     1395      OutEdgeIt(const Graph& _graph, const Node& node)
     1396        : graph(&_graph) {
     1397        graph->firstOut(*this, node);
     1398      }
     1399   
     1400      OutEdgeIt(const Graph& _graph, const Edge& edge)
     1401        : Edge(edge), graph(&_graph) {}
     1402   
     1403      OutEdgeIt& operator++() {
     1404        graph->nextOut(*this);
     1405        return *this;
     1406      }
     1407
     1408    };
     1409
     1410
     1411    class InEdgeIt : public Edge {
     1412      friend class BpUGraphExtender;
     1413      const Graph* graph;
     1414    public:
     1415   
     1416      InEdgeIt() { }
     1417   
     1418      InEdgeIt(Invalid i) : Edge(i) { }
     1419   
     1420      InEdgeIt(const Graph& _graph, const Node& node)
     1421        : graph(&_graph) {
     1422        graph->firstIn(*this, node);
     1423      }
     1424   
     1425      InEdgeIt(const Graph& _graph, const Edge& edge) :
     1426        Edge(edge), graph(&_graph) {}
     1427   
     1428      InEdgeIt& operator++() {
     1429        graph->nextIn(*this);
     1430        return *this;
     1431      }
     1432
     1433    };
     1434 
     1435    /// \brief Base node of the iterator
     1436    ///
     1437    /// Returns the base node (ie. the source in this case) of the iterator
     1438    Node baseNode(const OutEdgeIt &e) const {
     1439      return Parent::source((Edge&)e);
     1440    }
     1441    /// \brief Running node of the iterator
     1442    ///
     1443    /// Returns the running node (ie. the target in this case) of the
     1444    /// iterator
     1445    Node runningNode(const OutEdgeIt &e) const {
     1446      return Parent::target((Edge&)e);
     1447    }
     1448 
     1449    /// \brief Base node of the iterator
     1450    ///
     1451    /// Returns the base node (ie. the target in this case) of the iterator
     1452    Node baseNode(const InEdgeIt &e) const {
     1453      return Parent::target((Edge&)e);
     1454    }
     1455    /// \brief Running node of the iterator
     1456    ///
     1457    /// Returns the running node (ie. the source in this case) of the
     1458    /// iterator
     1459    Node runningNode(const InEdgeIt &e) const {
     1460      return Parent::source((Edge&)e);
     1461    }
     1462 
     1463    class IncEdgeIt : public Parent::UEdge {
     1464      friend class BpUGraphExtender;
     1465      const Graph* graph;
     1466      bool direction;
     1467    public:
     1468   
     1469      IncEdgeIt() { }
     1470   
     1471      IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
     1472   
     1473      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
     1474        graph->firstInc(*this, direction, n);
     1475      }
     1476
     1477      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
     1478        : graph(&_graph), UEdge(ue) {
     1479        direction = (graph->source(ue) == n);
     1480      }
     1481
     1482      IncEdgeIt& operator++() {
     1483        graph->nextInc(*this, direction);
     1484        return *this;
     1485      }
     1486    };
     1487 
     1488
     1489    /// Base node of the iterator
     1490    ///
     1491    /// Returns the base node of the iterator
     1492    Node baseNode(const IncEdgeIt &e) const {
     1493      return e.direction ? source(e) : target(e);
     1494    }
     1495
     1496    /// Running node of the iterator
     1497    ///
     1498    /// Returns the running node of the iterator
     1499    Node runningNode(const IncEdgeIt &e) const {
     1500      return e.direction ? target(e) : source(e);
     1501    }
     1502
     1503    template <typename _Value>
     1504    class ANodeMap
     1505      : public IterableMapExtender<DefaultMap<Graph, ANode, _Value> > {
     1506    public:
     1507      typedef BpUGraphExtender Graph;
     1508      typedef IterableMapExtender<DefaultMap<Graph, ANode, _Value> >
     1509      Parent;
     1510   
     1511      ANodeMap(const Graph& _g)
     1512        : Parent(_g) {}
     1513      ANodeMap(const Graph& _g, const _Value& _v)
     1514        : Parent(_g, _v) {}
     1515   
     1516      ANodeMap& operator=(const ANodeMap& cmap) {
     1517        return operator=<ANodeMap>(cmap);
     1518      }
     1519   
     1520
     1521      /// \brief Template assign operator.
     1522      ///
     1523      /// The given parameter should be conform to the ReadMap
     1524      /// concept and could be indiced by the current item set of
     1525      /// the ANodeMap. In this case the value for each item
     1526      /// is assigned by the value of the given ReadMap.
     1527      template <typename CMap>
     1528      ANodeMap& operator=(const CMap& cmap) {
     1529        checkConcept<concept::ReadMap<ANode, _Value>, CMap>();
     1530        const typename Parent::Graph* graph = Parent::getGraph();
     1531        ANode it;
     1532        for (graph->first(it); it != INVALID; graph->next(it)) {
     1533          Parent::set(it, cmap[it]);
     1534        }
     1535        return *this;
     1536      }
     1537   
     1538    };
     1539
     1540    template <typename _Value>
     1541    class BNodeMap
     1542      : public IterableMapExtender<DefaultMap<Graph, BNode, _Value> > {
     1543    public:
     1544      typedef BpUGraphExtender Graph;
     1545      typedef IterableMapExtender<DefaultMap<Graph, BNode, _Value> >
     1546      Parent;
     1547   
     1548      BNodeMap(const Graph& _g)
     1549        : Parent(_g) {}
     1550      BNodeMap(const Graph& _g, const _Value& _v)
     1551        : Parent(_g, _v) {}
     1552   
     1553      BNodeMap& operator=(const BNodeMap& cmap) {
     1554        return operator=<BNodeMap>(cmap);
     1555      }
     1556   
     1557
     1558      /// \brief Template assign operator.
     1559      ///
     1560      /// The given parameter should be conform to the ReadMap
     1561      /// concept and could be indiced by the current item set of
     1562      /// the BNodeMap. In this case the value for each item
     1563      /// is assigned by the value of the given ReadMap.
     1564      template <typename CMap>
     1565      BNodeMap& operator=(const CMap& cmap) {
     1566        checkConcept<concept::ReadMap<BNode, _Value>, CMap>();
     1567        const typename Parent::Graph* graph = Parent::getGraph();
     1568        BNode it;
     1569        for (graph->first(it); it != INVALID; graph->next(it)) {
     1570          Parent::set(it, cmap[it]);
     1571        }
     1572        return *this;
     1573      }
     1574   
     1575    };
     1576
     1577  protected:
     1578
     1579    template <typename _Value>
     1580    class NodeMapBase : public NodeNotifier::ObserverBase {
     1581    public:
     1582      typedef BpUGraphExtender Graph;
     1583
     1584      typedef Node Key;
     1585      typedef _Value Value;
     1586
     1587      /// The reference type of the map;
     1588      typedef typename BNodeMap<_Value>::Reference Reference;
     1589      /// The pointer type of the map;
     1590      typedef typename BNodeMap<_Value>::Pointer Pointer;
     1591     
     1592      /// The const value type of the map.
     1593      typedef const Value ConstValue;
     1594      /// The const reference type of the map;
     1595      typedef typename BNodeMap<_Value>::ConstReference ConstReference;
     1596      /// The pointer type of the map;
     1597      typedef typename BNodeMap<_Value>::ConstPointer ConstPointer;
     1598
     1599      typedef True ReferenceMapTag;
     1600
     1601      NodeMapBase(const Graph& _g)
     1602        : graph(&_g), bNodeMap(_g), aNodeMap(_g) {
     1603        NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
     1604      }
     1605      NodeMapBase(const Graph& _g, const _Value& _v)
     1606        : graph(&_g), bNodeMap(_g, _v),
     1607          aNodeMap(_g, _v) {
     1608        NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
     1609      }
     1610
     1611      virtual ~NodeMapBase() {     
     1612        if (NodeNotifier::ObserverBase::attached()) {
     1613          NodeNotifier::ObserverBase::detach();
     1614        }
     1615      }
     1616   
     1617      ConstReference operator[](const Key& node) const {
     1618        if (Parent::aNode(node)) {
     1619          return aNodeMap[node];
     1620        } else {
     1621          return bNodeMap[node];
     1622        }
     1623      }
     1624
     1625      Reference operator[](const Key& node) {
     1626        if (Parent::aNode(node)) {
     1627          return aNodeMap[node];
     1628        } else {
     1629          return bNodeMap[node];
     1630        }
     1631      }
     1632
     1633      void set(const Key& node, const Value& value) {
     1634        if (Parent::aNode(node)) {
     1635          aNodeMap.set(node, value);
     1636        } else {
     1637          bNodeMap.set(node, value);
     1638        }
     1639      }
     1640
     1641    protected:
     1642     
     1643      virtual void add(const Node&) {}
     1644      virtual void add(const std::vector<Node>&) {}
     1645      virtual void erase(const Node&) {}
     1646      virtual void erase(const std::vector<Node>&) {}
     1647      virtual void clear() {}
     1648      virtual void build() {}
     1649
     1650      const Graph* getGraph() const { return graph; }
     1651     
     1652    private:
     1653      const Graph* graph;
     1654      BNodeMap<_Value> bNodeMap;
     1655      ANodeMap<_Value> aNodeMap;
     1656    };
     1657   
     1658  public:
     1659
     1660    template <typename _Value>
     1661    class NodeMap
     1662      : public IterableMapExtender<NodeMapBase<_Value> > {
     1663    public:
     1664      typedef BpUGraphExtender Graph;
     1665      typedef IterableMapExtender< NodeMapBase<_Value> > Parent;
     1666   
     1667      NodeMap(const Graph& _g)
     1668        : Parent(_g) {}
     1669      NodeMap(const Graph& _g, const _Value& _v)
     1670        : Parent(_g, _v) {}
     1671   
     1672      NodeMap& operator=(const NodeMap& cmap) {
     1673        return operator=<NodeMap>(cmap);
     1674      }
     1675   
     1676
     1677      /// \brief Template assign operator.
     1678      ///
     1679      /// The given parameter should be conform to the ReadMap
     1680      /// concept and could be indiced by the current item set of
     1681      /// the NodeMap. In this case the value for each item
     1682      /// is assigned by the value of the given ReadMap.
     1683      template <typename CMap>
     1684      NodeMap& operator=(const CMap& cmap) {
     1685        checkConcept<concept::ReadMap<Node, _Value>, CMap>();
     1686        const typename Parent::Graph* graph = Parent::getGraph();
     1687        Node it;
     1688        for (graph->first(it); it != INVALID; graph->next(it)) {
     1689          Parent::set(it, cmap[it]);
     1690        }
     1691        return *this;
     1692      }
     1693   
     1694    };
     1695
     1696
     1697
     1698    template <typename _Value>
     1699    class EdgeMap
     1700      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
     1701    public:
     1702      typedef BpUGraphExtender Graph;
     1703      typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
     1704   
     1705      EdgeMap(const Graph& _g)
     1706        : Parent(_g) {}
     1707      EdgeMap(const Graph& _g, const _Value& _v)
     1708        : Parent(_g, _v) {}
     1709   
     1710      EdgeMap& operator=(const EdgeMap& cmap) {
     1711        return operator=<EdgeMap>(cmap);
     1712      }
     1713   
     1714      template <typename CMap>
     1715      EdgeMap& operator=(const CMap& cmap) {
     1716        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
     1717        const typename Parent::Graph* graph = Parent::getGraph();
     1718        Edge it;
     1719        for (graph->first(it); it != INVALID; graph->next(it)) {
     1720          Parent::set(it, cmap[it]);
     1721        }
     1722        return *this;
     1723      }
     1724    };
     1725
     1726    template <typename _Value>
     1727    class UEdgeMap
     1728      : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
     1729    public:
     1730      typedef BpUGraphExtender Graph;
     1731      typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> >
     1732      Parent;
     1733   
     1734      UEdgeMap(const Graph& _g)
     1735        : Parent(_g) {}
     1736      UEdgeMap(const Graph& _g, const _Value& _v)
     1737        : Parent(_g, _v) {}
     1738   
     1739      UEdgeMap& operator=(const UEdgeMap& cmap) {
     1740        return operator=<UEdgeMap>(cmap);
     1741      }
     1742   
     1743      template <typename CMap>
     1744      UEdgeMap& operator=(const CMap& cmap) {
     1745        checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
     1746        const typename Parent::Graph* graph = Parent::getGraph();
     1747        UEdge it;
     1748        for (graph->first(it); it != INVALID; graph->next(it)) {
     1749          Parent::set(it, cmap[it]);
     1750        }
     1751        return *this;
     1752      }
     1753    };
     1754
     1755 
     1756    Node addANode() {
     1757      Node node = Parent::addANode();
     1758      getNotifier(ANode()).add(node);
     1759      getNotifier(Node()).add(node);
     1760      return node;
     1761    }
     1762
     1763    Node addBNode() {
     1764      Node node = Parent::addBNode();
     1765      getNotifier(BNode()).add(node);
     1766      getNotifier(Node()).add(node);
     1767      return node;
     1768    }
     1769 
     1770    UEdge addEdge(const Node& source, const Node& target) {
     1771      UEdge uedge = Parent::addEdge(source, target);
     1772      getNotifier(UEdge()).add(uedge);
     1773   
     1774      std::vector<Edge> edges;
     1775      edges.push_back(direct(uedge, true));
     1776      edges.push_back(direct(uedge, false));
     1777      getNotifier(Edge()).add(edges);
     1778   
     1779      return uedge;
     1780    }
     1781
     1782    void clear() {
     1783      getNotifier(Edge()).clear();
     1784      getNotifier(UEdge()).clear();
     1785      getNotifier(Node()).clear();
     1786      getNotifier(BNode()).clear();
     1787      getNotifier(ANode()).clear();
     1788      Parent::clear();
     1789    }
     1790
     1791    void erase(const Node& node) {
     1792      UEdge uedge;
     1793      bool dir;
     1794      Parent::firstInc(uedge, dir, node);
     1795      while (uedge != INVALID ) {
     1796        erase(uedge);
     1797        Parent::firstInc(uedge, dir, node);
     1798      }
     1799
     1800      getNotifier(Node()).erase(node);
     1801      Parent::erase(node);
     1802    }
     1803   
     1804    void erase(const UEdge& uedge) {
     1805      std::vector<Edge> edges;
     1806      edges.push_back(direct(uedge, true));
     1807      edges.push_back(direct(uedge, false));
     1808      getNotifier(Edge()).erase(edges);
     1809      getNotifier(UEdge()).erase(uedge);
     1810      Parent::erase(uedge);
     1811    }
     1812
     1813
     1814    ~BpUGraphExtender() {
     1815      getNotifier(Edge()).clear();
     1816      getNotifier(UEdge()).clear();
     1817      getNotifier(Node()).clear();
     1818      getNotifier(BNode()).clear();
     1819      getNotifier(ANode()).clear();
     1820    }
     1821
    6161822
    6171823  };
  • lemon/bits/static_map.h

    r1961 r1979  
    5757  public:
    5858
    59     /// \brief Exception class for unsinported exceptions.
    60     class UnsinportedOperation : public lemon::LogicError {
     59    /// \brief Exception class for unsupported exceptions.
     60    class UnsupportedOperation : public lemon::LogicError {
    6161    public:
    6262      virtual const char* exceptionName() const {
    63         return "lemon::StaticMap::UnsinportedOperation";
     63        return "lemon::StaticMap::UnsupportedOperation";
    6464      }
    6565    };
     
    188188     
    189189    void add(const Key&) {
    190       throw UnsinportedOperation();
     190      throw UnsupportedOperation();
    191191    }
    192192
     
    196196    /// and it overrides the erase() member function of the observer base.     
    197197    void erase(const Key&) {
    198       throw UnsinportedOperation();
     198      throw UnsupportedOperation();
    199199    }
    200200
     
    225225  };
    226226
    227   /// \e
    228   template <typename _Base>
    229   class StaticMappableGraphExtender : public _Base {
    230   public:
    231 
    232     typedef StaticMappableGraphExtender<_Base> Graph;
    233     typedef _Base Parent;
    234 
    235     typedef typename Parent::Node Node;
    236     typedef typename Parent::NodeIt NodeIt;
    237 
    238     typedef typename Parent::Edge Edge;
    239     typedef typename Parent::EdgeIt EdgeIt;
    240 
    241    
    242     template <typename _Value>
    243     class NodeMap
    244       : public IterableMapExtender<StaticMap<Graph, Node, _Value> > {
    245     public:
    246       typedef StaticMappableGraphExtender Graph;
    247       typedef IterableMapExtender<StaticMap<Graph, Node, _Value> > Parent;
    248 
    249       NodeMap(const Graph& _g)
    250         : Parent(_g) {}
    251       NodeMap(const Graph& _g, const _Value& _v)
    252         : Parent(_g, _v) {}
    253 
    254       NodeMap& operator=(const NodeMap& cmap) {
    255         return operator=<NodeMap>(cmap);
    256       }
    257 
    258 
    259       /// \brief Template assign operator.
    260       ///
    261       /// The given parameter should be conform to the ReadMap
    262       /// concecpt and could be indiced by the current item set of
    263       /// the NodeMap. In this case the value for each item
    264       /// is assigned by the value of the given ReadMap.
    265       template <typename CMap>
    266       NodeMap& operator=(const CMap& cmap) {
    267         checkConcept<concept::ReadMap<Node, _Value>, CMap>();
    268         const typename Parent::Graph* graph = Parent::getGraph();
    269         Node it;
    270         for (graph->first(it); it != INVALID; graph->next(it)) {
    271           Parent::set(it, cmap[it]);
    272         }
    273         return *this;
    274       }
    275 
    276     };
    277 
    278     template <typename _Value>
    279     class EdgeMap
    280       : public IterableMapExtender<StaticMap<Graph, Edge, _Value> > {
    281     public:
    282       typedef StaticMappableGraphExtender Graph;
    283       typedef IterableMapExtender<StaticMap<Graph, Edge, _Value> > Parent;
    284 
    285       EdgeMap(const Graph& _g)
    286         : Parent(_g) {}
    287       EdgeMap(const Graph& _g, const _Value& _v)
    288         : Parent(_g, _v) {}
    289 
    290       EdgeMap& operator=(const EdgeMap& cmap) {
    291         return operator=<EdgeMap>(cmap);
    292       }
    293 
    294       template <typename CMap>
    295       EdgeMap& operator=(const CMap& cmap) {
    296         checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
    297         const typename Parent::Graph* graph = Parent::getGraph();
    298         Edge it;
    299         for (graph->first(it); it != INVALID; graph->next(it)) {
    300           Parent::set(it, cmap[it]);
    301         }
    302         return *this;
    303       }
    304     };
    305    
    306   };
    307 
    308   /// \e
    309   template <typename _Base>
    310   class StaticMappableUGraphExtender :
    311     public StaticMappableGraphExtender<_Base> {
    312   public:
    313 
    314     typedef StaticMappableUGraphExtender Graph;
    315     typedef StaticMappableGraphExtender<_Base> Parent;
    316 
    317     typedef typename Parent::UEdge UEdge;
    318 
    319     template <typename _Value>
    320     class UEdgeMap
    321       : public IterableMapExtender<StaticMap<Graph, UEdge, _Value> > {
    322     public:
    323       typedef StaticMappableUGraphExtender Graph;
    324       typedef IterableMapExtender<
    325         StaticMap<Graph, UEdge, _Value> > Parent;
    326 
    327       UEdgeMap(const Graph& _g)
    328         : Parent(_g) {}
    329       UEdgeMap(const Graph& _g, const _Value& _v)
    330         : Parent(_g, _v) {}
    331 
    332       UEdgeMap& operator=(const UEdgeMap& cmap) {
    333         return operator=<UEdgeMap>(cmap);
    334       }
    335 
    336       template <typename CMap>
    337       UEdgeMap& operator=(const CMap& cmap) {
    338         checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
    339         const typename Parent::Graph* graph = Parent::getGraph();
    340         UEdge it;
    341         for (graph->first(it); it != INVALID; graph->next(it)) {
    342           Parent::set(it, cmap[it]);
    343         }
    344         return *this;
    345       }
    346     };
    347 
    348   };
    349 
    350   template <typename _Base>
    351   class StaticMappableBpUGraphExtender : public _Base {
    352   public:
    353 
    354     typedef _Base Parent;
    355     typedef StaticMappableBpUGraphExtender Graph;
    356 
    357     typedef typename Parent::Node Node;
    358     typedef typename Parent::ANode ANode;
    359     typedef typename Parent::BNode BNode;
    360     typedef typename Parent::Edge Edge;
    361     typedef typename Parent::UEdge UEdge;
    362    
    363     template <typename _Value>
    364     class ANodeMap
    365       : public IterableMapExtender<StaticMap<Graph, ANode, _Value> > {
    366     public:
    367       typedef StaticMappableBpUGraphExtender Graph;
    368       typedef IterableMapExtender<StaticMap<Graph, ANode, _Value> >
    369       Parent;
    370    
    371       ANodeMap(const Graph& _g)
    372         : Parent(_g) {}
    373       ANodeMap(const Graph& _g, const _Value& _v)
    374         : Parent(_g, _v) {}
    375    
    376       ANodeMap& operator=(const ANodeMap& cmap) {
    377         return operator=<ANodeMap>(cmap);
    378       }
    379    
    380 
    381       /// \brief Template assign operator.
    382       ///
    383       /// The given parameter should be conform to the ReadMap
    384       /// concept and could be indiced by the current item set of
    385       /// the ANodeMap. In this case the value for each item
    386       /// is assigned by the value of the given ReadMap.
    387       template <typename CMap>
    388       ANodeMap& operator=(const CMap& cmap) {
    389         checkConcept<concept::ReadMap<ANode, _Value>, CMap>();
    390         const typename Parent::Graph* graph = Parent::getGraph();
    391         ANode it;
    392         for (graph->first(it); it != INVALID; graph->next(it)) {
    393           Parent::set(it, cmap[it]);
    394         }
    395         return *this;
    396       }
    397    
    398     };
    399 
    400     template <typename _Value>
    401     class BNodeMap
    402       : public IterableMapExtender<StaticMap<Graph, BNode, _Value> > {
    403     public:
    404       typedef StaticMappableBpUGraphExtender Graph;
    405       typedef IterableMapExtender<StaticMap<Graph, BNode, _Value> >
    406       Parent;
    407    
    408       BNodeMap(const Graph& _g)
    409         : Parent(_g) {}
    410       BNodeMap(const Graph& _g, const _Value& _v)
    411         : Parent(_g, _v) {}
    412    
    413       BNodeMap& operator=(const BNodeMap& cmap) {
    414         return operator=<BNodeMap>(cmap);
    415       }
    416    
    417 
    418       /// \brief Template assign operator.
    419       ///
    420       /// The given parameter should be conform to the ReadMap
    421       /// concept and could be indiced by the current item set of
    422       /// the BNodeMap. In this case the value for each item
    423       /// is assigned by the value of the given ReadMap.
    424       template <typename CMap>
    425       BNodeMap& operator=(const CMap& cmap) {
    426         checkConcept<concept::ReadMap<BNode, _Value>, CMap>();
    427         const typename Parent::Graph* graph = Parent::getGraph();
    428         BNode it;
    429         for (graph->first(it); it != INVALID; graph->next(it)) {
    430           Parent::set(it, cmap[it]);
    431         }
    432         return *this;
    433       }
    434    
    435     };
    436 
    437   protected:
    438 
    439     template <typename _Value>
    440     class NodeMapBase : public Parent::NodeNotifier::ObserverBase {
    441     public:
    442       typedef StaticMappableBpUGraphExtender Graph;
    443 
    444       typedef Node Key;
    445       typedef _Value Value;
    446 
    447       /// The reference type of the map;
    448       typedef typename BNodeMap<_Value>::Reference Reference;
    449       /// The pointer type of the map;
    450       typedef typename BNodeMap<_Value>::Pointer Pointer;
    451      
    452       /// The const value type of the map.
    453       typedef const Value ConstValue;
    454       /// The const reference type of the map;
    455       typedef typename BNodeMap<_Value>::ConstReference ConstReference;
    456       /// The pointer type of the map;
    457       typedef typename BNodeMap<_Value>::ConstPointer ConstPointer;
    458 
    459       typedef True ReferenceMapTag;
    460 
    461       NodeMapBase(const Graph& _g)
    462         : graph(&_g), bNodeMap(_g), aNodeMap(_g) {
    463         Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
    464       }
    465       NodeMapBase(const Graph& _g, const _Value& _v)
    466         : graph(&_g), bNodeMap(_g, _v),
    467           aNodeMap(_g, _v) {
    468         Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
    469       }
    470 
    471       virtual ~NodeMapBase() {     
    472         if (Parent::NodeNotifier::ObserverBase::attached()) {
    473           Parent::NodeNotifier::ObserverBase::detach();
    474         }
    475       }
    476    
    477       ConstReference operator[](const Key& node) const {
    478         if (Parent::aNode(node)) {
    479           return aNodeMap[node];
    480         } else {
    481           return bNodeMap[node];
    482         }
    483       }
    484 
    485       Reference operator[](const Key& node) {
    486         if (Parent::aNode(node)) {
    487           return aNodeMap[node];
    488         } else {
    489           return bNodeMap[node];
    490         }
    491       }
    492 
    493       void set(const Key& node, const Value& value) {
    494         if (Parent::aNode(node)) {
    495           aNodeMap.set(node, value);
    496         } else {
    497           bNodeMap.set(node, value);
    498         }
    499       }
    500 
    501     protected:
    502      
    503       virtual void add(const Node&) {}
    504       virtual void add(const std::vector<Node>&) {}
    505       virtual void erase(const Node&) {}
    506       virtual void erase(const std::vector<Node>&) {}
    507       virtual void clear() {}
    508       virtual void build() {}
    509 
    510       const Graph* getGraph() const { return graph; }
    511      
    512     private:
    513       const Graph* graph;
    514       BNodeMap<_Value> bNodeMap;
    515       ANodeMap<_Value> aNodeMap;
    516     };
    517    
    518   public:
    519 
    520     template <typename _Value>
    521     class NodeMap
    522       : public IterableMapExtender<NodeMapBase<_Value> > {
    523     public:
    524       typedef StaticMappableBpUGraphExtender Graph;
    525       typedef IterableMapExtender< NodeMapBase<_Value> > Parent;
    526    
    527       NodeMap(const Graph& _g)
    528         : Parent(_g) {}
    529       NodeMap(const Graph& _g, const _Value& _v)
    530         : Parent(_g, _v) {}
    531    
    532       NodeMap& operator=(const NodeMap& cmap) {
    533         return operator=<NodeMap>(cmap);
    534       }
    535    
    536 
    537       /// \brief Template assign operator.
    538       ///
    539       /// The given parameter should be conform to the ReadMap
    540       /// concept and could be indiced by the current item set of
    541       /// the NodeMap. In this case the value for each item
    542       /// is assigned by the value of the given ReadMap.
    543       template <typename CMap>
    544       NodeMap& operator=(const CMap& cmap) {
    545         checkConcept<concept::ReadMap<Node, _Value>, CMap>();
    546         const typename Parent::Graph* graph = Parent::getGraph();
    547         Node it;
    548         for (graph->first(it); it != INVALID; graph->next(it)) {
    549           Parent::set(it, cmap[it]);
    550         }
    551         return *this;
    552       }
    553    
    554     };
    555 
    556 
    557 
    558     template <typename _Value>
    559     class EdgeMap
    560       : public IterableMapExtender<StaticMap<Graph, Edge, _Value> > {
    561     public:
    562       typedef StaticMappableBpUGraphExtender Graph;
    563       typedef IterableMapExtender<StaticMap<Graph, Edge, _Value> > Parent;
    564    
    565       EdgeMap(const Graph& _g)
    566         : Parent(_g) {}
    567       EdgeMap(const Graph& _g, const _Value& _v)
    568         : Parent(_g, _v) {}
    569    
    570       EdgeMap& operator=(const EdgeMap& cmap) {
    571         return operator=<EdgeMap>(cmap);
    572       }
    573    
    574       template <typename CMap>
    575       EdgeMap& operator=(const CMap& cmap) {
    576         checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
    577         const typename Parent::Graph* graph = Parent::getGraph();
    578         Edge it;
    579         for (graph->first(it); it != INVALID; graph->next(it)) {
    580           Parent::set(it, cmap[it]);
    581         }
    582         return *this;
    583       }
    584     };
    585 
    586     template <typename _Value>
    587     class UEdgeMap
    588       : public IterableMapExtender<StaticMap<Graph, UEdge, _Value> > {
    589     public:
    590       typedef StaticMappableBpUGraphExtender Graph;
    591       typedef IterableMapExtender<StaticMap<Graph, UEdge, _Value> >
    592       Parent;
    593    
    594       UEdgeMap(const Graph& _g)
    595         : Parent(_g) {}
    596       UEdgeMap(const Graph& _g, const _Value& _v)
    597         : Parent(_g, _v) {}
    598    
    599       UEdgeMap& operator=(const UEdgeMap& cmap) {
    600         return operator=<UEdgeMap>(cmap);
    601       }
    602    
    603       template <typename CMap>
    604       UEdgeMap& operator=(const CMap& cmap) {
    605         checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
    606         const typename Parent::Graph* graph = Parent::getGraph();
    607         UEdge it;
    608         for (graph->first(it); it != INVALID; graph->next(it)) {
    609           Parent::set(it, cmap[it]);
    610         }
    611         return *this;
    612       }
    613     };
    614  
    615   };
    616 
    617227}
    618228
  • lemon/concept/bpugraph.h

    r1956 r1979  
    7171      /// \todo undocumented
    7272      ///
    73       typedef True UTag;
     73      typedef True UndirectedTag;
    7474
    7575      /// \brief The base type of node iterators,
  • lemon/concept/graph.h

    r1956 r1979  
    4545    public:
    4646
    47       typedef False UTag;
    48      
    4947      typedef BaseGraphComponent::Node Node;
    5048      typedef BaseGraphComponent::Edge Edge;
     
    124122      ///\e
    125123
    126       ///\todo undocumented
    127       ///
    128       typedef False UTag;
    129 
    130124      /// Defalult constructor.
    131125
  • lemon/concept/ugraph.h

    r1956 r1979  
    246246      ///\todo undocumented
    247247      ///
    248       typedef True UTag;
     248      typedef True UndirectedTag;
    249249
    250250      /// \brief The base type of node iterators,
  • lemon/edge_set.h

    r1962 r1979  
    2020#define LEMON_EDGE_SET_H
    2121
    22 #include <lemon/bits/erasable_graph_extender.h>
    23 #include <lemon/bits/clearable_graph_extender.h>
    24 #include <lemon/bits/extendable_graph_extender.h>
    25 #include <lemon/bits/iterable_graph_extender.h>
    26 #include <lemon/bits/alteration_notifier.h>
    27 #include <lemon/bits/default_map.h>
    28 #include <lemon/bits/graph_extender.h>
     22
     23#include <lemon/bits/edge_set_extender.h>
    2924
    3025/// \ingroup graphs
     
    230225  /// \ref concept::ErasableGraph "ErasableGraph" concept.
    231226  template <typename _Graph>
    232   class ListEdgeSet :
    233     public ErasableEdgeSetExtender<
    234     ClearableEdgeSetExtender<
    235     ExtendableEdgeSetExtender<
    236     MappableEdgeSetExtender<
    237     IterableGraphExtender<
    238     AlterableEdgeSetExtender<
    239     GraphExtender<
    240     ListEdgeSetBase<_Graph> > > > > > > > {
    241 
    242   public:
    243 
    244     typedef ErasableEdgeSetExtender<
    245       ClearableEdgeSetExtender<
    246       ExtendableEdgeSetExtender<
    247       MappableEdgeSetExtender<
    248       IterableGraphExtender<
    249       AlterableEdgeSetExtender<
    250       GraphExtender<
    251       ListEdgeSetBase<_Graph> > > > > > > > Parent;
     227  class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
     228
     229  public:
     230
     231    typedef EdgeSetExtender<ListEdgeSetBase<_Graph> > Parent;
    252232   
    253233    typedef typename Parent::Node Node;
     
    337317  /// \ref concept::ErasableUGraph "ErasableUGraph" concept.
    338318  template <typename _Graph>
    339   class ListUEdgeSet :
    340     public ErasableUEdgeSetExtender<
    341     ClearableUEdgeSetExtender<
    342     ExtendableUEdgeSetExtender<
    343     MappableUEdgeSetExtender<
    344     IterableUGraphExtender<
    345     AlterableUEdgeSetExtender<
    346     UGraphExtender<
    347     ListEdgeSetBase<_Graph> > > > > > > > {
    348 
    349   public:
    350 
    351     typedef ErasableUEdgeSetExtender<
    352       ClearableUEdgeSetExtender<
    353       ExtendableUEdgeSetExtender<
    354       MappableUEdgeSetExtender<
    355       IterableUGraphExtender<
    356       AlterableUEdgeSetExtender<
    357       UGraphExtender<
    358       ListEdgeSetBase<_Graph> > > > > > > > Parent;
     319  class ListUEdgeSet
     320    : public UEdgeSetExtender<UGraphBaseExtender<ListEdgeSetBase<_Graph> > > {
     321
     322  public:
     323
     324    typedef UEdgeSetExtender<UGraphBaseExtender<
     325      ListEdgeSetBase<_Graph> > > Parent;
    359326   
    360327    typedef typename Parent::Node Node;
     
    568535  /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
    569536  template <typename _Graph>
    570   class SmartEdgeSet :
    571     public ClearableEdgeSetExtender<
    572     ExtendableEdgeSetExtender<
    573     MappableEdgeSetExtender<
    574     IterableGraphExtender<
    575     AlterableEdgeSetExtender<
    576     GraphExtender<
    577     SmartEdgeSetBase<_Graph> > > > > > > {
    578 
    579   public:
    580 
    581     typedef ClearableEdgeSetExtender<
    582       ExtendableEdgeSetExtender<
    583       MappableEdgeSetExtender<
    584       IterableGraphExtender<
    585       AlterableEdgeSetExtender<
    586       GraphExtender<
    587       SmartEdgeSetBase<_Graph> > > > > > > Parent;
     537  class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {
     538
     539  public:
     540
     541    typedef EdgeSetExtender<SmartEdgeSetBase<_Graph> > Parent;
    588542   
    589543    typedef typename Parent::Node Node;
     
    672626  /// \ref concept::ExtendableUGraph "ExtendableUGraph" concept.
    673627  template <typename _Graph>
    674   class SmartUEdgeSet :
    675     public ClearableUEdgeSetExtender<
    676     ExtendableUEdgeSetExtender<
    677     MappableUEdgeSetExtender<
    678     IterableUGraphExtender<
    679     AlterableUEdgeSetExtender<
    680     UGraphExtender<
    681     SmartEdgeSetBase<_Graph> > > > > > > {
    682 
    683   public:
    684 
    685     typedef ClearableUEdgeSetExtender<
    686       ExtendableUEdgeSetExtender<
    687       MappableUEdgeSetExtender<
    688       IterableUGraphExtender<
    689       AlterableUEdgeSetExtender<
    690       UGraphExtender<
    691       SmartEdgeSetBase<_Graph> > > > > > > Parent;
     628  class SmartUEdgeSet
     629    : public UEdgeSetExtender<UGraphBaseExtender<SmartEdgeSetBase<_Graph> > > {
     630
     631  public:
     632
     633    typedef UEdgeSetExtender<UGraphBaseExtender<
     634      SmartEdgeSetBase<_Graph> > > Parent;
    692635   
    693636    typedef typename Parent::Node Node;
  • lemon/euler.h

    r1970 r1979  
    234234  bool
    235235#else
    236   typename enable_if<typename Graph::UTag,bool>::type
     236  typename enable_if<UndirectedTagIndicator<Graph>,bool>::type
    237237  euler(const Graph &g)
    238238  {
     
    242242  }
    243243  template<class Graph>
    244   typename disable_if<typename Graph::UTag,bool>::type
     244  typename disable_if<UndirectedTagIndicator<Graph>,bool>::type
    245245#endif
    246246  euler(const Graph &g)
  • lemon/fredman_tarjan.h

    r1956 r1979  
    505505    ft.treeMap(tree);
    506506    ft.run();
    507   };
     507  }
    508508
    509509} //END OF NAMESPACE LEMON
  • lemon/full_graph.h

    r1956 r1979  
    2323
    2424
    25 #include <lemon/bits/iterable_graph_extender.h>
    26 #include <lemon/bits/alteration_notifier.h>
    27 #include <lemon/bits/static_map.h>
    2825#include <lemon/bits/graph_extender.h>
     26
    2927
    3028#include <lemon/invalid.h>
     
    192190  };
    193191
    194   typedef StaticMappableGraphExtender<
    195     IterableGraphExtender<
    196     AlterableGraphExtender<
    197     GraphExtender<FullGraphBase> > > > ExtendedFullGraphBase;
     192  typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
    198193
    199194  /// \ingroup graphs
     
    212207  public:
    213208
     209    typedef ExtendedFullGraphBase Parent;
     210
     211    /// \brief Constructor
     212    ///
    214213    FullGraph(int n) { construct(n); }
     214
     215    /// \brief Resize the graph
     216    ///
     217    void resize(int n) {
     218      Parent::getNotifier(Edge()).clear();
     219      Parent::getNotifier(Node()).clear();
     220      construct(n);
     221      Parent::getNotifier(Node()).build();
     222      Parent::getNotifier(Edge()).build();
     223    }
    215224  };
    216225
     
    380389  };
    381390
    382   typedef StaticMappableUGraphExtender<
    383     IterableUGraphExtender<
    384     AlterableUGraphExtender<
    385     UGraphExtender<FullUGraphBase> > > > ExtendedFullUGraphBase;
     391  typedef UGraphExtender<UGraphBaseExtender<FullUGraphBase> >
     392  ExtendedFullUGraphBase;
    386393
    387394  /// \ingroup graphs
     
    402409  class FullUGraph : public ExtendedFullUGraphBase {
    403410  public:
     411
     412    typedef ExtendedFullUGraphBase Parent;
     413
     414    /// \brief Constructor
    404415    FullUGraph(int n) { construct(n); }
     416
     417    /// \brief Resize the graph
     418    ///
     419    void resize(int n) {
     420      Parent::getNotifier(Edge()).clear();
     421      Parent::getNotifier(UEdge()).clear();
     422      Parent::getNotifier(Node()).clear();
     423      construct(n);
     424      Parent::getNotifier(Node()).build();
     425      Parent::getNotifier(UEdge()).build();
     426      Parent::getNotifier(Edge()).build();
     427    }
    405428  };
    406429
     
    578601
    579602
    580   typedef StaticMappableBpUGraphExtender<
    581     IterableBpUGraphExtender<
    582     AlterableBpUGraphExtender<
    583     BpUGraphExtender <
    584     FullBpUGraphBase> > > >
    585   ExtendedFullBpUGraphBase;
     603  typedef BpUGraphExtender< BpUGraphBaseExtender<
     604    FullBpUGraphBase> > ExtendedFullBpUGraphBase;
    586605
    587606
     
    600619    public ExtendedFullBpUGraphBase {
    601620  public:
     621
    602622    typedef ExtendedFullBpUGraphBase Parent;
     623
    603624    FullBpUGraph(int aNodeNum, int bNodeNum) {
    604625      Parent::construct(aNodeNum, bNodeNum);
    605626    }
     627    /// \brief Resize the graph
     628    ///
     629    void resize(int n, int m) {
     630      Parent::getNotifier(Edge()).clear();
     631      Parent::getNotifier(UEdge()).clear();
     632      Parent::getNotifier(Node()).clear();
     633      construct(n, m);
     634      Parent::getNotifier(Node()).build();
     635      Parent::getNotifier(UEdge()).build();
     636      Parent::getNotifier(Edge()).build();
     637    }
    606638  };
    607639
  • lemon/graph_adaptor.h

    r1957 r1979  
    3030#include <lemon/invalid.h>
    3131#include <lemon/maps.h>
    32 #include <lemon/bits/erasable_graph_extender.h>
    33 #include <lemon/bits/clearable_graph_extender.h>
    34 #include <lemon/bits/extendable_graph_extender.h>
    35 #include <lemon/bits/iterable_graph_extender.h>
    36 #include <lemon/bits/alteration_notifier.h>
    37 #include <lemon/bits/default_map.h>
     32
     33#include <lemon/bits/graph_adaptor_extender.h>
    3834#include <lemon/bits/graph_extender.h>
     35
    3936#include <iostream>
    4037
     
    118115    int id(const Edge& e) const { return graph->id(e); }
    119116   
    120     Edge oppositeNode(const Edge& e) const {
    121       return Edge(graph->opposite(e));
    122     }
    123 
    124117    template <typename _Value>
    125118    class NodeMap : public _Graph::template NodeMap<_Value> {
     
    146139  template <typename _Graph>
    147140  class GraphAdaptor :
    148     public IterableGraphExtender<GraphAdaptorBase<_Graph> > {
     141    public GraphAdaptorExtender<GraphAdaptorBase<_Graph> > {
    149142  public:
    150143    typedef _Graph Graph;
    151     typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
     144    typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;
    152145  protected:
    153146    GraphAdaptor() : Parent() { }
     
    199192  template<typename _Graph>
    200193  class RevGraphAdaptor :
    201     public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
     194    public GraphAdaptorExtender<RevGraphAdaptorBase<_Graph> > {
    202195  public:
    203196    typedef _Graph Graph;
    204     typedef IterableGraphExtender<
     197    typedef GraphAdaptorExtender<
    205198      RevGraphAdaptorBase<_Graph> > Parent;
    206199  protected:
     
    323316    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
    324317
     318    typedef False FindEdgeTag;
    325319    typedef False NodeNumTag;
    326320    typedef False EdgeNumTag;
     
    429423    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
    430424
     425    typedef False FindEdgeTag;
    431426    typedef False NodeNumTag;
    432427    typedef False EdgeNumTag;
     
    497492           typename EdgeFilterMap, bool checked = true>
    498493  class SubGraphAdaptor :
    499     public IterableGraphExtender<
     494    public GraphAdaptorExtender<
    500495    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
    501496  public:
    502497    typedef _Graph Graph;
    503     typedef IterableGraphExtender<
     498    typedef GraphAdaptorExtender<
    504499      SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
    505500  protected:
     
    704699
    705700  template <typename _Graph>
    706   class UGraphAdaptorBase :
    707     public UGraphExtender<GraphAdaptorBase<_Graph> > {
     701  class UndirectGraphAdaptorBase :
     702    public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
    708703  public:
    709704    typedef _Graph Graph;
    710     typedef UGraphExtender<GraphAdaptorBase<_Graph> > Parent;
     705    typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
    711706  protected:
    712     UGraphAdaptorBase() : Parent() { }
     707    UndirectGraphAdaptorBase() : Parent() { }
    713708  public:
    714709    typedef typename Parent::UEdge UEdge;
     
    718713    class EdgeMap {
    719714    protected:
    720       const UGraphAdaptorBase<_Graph>* g;
     715      const UndirectGraphAdaptorBase<_Graph>* g;
    721716      template <typename TT> friend class EdgeMap;
    722717      typename _Graph::template EdgeMap<T> forward_map, backward_map;
     
    725720      typedef Edge Key;
    726721     
    727       EdgeMap(const UGraphAdaptorBase<_Graph>& _g) : g(&_g),
     722      EdgeMap(const UndirectGraphAdaptorBase<_Graph>& _g) : g(&_g),
    728723        forward_map(*(g->graph)), backward_map(*(g->graph)) { }
    729724
    730       EdgeMap(const UGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
     725      EdgeMap(const UndirectGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
    731726        forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
    732727     
     
    754749      typedef UEdge Key;
    755750     
    756       UEdgeMap(const UGraphAdaptorBase<_Graph>& g) :
     751      UEdgeMap(const UndirectGraphAdaptorBase<_Graph>& g) :
    757752        map(*(g.graph)) { }
    758753
    759       UEdgeMap(const UGraphAdaptorBase<_Graph>& g, T a) :
     754      UEdgeMap(const UndirectGraphAdaptorBase<_Graph>& g, T a) :
    760755        map(*(g.graph), a) { }
    761756     
     
    779774  /// \author Marton Makai
    780775  template<typename _Graph>
    781   class UGraphAdaptor :
    782     public IterableUGraphExtender<
    783     UGraphAdaptorBase<_Graph> > {
     776  class UndirectGraphAdaptor :
     777    public UGraphAdaptorExtender<
     778    UndirectGraphAdaptorBase<_Graph> > {
    784779  public:
    785780    typedef _Graph Graph;
    786     typedef IterableUGraphExtender<
    787       UGraphAdaptorBase<_Graph> > Parent;
     781    typedef UGraphAdaptorExtender<
     782      UndirectGraphAdaptorBase<_Graph> > Parent;
    788783  protected:
    789     UGraphAdaptor() { }
    790   public:
    791     UGraphAdaptor(_Graph& _graph) {
     784    UndirectGraphAdaptor() { }
     785  public:
     786    UndirectGraphAdaptor(_Graph& _graph) {
    792787      setGraph(_graph);
    793788    }
     
    10841079           typename ForwardFilterMap, typename BackwardFilterMap>
    10851080  class SubBidirGraphAdaptor :
    1086     public IterableGraphExtender<
     1081    public GraphAdaptorExtender<
    10871082    SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
    10881083  public:
    10891084    typedef _Graph Graph;
    1090     typedef IterableGraphExtender<
     1085    typedef GraphAdaptorExtender<
    10911086      SubBidirGraphAdaptorBase<
    10921087      _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
     
    13421337  template <typename _Graph, typename FirstOutEdgesMap>
    13431338  class ErasingFirstGraphAdaptor :
    1344     public IterableGraphExtender<
     1339    public GraphAdaptorExtender<
    13451340    ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
    13461341  public:
    13471342    typedef _Graph Graph;
    1348     typedef IterableGraphExtender<
     1343    typedef GraphAdaptorExtender<
    13491344      ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
    13501345    ErasingFirstGraphAdaptor(Graph& _graph,
     
    17121707  template <typename _Graph>
    17131708  class SplitGraphAdaptor
    1714     : public IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > {
    1715   public:
    1716     typedef IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > Parent;
     1709    : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
     1710  public:
     1711    typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
    17171712
    17181713    SplitGraphAdaptor(_Graph& graph) {
  • lemon/hypercube_graph.h

    r1963 r1979  
    2626#include <lemon/error.h>
    2727
    28 #include <lemon/bits/iterable_graph_extender.h>
    29 #include <lemon/bits/alteration_notifier.h>
    30 #include <lemon/bits/static_map.h>
    3128#include <lemon/bits/graph_extender.h>
    3229
     
    237234
    238235
    239   typedef StaticMappableGraphExtender<
    240     IterableGraphExtender<
    241     AlterableGraphExtender<
    242     GraphExtender<
    243     HyperCubeGraphBase> > > > ExtendedHyperCubeGraphBase;
     236  typedef GraphExtender<HyperCubeGraphBase> ExtendedHyperCubeGraphBase;
    244237
    245238  /// \ingroup graphs
  • lemon/kruskal.h

    r1956 r1979  
    2424#include <lemon/unionfind.h>
    2525#include <lemon/utility.h>
     26#include <lemon/traits.h>
    2627
    2728/**
     
    229230
    230231    template<class _GR>
    231     typename enable_if<typename _GR::UTag,void>::type
     232    typename enable_if<UndirectedTagIndicator<_GR>,void>::type
    232233    fillWithEdges(const _GR& g, const Map& m,dummy<0> = 0)
    233234    {
     
    237238
    238239    template<class _GR>
    239     typename disable_if<typename _GR::UTag,void>::type
     240    typename disable_if<UndirectedTagIndicator<_GR>,void>::type
    240241    fillWithEdges(const _GR& g, const Map& m,dummy<1> = 1)
    241242    {
  • lemon/list_graph.h

    r1956 r1979  
    2424///\brief ListGraph, ListUGraph classes.
    2525
    26 #include <lemon/bits/erasable_graph_extender.h>
    27 #include <lemon/bits/clearable_graph_extender.h>
    28 #include <lemon/bits/extendable_graph_extender.h>
    29 #include <lemon/bits/iterable_graph_extender.h>
    30 #include <lemon/bits/alteration_notifier.h>
    31 #include <lemon/bits/default_map.h>
    3226#include <lemon/bits/graph_extender.h>
    3327
    3428#include <lemon/error.h>
    3529
     30#include <vector>
    3631#include <list>
    3732
     
    312307  };
    313308
    314   typedef ErasableGraphExtender<
    315     ClearableGraphExtender<
    316     ExtendableGraphExtender<
    317     MappableGraphExtender<
    318     IterableGraphExtender<
    319     AlterableGraphExtender<
    320     GraphExtender<ListGraphBase> > > > > > > ExtendedListGraphBase;
     309  typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
    321310
    322311  /// \addtogroup graphs
     
    579568  /**************** Undirected List Graph ****************/
    580569
    581   typedef ErasableUGraphExtender<
    582     ClearableUGraphExtender<
    583     ExtendableUGraphExtender<
    584     MappableUGraphExtender<
    585     IterableUGraphExtender<
    586     AlterableUGraphExtender<
    587     UGraphExtender<ListGraphBase> > > > > > > ExtendedListUGraphBase;
     570  typedef UGraphExtender<UGraphBaseExtender<
     571    ListGraphBase> > ExtendedListUGraphBase;
    588572
    589573  /// \addtogroup graphs
  • lemon/prim.h

    r1956 r1979  
    789789    prm.treeMap(tree);
    790790    prm.run();
    791   };
     791  }
    792792
    793793} //END OF NAMESPACE LEMON
  • lemon/radix_sort.h

    r1956 r1979  
    265265    const int size =
    266266      (unsigned int)std::numeric_limits<unsigned char>::max() + 1;
    267     int counter[size];
     267    std::vector<int> counter(size);
    268268    for (int i = 0; i < size; ++i) {
    269269      counter[i] = 0;
     
    291291    const int size =
    292292      (unsigned int)std::numeric_limits<unsigned char>::max() + 1;
    293     int counter[size];
     293    std::vector<int> counter(size);
    294294    for (int i = 0; i < size; ++i) {
    295295      counter[i] = 0;
  • lemon/smart_graph.h

    r1956 r1979  
    2828#include <lemon/invalid.h>
    2929
    30 #include <lemon/bits/clearable_graph_extender.h>
    31 #include <lemon/bits/extendable_graph_extender.h>
    32 #include <lemon/bits/iterable_graph_extender.h>
    33 #include <lemon/bits/alteration_notifier.h>
    34 #include <lemon/bits/default_map.h>
    3530#include <lemon/bits/graph_extender.h>
    3631
    3732#include <lemon/utility.h>
    3833#include <lemon/error.h>
     34
     35#include <lemon/bits/graph_extender.h>
    3936
    4037namespace lemon {
     
    223220  };
    224221
    225   typedef ClearableGraphExtender<
    226     ExtendableGraphExtender<
    227     MappableGraphExtender<
    228     IterableGraphExtender<
    229     AlterableGraphExtender<
    230     GraphExtender<SmartGraphBase> > > > > > ExtendedSmartGraphBase;
     222  typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
    231223
    232224  /// \ingroup graphs
     
    245237  class SmartGraph : public ExtendedSmartGraphBase {
    246238  public:
    247    
     239
     240    typedef ExtendedSmartGraphBase Parent;
     241
    248242    class Snapshot;
    249243    friend class Snapshot;
     
    356350  /**************** Undirected List Graph ****************/
    357351
    358   typedef ClearableUGraphExtender<
    359     ExtendableUGraphExtender<
    360     MappableUGraphExtender<
    361     IterableUGraphExtender<
    362     AlterableUGraphExtender<
    363     UGraphExtender<SmartGraphBase> > > > > > ExtendedSmartUGraphBase;
     352  typedef UGraphExtender<UGraphBaseExtender<SmartGraphBase> >
     353  ExtendedSmartUGraphBase;
    364354
    365355  /// \ingroup graphs
     
    588578
    589579
    590   typedef ClearableBpUGraphExtender<
    591     ExtendableBpUGraphExtender<
    592     MappableBpUGraphExtender<
    593     IterableBpUGraphExtender<
    594     AlterableBpUGraphExtender<
    595     BpUGraphExtender <
    596     SmartBpUGraphBase> > > > > >
    597   ExtendedSmartBpUGraphBase;
     580  typedef BpUGraphExtender< BpUGraphBaseExtender<
     581    SmartBpUGraphBase> > ExtendedSmartBpUGraphBase;
    598582
    599583  /// \ingroup graphs
  • lemon/sub_graph.h

    r1964 r1979  
    387387  template <typename Graph>
    388388  class SubGraph
    389     : public IterableGraphExtender< SubGraphBase<Graph> > {
     389    : public GraphAdaptorExtender< SubGraphBase<Graph> > {
    390390  public:
    391     typedef IterableGraphExtender< SubGraphBase<Graph> > Parent;
     391    typedef GraphAdaptorExtender< SubGraphBase<Graph> > Parent;
    392392  public:
    393393    /// \brief Constructor for sub-graph.
     
    684684  template <typename Graph>
    685685  class EdgeSubGraph
    686     : public IterableGraphExtender< EdgeSubGraphBase<Graph> > {
     686    : public GraphAdaptorExtender< EdgeSubGraphBase<Graph> > {
    687687  public:
    688     typedef IterableGraphExtender< EdgeSubGraphBase<Graph> > Parent;
     688    typedef GraphAdaptorExtender< EdgeSubGraphBase<Graph> > Parent;
    689689  public:
    690690    /// \brief Constructor for sub-graph.
  • lemon/topology.h

    r1956 r1979  
    14181418    }
    14191419    return true;
    1420   };
     1420  }
    14211421 
    14221422  /// \ingroup topology
     
    14601460    }
    14611461    return true;
    1462   };
     1462  }
    14631463   
    14641464} //namespace lemon
  • lemon/traits.h

    r1956 r1979  
    210210  };
    211211
     212  template <typename Graph, typename Enable = void>
     213  struct UndirectedTagIndicator {
     214    static const bool value = false;
     215  };
     216
     217  template <typename Graph>
     218  struct UndirectedTagIndicator<
     219    Graph,
     220    typename enable_if<typename Graph::UndirectedTag, void>::type
     221  > {
     222    static const bool value = true;
     223  };
     224
    212225
    213226
  • test/graph_adaptor_test.cc

    r1956 r1979  
    6868
    6969    /// \bug why does not compile with StaticGraph
    70     checkConcept<BaseIterableUGraphConcept, UGraphAdaptor<ListGraph> >();
    71     checkConcept<IterableUGraphConcept, UGraphAdaptor<ListGraph> >();
    72     checkConcept<MappableUGraphConcept, UGraphAdaptor<ListGraph> >();
     70    checkConcept<UGraph, UndirectGraphAdaptor<ListGraph> >();
    7371  }
    7472  std::cout << __FILE__ ": All tests passed.\n";
  • test/ugraph_test.cc

    r1956 r1979  
    2222#include <lemon/smart_graph.h>
    2323#include <lemon/full_graph.h>
    24 #include <lemon/grid_graph.h>
     24#include <lemon/grid_ugraph.h>
    2525
    2626#include <lemon/graph_utils.h>
     
    3333
    3434void check_concepts() {
    35   typedef UGraphExtender<ListGraphBase> ListUGraphBase;
    36 
    37   typedef IterableUGraphExtender<
    38     AlterableUGraphExtender<ListUGraphBase> > IterableListUGraph;
    39 
    40   typedef MappableUGraphExtender<IterableListUGraph>
    41     MappableListUGraph;
    42 
    43   typedef ErasableUGraphExtender<
    44     ClearableUGraphExtender<
    45     ExtendableUGraphExtender<MappableListUGraph> > > Graph;
    46 
    47   checkConcept<BaseIterableUGraphConcept, Graph>();
    48   checkConcept<IterableUGraphConcept, Graph>();
    49   checkConcept<MappableUGraphConcept, Graph>();
    50 
    51   checkConcept<UGraph, Graph>();
    52   checkConcept<ErasableUGraph, Graph>();
    53 
    5435  checkConcept<UGraph, ListUGraph>();
    5536  checkConcept<ErasableUGraph, ListUGraph>();
     
    6243  checkConcept<UGraph, UGraph>();
    6344
    64   checkConcept<UGraph, GridGraph>();
     45  checkConcept<UGraph, GridUGraph>();
    6546}
    6647
     
    151132}
    152133
    153 void checkGridGraph(const GridGraph& g, int w, int h) {
     134void checkGridUGraph(const GridUGraph& g, int w, int h) {
    154135  check(g.width() == w, "Wrong width");
    155136  check(g.height() == h, "Wrong height");
     
    207188
    208189  {
    209     GridGraph g(5, 6);
     190    GridUGraph g(5, 6);
    210191    check_item_counts(g, 30, 49);
    211     checkGridGraph(g, 5, 6);
     192    checkGridUGraph(g, 5, 6);
    212193  }
    213194
Note: See TracChangeset for help on using the changeset viewer.