lemon/bits/graph_extender.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 16 Oct 2009 01:06:16 +0200
changeset 853 ec0b1b423b8b
parent 440 88ed40ad0d4f
child 685 a27356ceb5bd
permissions -rw-r--r--
Rework and improve Suurballe (#323)

- Improve the implementation: use a specific, faster variant of
residual Dijkstra for the first search.
- Some reorganizatiopn to make the code simpler.
- Small doc improvements.
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_BITS_GRAPH_EXTENDER_H
    20 #define LEMON_BITS_GRAPH_EXTENDER_H
    21 
    22 #include <lemon/core.h>
    23 
    24 #include <lemon/bits/map_extender.h>
    25 #include <lemon/bits/default_map.h>
    26 
    27 #include <lemon/concept_check.h>
    28 #include <lemon/concepts/maps.h>
    29 
    30 //\ingroup graphbits
    31 //\file
    32 //\brief Extenders for the graph types
    33 namespace lemon {
    34 
    35   // \ingroup graphbits
    36   //
    37   // \brief Extender for the digraph implementations
    38   template <typename Base>
    39   class DigraphExtender : public Base {
    40     typedef Base Parent;
    41 
    42   public:
    43 
    44     typedef DigraphExtender Digraph;
    45 
    46     // Base extensions
    47 
    48     typedef typename Parent::Node Node;
    49     typedef typename Parent::Arc Arc;
    50 
    51     int maxId(Node) const {
    52       return Parent::maxNodeId();
    53     }
    54 
    55     int maxId(Arc) const {
    56       return Parent::maxArcId();
    57     }
    58 
    59     Node fromId(int id, Node) const {
    60       return Parent::nodeFromId(id);
    61     }
    62 
    63     Arc fromId(int id, Arc) const {
    64       return Parent::arcFromId(id);
    65     }
    66 
    67     Node oppositeNode(const Node &node, const Arc &arc) const {
    68       if (node == Parent::source(arc))
    69         return Parent::target(arc);
    70       else if(node == Parent::target(arc))
    71         return Parent::source(arc);
    72       else
    73         return INVALID;
    74     }
    75 
    76     // Alterable extension
    77 
    78     typedef AlterationNotifier<DigraphExtender, Node> NodeNotifier;
    79     typedef AlterationNotifier<DigraphExtender, Arc> ArcNotifier;
    80 
    81 
    82   protected:
    83 
    84     mutable NodeNotifier node_notifier;
    85     mutable ArcNotifier arc_notifier;
    86 
    87   public:
    88 
    89     NodeNotifier& notifier(Node) const {
    90       return node_notifier;
    91     }
    92 
    93     ArcNotifier& notifier(Arc) const {
    94       return arc_notifier;
    95     }
    96 
    97     class NodeIt : public Node {
    98       const Digraph* _digraph;
    99     public:
   100 
   101       NodeIt() {}
   102 
   103       NodeIt(Invalid i) : Node(i) { }
   104 
   105       explicit NodeIt(const Digraph& digraph) : _digraph(&digraph) {
   106         _digraph->first(static_cast<Node&>(*this));
   107       }
   108 
   109       NodeIt(const Digraph& digraph, const Node& node)
   110         : Node(node), _digraph(&digraph) {}
   111 
   112       NodeIt& operator++() {
   113         _digraph->next(*this);
   114         return *this;
   115       }
   116 
   117     };
   118 
   119 
   120     class ArcIt : public Arc {
   121       const Digraph* _digraph;
   122     public:
   123 
   124       ArcIt() { }
   125 
   126       ArcIt(Invalid i) : Arc(i) { }
   127 
   128       explicit ArcIt(const Digraph& digraph) : _digraph(&digraph) {
   129         _digraph->first(static_cast<Arc&>(*this));
   130       }
   131 
   132       ArcIt(const Digraph& digraph, const Arc& arc) :
   133         Arc(arc), _digraph(&digraph) { }
   134 
   135       ArcIt& operator++() {
   136         _digraph->next(*this);
   137         return *this;
   138       }
   139 
   140     };
   141 
   142 
   143     class OutArcIt : public Arc {
   144       const Digraph* _digraph;
   145     public:
   146 
   147       OutArcIt() { }
   148 
   149       OutArcIt(Invalid i) : Arc(i) { }
   150 
   151       OutArcIt(const Digraph& digraph, const Node& node)
   152         : _digraph(&digraph) {
   153         _digraph->firstOut(*this, node);
   154       }
   155 
   156       OutArcIt(const Digraph& digraph, const Arc& arc)
   157         : Arc(arc), _digraph(&digraph) {}
   158 
   159       OutArcIt& operator++() {
   160         _digraph->nextOut(*this);
   161         return *this;
   162       }
   163 
   164     };
   165 
   166 
   167     class InArcIt : public Arc {
   168       const Digraph* _digraph;
   169     public:
   170 
   171       InArcIt() { }
   172 
   173       InArcIt(Invalid i) : Arc(i) { }
   174 
   175       InArcIt(const Digraph& digraph, const Node& node)
   176         : _digraph(&digraph) {
   177         _digraph->firstIn(*this, node);
   178       }
   179 
   180       InArcIt(const Digraph& digraph, const Arc& arc) :
   181         Arc(arc), _digraph(&digraph) {}
   182 
   183       InArcIt& operator++() {
   184         _digraph->nextIn(*this);
   185         return *this;
   186       }
   187 
   188     };
   189 
   190     // \brief Base node of the iterator
   191     //
   192     // Returns the base node (i.e. the source in this case) of the iterator
   193     Node baseNode(const OutArcIt &arc) const {
   194       return Parent::source(arc);
   195     }
   196     // \brief Running node of the iterator
   197     //
   198     // Returns the running node (i.e. the target in this case) of the
   199     // iterator
   200     Node runningNode(const OutArcIt &arc) const {
   201       return Parent::target(arc);
   202     }
   203 
   204     // \brief Base node of the iterator
   205     //
   206     // Returns the base node (i.e. the target in this case) of the iterator
   207     Node baseNode(const InArcIt &arc) const {
   208       return Parent::target(arc);
   209     }
   210     // \brief Running node of the iterator
   211     //
   212     // Returns the running node (i.e. the source in this case) of the
   213     // iterator
   214     Node runningNode(const InArcIt &arc) const {
   215       return Parent::source(arc);
   216     }
   217 
   218 
   219     template <typename _Value>
   220     class NodeMap
   221       : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
   222       typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
   223 
   224     public:
   225       explicit NodeMap(const Digraph& digraph)
   226         : Parent(digraph) {}
   227       NodeMap(const Digraph& digraph, const _Value& value)
   228         : Parent(digraph, value) {}
   229 
   230     private:
   231       NodeMap& operator=(const NodeMap& cmap) {
   232         return operator=<NodeMap>(cmap);
   233       }
   234 
   235       template <typename CMap>
   236       NodeMap& operator=(const CMap& cmap) {
   237         Parent::operator=(cmap);
   238         return *this;
   239       }
   240 
   241     };
   242 
   243     template <typename _Value>
   244     class ArcMap
   245       : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
   246       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
   247 
   248     public:
   249       explicit ArcMap(const Digraph& digraph)
   250         : Parent(digraph) {}
   251       ArcMap(const Digraph& digraph, const _Value& value)
   252         : Parent(digraph, value) {}
   253 
   254     private:
   255       ArcMap& operator=(const ArcMap& cmap) {
   256         return operator=<ArcMap>(cmap);
   257       }
   258 
   259       template <typename CMap>
   260       ArcMap& operator=(const CMap& cmap) {
   261         Parent::operator=(cmap);
   262         return *this;
   263       }
   264     };
   265 
   266 
   267     Node addNode() {
   268       Node node = Parent::addNode();
   269       notifier(Node()).add(node);
   270       return node;
   271     }
   272 
   273     Arc addArc(const Node& from, const Node& to) {
   274       Arc arc = Parent::addArc(from, to);
   275       notifier(Arc()).add(arc);
   276       return arc;
   277     }
   278 
   279     void clear() {
   280       notifier(Arc()).clear();
   281       notifier(Node()).clear();
   282       Parent::clear();
   283     }
   284 
   285     template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
   286     void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
   287       Parent::build(digraph, nodeRef, arcRef);
   288       notifier(Node()).build();
   289       notifier(Arc()).build();
   290     }
   291 
   292     void erase(const Node& node) {
   293       Arc arc;
   294       Parent::firstOut(arc, node);
   295       while (arc != INVALID ) {
   296         erase(arc);
   297         Parent::firstOut(arc, node);
   298       }
   299 
   300       Parent::firstIn(arc, node);
   301       while (arc != INVALID ) {
   302         erase(arc);
   303         Parent::firstIn(arc, node);
   304       }
   305 
   306       notifier(Node()).erase(node);
   307       Parent::erase(node);
   308     }
   309 
   310     void erase(const Arc& arc) {
   311       notifier(Arc()).erase(arc);
   312       Parent::erase(arc);
   313     }
   314 
   315     DigraphExtender() {
   316       node_notifier.setContainer(*this);
   317       arc_notifier.setContainer(*this);
   318     }
   319 
   320 
   321     ~DigraphExtender() {
   322       arc_notifier.clear();
   323       node_notifier.clear();
   324     }
   325   };
   326 
   327   // \ingroup _graphbits
   328   //
   329   // \brief Extender for the Graphs
   330   template <typename Base>
   331   class GraphExtender : public Base {
   332     typedef Base Parent;
   333 
   334   public:
   335 
   336     typedef GraphExtender Graph;
   337 
   338     typedef True UndirectedTag;
   339 
   340     typedef typename Parent::Node Node;
   341     typedef typename Parent::Arc Arc;
   342     typedef typename Parent::Edge Edge;
   343 
   344     // Graph extension
   345 
   346     int maxId(Node) const {
   347       return Parent::maxNodeId();
   348     }
   349 
   350     int maxId(Arc) const {
   351       return Parent::maxArcId();
   352     }
   353 
   354     int maxId(Edge) const {
   355       return Parent::maxEdgeId();
   356     }
   357 
   358     Node fromId(int id, Node) const {
   359       return Parent::nodeFromId(id);
   360     }
   361 
   362     Arc fromId(int id, Arc) const {
   363       return Parent::arcFromId(id);
   364     }
   365 
   366     Edge fromId(int id, Edge) const {
   367       return Parent::edgeFromId(id);
   368     }
   369 
   370     Node oppositeNode(const Node &n, const Edge &e) const {
   371       if( n == Parent::u(e))
   372         return Parent::v(e);
   373       else if( n == Parent::v(e))
   374         return Parent::u(e);
   375       else
   376         return INVALID;
   377     }
   378 
   379     Arc oppositeArc(const Arc &arc) const {
   380       return Parent::direct(arc, !Parent::direction(arc));
   381     }
   382 
   383     using Parent::direct;
   384     Arc direct(const Edge &edge, const Node &node) const {
   385       return Parent::direct(edge, Parent::u(edge) == node);
   386     }
   387 
   388     // Alterable extension
   389 
   390     typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
   391     typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;
   392     typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
   393 
   394 
   395   protected:
   396 
   397     mutable NodeNotifier node_notifier;
   398     mutable ArcNotifier arc_notifier;
   399     mutable EdgeNotifier edge_notifier;
   400 
   401   public:
   402 
   403     NodeNotifier& notifier(Node) const {
   404       return node_notifier;
   405     }
   406 
   407     ArcNotifier& notifier(Arc) const {
   408       return arc_notifier;
   409     }
   410 
   411     EdgeNotifier& notifier(Edge) const {
   412       return edge_notifier;
   413     }
   414 
   415 
   416 
   417     class NodeIt : public Node {
   418       const Graph* _graph;
   419     public:
   420 
   421       NodeIt() {}
   422 
   423       NodeIt(Invalid i) : Node(i) { }
   424 
   425       explicit NodeIt(const Graph& graph) : _graph(&graph) {
   426         _graph->first(static_cast<Node&>(*this));
   427       }
   428 
   429       NodeIt(const Graph& graph, const Node& node)
   430         : Node(node), _graph(&graph) {}
   431 
   432       NodeIt& operator++() {
   433         _graph->next(*this);
   434         return *this;
   435       }
   436 
   437     };
   438 
   439 
   440     class ArcIt : public Arc {
   441       const Graph* _graph;
   442     public:
   443 
   444       ArcIt() { }
   445 
   446       ArcIt(Invalid i) : Arc(i) { }
   447 
   448       explicit ArcIt(const Graph& graph) : _graph(&graph) {
   449         _graph->first(static_cast<Arc&>(*this));
   450       }
   451 
   452       ArcIt(const Graph& graph, const Arc& arc) :
   453         Arc(arc), _graph(&graph) { }
   454 
   455       ArcIt& operator++() {
   456         _graph->next(*this);
   457         return *this;
   458       }
   459 
   460     };
   461 
   462 
   463     class OutArcIt : public Arc {
   464       const Graph* _graph;
   465     public:
   466 
   467       OutArcIt() { }
   468 
   469       OutArcIt(Invalid i) : Arc(i) { }
   470 
   471       OutArcIt(const Graph& graph, const Node& node)
   472         : _graph(&graph) {
   473         _graph->firstOut(*this, node);
   474       }
   475 
   476       OutArcIt(const Graph& graph, const Arc& arc)
   477         : Arc(arc), _graph(&graph) {}
   478 
   479       OutArcIt& operator++() {
   480         _graph->nextOut(*this);
   481         return *this;
   482       }
   483 
   484     };
   485 
   486 
   487     class InArcIt : public Arc {
   488       const Graph* _graph;
   489     public:
   490 
   491       InArcIt() { }
   492 
   493       InArcIt(Invalid i) : Arc(i) { }
   494 
   495       InArcIt(const Graph& graph, const Node& node)
   496         : _graph(&graph) {
   497         _graph->firstIn(*this, node);
   498       }
   499 
   500       InArcIt(const Graph& graph, const Arc& arc) :
   501         Arc(arc), _graph(&graph) {}
   502 
   503       InArcIt& operator++() {
   504         _graph->nextIn(*this);
   505         return *this;
   506       }
   507 
   508     };
   509 
   510 
   511     class EdgeIt : public Parent::Edge {
   512       const Graph* _graph;
   513     public:
   514 
   515       EdgeIt() { }
   516 
   517       EdgeIt(Invalid i) : Edge(i) { }
   518 
   519       explicit EdgeIt(const Graph& graph) : _graph(&graph) {
   520         _graph->first(static_cast<Edge&>(*this));
   521       }
   522 
   523       EdgeIt(const Graph& graph, const Edge& edge) :
   524         Edge(edge), _graph(&graph) { }
   525 
   526       EdgeIt& operator++() {
   527         _graph->next(*this);
   528         return *this;
   529       }
   530 
   531     };
   532 
   533     class IncEdgeIt : public Parent::Edge {
   534       friend class GraphExtender;
   535       const Graph* _graph;
   536       bool _direction;
   537     public:
   538 
   539       IncEdgeIt() { }
   540 
   541       IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
   542 
   543       IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {
   544         _graph->firstInc(*this, _direction, node);
   545       }
   546 
   547       IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)
   548         : _graph(&graph), Edge(edge) {
   549         _direction = (_graph->source(edge) == node);
   550       }
   551 
   552       IncEdgeIt& operator++() {
   553         _graph->nextInc(*this, _direction);
   554         return *this;
   555       }
   556     };
   557 
   558     // \brief Base node of the iterator
   559     //
   560     // Returns the base node (ie. the source in this case) of the iterator
   561     Node baseNode(const OutArcIt &arc) const {
   562       return Parent::source(static_cast<const Arc&>(arc));
   563     }
   564     // \brief Running node of the iterator
   565     //
   566     // Returns the running node (ie. the target in this case) of the
   567     // iterator
   568     Node runningNode(const OutArcIt &arc) const {
   569       return Parent::target(static_cast<const Arc&>(arc));
   570     }
   571 
   572     // \brief Base node of the iterator
   573     //
   574     // Returns the base node (ie. the target in this case) of the iterator
   575     Node baseNode(const InArcIt &arc) const {
   576       return Parent::target(static_cast<const Arc&>(arc));
   577     }
   578     // \brief Running node of the iterator
   579     //
   580     // Returns the running node (ie. the source in this case) of the
   581     // iterator
   582     Node runningNode(const InArcIt &arc) const {
   583       return Parent::source(static_cast<const Arc&>(arc));
   584     }
   585 
   586     // Base node of the iterator
   587     //
   588     // Returns the base node of the iterator
   589     Node baseNode(const IncEdgeIt &edge) const {
   590       return edge._direction ? u(edge) : v(edge);
   591     }
   592     // Running node of the iterator
   593     //
   594     // Returns the running node of the iterator
   595     Node runningNode(const IncEdgeIt &edge) const {
   596       return edge._direction ? v(edge) : u(edge);
   597     }
   598 
   599     // Mappable extension
   600 
   601     template <typename _Value>
   602     class NodeMap
   603       : public MapExtender<DefaultMap<Graph, Node, _Value> > {
   604       typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
   605 
   606     public:
   607       NodeMap(const Graph& graph)
   608         : Parent(graph) {}
   609       NodeMap(const Graph& graph, const _Value& value)
   610         : Parent(graph, value) {}
   611 
   612     private:
   613       NodeMap& operator=(const NodeMap& cmap) {
   614         return operator=<NodeMap>(cmap);
   615       }
   616 
   617       template <typename CMap>
   618       NodeMap& operator=(const CMap& cmap) {
   619         Parent::operator=(cmap);
   620         return *this;
   621       }
   622 
   623     };
   624 
   625     template <typename _Value>
   626     class ArcMap
   627       : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
   628       typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
   629 
   630     public:
   631       ArcMap(const Graph& graph)
   632         : Parent(graph) {}
   633       ArcMap(const Graph& graph, const _Value& value)
   634         : Parent(graph, value) {}
   635 
   636     private:
   637       ArcMap& operator=(const ArcMap& cmap) {
   638         return operator=<ArcMap>(cmap);
   639       }
   640 
   641       template <typename CMap>
   642       ArcMap& operator=(const CMap& cmap) {
   643         Parent::operator=(cmap);
   644         return *this;
   645       }
   646     };
   647 
   648 
   649     template <typename _Value>
   650     class EdgeMap
   651       : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
   652       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
   653 
   654     public:
   655       EdgeMap(const Graph& graph)
   656         : Parent(graph) {}
   657 
   658       EdgeMap(const Graph& graph, const _Value& value)
   659         : Parent(graph, value) {}
   660 
   661     private:
   662       EdgeMap& operator=(const EdgeMap& cmap) {
   663         return operator=<EdgeMap>(cmap);
   664       }
   665 
   666       template <typename CMap>
   667       EdgeMap& operator=(const CMap& cmap) {
   668         Parent::operator=(cmap);
   669         return *this;
   670       }
   671 
   672     };
   673 
   674     // Alteration extension
   675 
   676     Node addNode() {
   677       Node node = Parent::addNode();
   678       notifier(Node()).add(node);
   679       return node;
   680     }
   681 
   682     Edge addEdge(const Node& from, const Node& to) {
   683       Edge edge = Parent::addEdge(from, to);
   684       notifier(Edge()).add(edge);
   685       std::vector<Arc> ev;
   686       ev.push_back(Parent::direct(edge, true));
   687       ev.push_back(Parent::direct(edge, false));
   688       notifier(Arc()).add(ev);
   689       return edge;
   690     }
   691 
   692     void clear() {
   693       notifier(Arc()).clear();
   694       notifier(Edge()).clear();
   695       notifier(Node()).clear();
   696       Parent::clear();
   697     }
   698 
   699     template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
   700     void build(const Graph& graph, NodeRefMap& nodeRef,
   701                EdgeRefMap& edgeRef) {
   702       Parent::build(graph, nodeRef, edgeRef);
   703       notifier(Node()).build();
   704       notifier(Edge()).build();
   705       notifier(Arc()).build();
   706     }
   707 
   708     void erase(const Node& node) {
   709       Arc arc;
   710       Parent::firstOut(arc, node);
   711       while (arc != INVALID ) {
   712         erase(arc);
   713         Parent::firstOut(arc, node);
   714       }
   715 
   716       Parent::firstIn(arc, node);
   717       while (arc != INVALID ) {
   718         erase(arc);
   719         Parent::firstIn(arc, node);
   720       }
   721 
   722       notifier(Node()).erase(node);
   723       Parent::erase(node);
   724     }
   725 
   726     void erase(const Edge& edge) {
   727       std::vector<Arc> av;
   728       av.push_back(Parent::direct(edge, true));
   729       av.push_back(Parent::direct(edge, false));
   730       notifier(Arc()).erase(av);
   731       notifier(Edge()).erase(edge);
   732       Parent::erase(edge);
   733     }
   734 
   735     GraphExtender() {
   736       node_notifier.setContainer(*this);
   737       arc_notifier.setContainer(*this);
   738       edge_notifier.setContainer(*this);
   739     }
   740 
   741     ~GraphExtender() {
   742       edge_notifier.clear();
   743       arc_notifier.clear();
   744       node_notifier.clear();
   745     }
   746 
   747   };
   748 
   749 }
   750 
   751 #endif