lemon/bits/base_extender.h
author Peter Kovacs <kpeter@inf.elte.hu>
Mon, 22 Sep 2008 15:33:23 +0200
changeset 278 931190050520
parent 220 a5d8c039f218
child 280 e7f8647ce760
permissions -rw-r--r--
Improve the function-type interface of bfs, dfs, and dijkstra (ticket #96)
- BfsWizard and DfsWizard have run(s), run(s,t), and run() functions,
DijkstraWizard has run(s) and run(s,t) functions.
- Set NodeMap<T> instead of NullMap as PredMap and DistMap in the default
traits classes for the function-type interface.
- Modify the related test files.
- Doc improvements.
- Bug fix in concepts/path.h.
     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-2008
     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_BASE_EXTENDER_H
    20 #define LEMON_BITS_BASE_EXTENDER_H
    21 
    22 #include <lemon/core.h>
    23 #include <lemon/error.h>
    24 
    25 #include <lemon/bits/map_extender.h>
    26 #include <lemon/bits/default_map.h>
    27 
    28 #include <lemon/concept_check.h>
    29 #include <lemon/concepts/maps.h>
    30 
    31 ///\ingroup digraphbits
    32 ///\file
    33 ///\brief Extenders for the digraph types
    34 namespace lemon {
    35 
    36   /// \ingroup digraphbits
    37   ///
    38   /// \brief BaseDigraph to BaseGraph extender
    39   template <typename Base>
    40   class UndirDigraphExtender : public Base {
    41 
    42   public:
    43 
    44     typedef Base Parent;
    45     typedef typename Parent::Arc Edge;
    46     typedef typename Parent::Node Node;
    47 
    48     typedef True UndirectedTag;
    49 
    50     class Arc : public Edge {
    51       friend class UndirDigraphExtender;
    52 
    53     protected:
    54       bool forward;
    55 
    56       Arc(const Edge &ue, bool _forward) :
    57         Edge(ue), forward(_forward) {}
    58 
    59     public:
    60       Arc() {}
    61 
    62       // Invalid arc constructor
    63       Arc(Invalid i) : Edge(i), forward(true) {}
    64 
    65       bool operator==(const Arc &that) const {
    66         return forward==that.forward && Edge(*this)==Edge(that);
    67       }
    68       bool operator!=(const Arc &that) const {
    69         return forward!=that.forward || Edge(*this)!=Edge(that);
    70       }
    71       bool operator<(const Arc &that) const {
    72         return forward<that.forward ||
    73           (!(that.forward<forward) && Edge(*this)<Edge(that));
    74       }
    75     };
    76 
    77     /// First node of the edge
    78     Node u(const Edge &e) const {
    79       return Parent::source(e);
    80     }
    81 
    82     /// Source of the given arc
    83     Node source(const Arc &e) const {
    84       return e.forward ? Parent::source(e) : Parent::target(e);
    85     }
    86 
    87     /// Second node of the edge
    88     Node v(const Edge &e) const {
    89       return Parent::target(e);
    90     }
    91 
    92     /// Target of the given arc
    93     Node target(const Arc &e) const {
    94       return e.forward ? Parent::target(e) : Parent::source(e);
    95     }
    96 
    97     /// \brief Directed arc from an edge.
    98     ///
    99     /// Returns a directed arc corresponding to the specified edge.
   100     /// If the given bool is true, the first node of the given edge and
   101     /// the source node of the returned arc are the same.
   102     static Arc direct(const Edge &e, bool d) {
   103       return Arc(e, d);
   104     }
   105 
   106     /// Returns whether the given directed arc has the same orientation
   107     /// as the corresponding edge.
   108     ///
   109     /// \todo reference to the corresponding point of the undirected digraph
   110     /// concept. "What does the direction of an edge mean?"
   111     static bool direction(const Arc &a) { return a.forward; }
   112 
   113     using Parent::first;
   114     using Parent::next;
   115 
   116     void first(Arc &e) const {
   117       Parent::first(e);
   118       e.forward=true;
   119     }
   120 
   121     void next(Arc &e) const {
   122       if( e.forward ) {
   123         e.forward = false;
   124       }
   125       else {
   126         Parent::next(e);
   127         e.forward = true;
   128       }
   129     }
   130 
   131     void firstOut(Arc &e, const Node &n) const {
   132       Parent::firstIn(e,n);
   133       if( Edge(e) != INVALID ) {
   134         e.forward = false;
   135       }
   136       else {
   137         Parent::firstOut(e,n);
   138         e.forward = true;
   139       }
   140     }
   141     void nextOut(Arc &e) const {
   142       if( ! e.forward ) {
   143         Node n = Parent::target(e);
   144         Parent::nextIn(e);
   145         if( Edge(e) == INVALID ) {
   146           Parent::firstOut(e, n);
   147           e.forward = true;
   148         }
   149       }
   150       else {
   151         Parent::nextOut(e);
   152       }
   153     }
   154 
   155     void firstIn(Arc &e, const Node &n) const {
   156       Parent::firstOut(e,n);
   157       if( Edge(e) != INVALID ) {
   158         e.forward = false;
   159       }
   160       else {
   161         Parent::firstIn(e,n);
   162         e.forward = true;
   163       }
   164     }
   165     void nextIn(Arc &e) const {
   166       if( ! e.forward ) {
   167         Node n = Parent::source(e);
   168         Parent::nextOut(e);
   169         if( Edge(e) == INVALID ) {
   170           Parent::firstIn(e, n);
   171           e.forward = true;
   172         }
   173       }
   174       else {
   175         Parent::nextIn(e);
   176       }
   177     }
   178 
   179     void firstInc(Edge &e, bool &d, const Node &n) const {
   180       d = true;
   181       Parent::firstOut(e, n);
   182       if (e != INVALID) return;
   183       d = false;
   184       Parent::firstIn(e, n);
   185     }
   186 
   187     void nextInc(Edge &e, bool &d) const {
   188       if (d) {
   189         Node s = Parent::source(e);
   190         Parent::nextOut(e);
   191         if (e != INVALID) return;
   192         d = false;
   193         Parent::firstIn(e, s);
   194       } else {
   195         Parent::nextIn(e);
   196       }
   197     }
   198 
   199     Node nodeFromId(int ix) const {
   200       return Parent::nodeFromId(ix);
   201     }
   202 
   203     Arc arcFromId(int ix) const {
   204       return direct(Parent::arcFromId(ix >> 1), bool(ix & 1));
   205     }
   206 
   207     Edge edgeFromId(int ix) const {
   208       return Parent::arcFromId(ix);
   209     }
   210 
   211     int id(const Node &n) const {
   212       return Parent::id(n);
   213     }
   214 
   215     int id(const Edge &e) const {
   216       return Parent::id(e);
   217     }
   218 
   219     int id(const Arc &e) const {
   220       return 2 * Parent::id(e) + int(e.forward);
   221     }
   222 
   223     int maxNodeId() const {
   224       return Parent::maxNodeId();
   225     }
   226 
   227     int maxArcId() const {
   228       return 2 * Parent::maxArcId() + 1;
   229     }
   230 
   231     int maxEdgeId() const {
   232       return Parent::maxArcId();
   233     }
   234 
   235     int arcNum() const {
   236       return 2 * Parent::arcNum();
   237     }
   238 
   239     int edgeNum() const {
   240       return Parent::arcNum();
   241     }
   242 
   243     Arc findArc(Node s, Node t, Arc p = INVALID) const {
   244       if (p == INVALID) {
   245         Edge arc = Parent::findArc(s, t);
   246         if (arc != INVALID) return direct(arc, true);
   247         arc = Parent::findArc(t, s);
   248         if (arc != INVALID) return direct(arc, false);
   249       } else if (direction(p)) {
   250         Edge arc = Parent::findArc(s, t, p);
   251         if (arc != INVALID) return direct(arc, true);
   252         arc = Parent::findArc(t, s);
   253         if (arc != INVALID) return direct(arc, false);
   254       } else {
   255         Edge arc = Parent::findArc(t, s, p);
   256         if (arc != INVALID) return direct(arc, false);
   257       }
   258       return INVALID;
   259     }
   260 
   261     Edge findEdge(Node s, Node t, Edge p = INVALID) const {
   262       if (s != t) {
   263         if (p == INVALID) {
   264           Edge arc = Parent::findArc(s, t);
   265           if (arc != INVALID) return arc;
   266           arc = Parent::findArc(t, s);
   267           if (arc != INVALID) return arc;
   268         } else if (Parent::s(p) == s) {
   269           Edge arc = Parent::findArc(s, t, p);
   270           if (arc != INVALID) return arc;
   271           arc = Parent::findArc(t, s);
   272           if (arc != INVALID) return arc;
   273         } else {
   274           Edge arc = Parent::findArc(t, s, p);
   275           if (arc != INVALID) return arc;
   276         }
   277       } else {
   278         return Parent::findArc(s, t, p);
   279       }
   280       return INVALID;
   281     }
   282   };
   283 
   284   template <typename Base>
   285   class BidirBpGraphExtender : public Base {
   286   public:
   287     typedef Base Parent;
   288     typedef BidirBpGraphExtender Digraph;
   289 
   290     typedef typename Parent::Node Node;
   291     typedef typename Parent::Edge Edge;
   292 
   293 
   294     using Parent::first;
   295     using Parent::next;
   296 
   297     using Parent::id;
   298 
   299     class Red : public Node {
   300       friend class BidirBpGraphExtender;
   301     public:
   302       Red() {}
   303       Red(const Node& node) : Node(node) {
   304         LEMON_ASSERT(Parent::red(node) || node == INVALID,
   305                      typename Parent::NodeSetError());
   306       }
   307       Red& operator=(const Node& node) {
   308         LEMON_ASSERT(Parent::red(node) || node == INVALID,
   309                      typename Parent::NodeSetError());
   310         Node::operator=(node);
   311         return *this;
   312       }
   313       Red(Invalid) : Node(INVALID) {}
   314       Red& operator=(Invalid) {
   315         Node::operator=(INVALID);
   316         return *this;
   317       }
   318     };
   319 
   320     void first(Red& node) const {
   321       Parent::firstRed(static_cast<Node&>(node));
   322     }
   323     void next(Red& node) const {
   324       Parent::nextRed(static_cast<Node&>(node));
   325     }
   326 
   327     int id(const Red& node) const {
   328       return Parent::redId(node);
   329     }
   330 
   331     class Blue : public Node {
   332       friend class BidirBpGraphExtender;
   333     public:
   334       Blue() {}
   335       Blue(const Node& node) : Node(node) {
   336         LEMON_ASSERT(Parent::blue(node) || node == INVALID,
   337                      typename Parent::NodeSetError());
   338       }
   339       Blue& operator=(const Node& node) {
   340         LEMON_ASSERT(Parent::blue(node) || node == INVALID,
   341                      typename Parent::NodeSetError());
   342         Node::operator=(node);
   343         return *this;
   344       }
   345       Blue(Invalid) : Node(INVALID) {}
   346       Blue& operator=(Invalid) {
   347         Node::operator=(INVALID);
   348         return *this;
   349       }
   350     };
   351 
   352     void first(Blue& node) const {
   353       Parent::firstBlue(static_cast<Node&>(node));
   354     }
   355     void next(Blue& node) const {
   356       Parent::nextBlue(static_cast<Node&>(node));
   357     }
   358 
   359     int id(const Blue& node) const {
   360       return Parent::redId(node);
   361     }
   362 
   363     Node source(const Edge& arc) const {
   364       return red(arc);
   365     }
   366     Node target(const Edge& arc) const {
   367       return blue(arc);
   368     }
   369 
   370     void firstInc(Edge& arc, bool& dir, const Node& node) const {
   371       if (Parent::red(node)) {
   372         Parent::firstFromRed(arc, node);
   373         dir = true;
   374       } else {
   375         Parent::firstFromBlue(arc, node);
   376         dir = static_cast<Edge&>(arc) == INVALID;
   377       }
   378     }
   379     void nextInc(Edge& arc, bool& dir) const {
   380       if (dir) {
   381         Parent::nextFromRed(arc);
   382       } else {
   383         Parent::nextFromBlue(arc);
   384         if (arc == INVALID) dir = true;
   385       }
   386     }
   387 
   388     class Arc : public Edge {
   389       friend class BidirBpGraphExtender;
   390     protected:
   391       bool forward;
   392 
   393       Arc(const Edge& arc, bool _forward)
   394         : Edge(arc), forward(_forward) {}
   395 
   396     public:
   397       Arc() {}
   398       Arc (Invalid) : Edge(INVALID), forward(true) {}
   399       bool operator==(const Arc& i) const {
   400         return Edge::operator==(i) && forward == i.forward;
   401       }
   402       bool operator!=(const Arc& i) const {
   403         return Edge::operator!=(i) || forward != i.forward;
   404       }
   405       bool operator<(const Arc& i) const {
   406         return Edge::operator<(i) ||
   407           (!(i.forward<forward) && Edge(*this)<Edge(i));
   408       }
   409     };
   410 
   411     void first(Arc& arc) const {
   412       Parent::first(static_cast<Edge&>(arc));
   413       arc.forward = true;
   414     }
   415 
   416     void next(Arc& arc) const {
   417       if (!arc.forward) {
   418         Parent::next(static_cast<Edge&>(arc));
   419       }
   420       arc.forward = !arc.forward;
   421     }
   422 
   423     void firstOut(Arc& arc, const Node& node) const {
   424       if (Parent::red(node)) {
   425         Parent::firstFromRed(arc, node);
   426         arc.forward = true;
   427       } else {
   428         Parent::firstFromBlue(arc, node);
   429         arc.forward = static_cast<Edge&>(arc) == INVALID;
   430       }
   431     }
   432     void nextOut(Arc& arc) const {
   433       if (arc.forward) {
   434         Parent::nextFromRed(arc);
   435       } else {
   436         Parent::nextFromBlue(arc);
   437         arc.forward = static_cast<Edge&>(arc) == INVALID;
   438       }
   439     }
   440 
   441     void firstIn(Arc& arc, const Node& node) const {
   442       if (Parent::blue(node)) {
   443         Parent::firstFromBlue(arc, node);
   444         arc.forward = true;
   445       } else {
   446         Parent::firstFromRed(arc, node);
   447         arc.forward = static_cast<Edge&>(arc) == INVALID;
   448       }
   449     }
   450     void nextIn(Arc& arc) const {
   451       if (arc.forward) {
   452         Parent::nextFromBlue(arc);
   453       } else {
   454         Parent::nextFromRed(arc);
   455         arc.forward = static_cast<Edge&>(arc) == INVALID;
   456       }
   457     }
   458 
   459     Node source(const Arc& arc) const {
   460       return arc.forward ? Parent::red(arc) : Parent::blue(arc);
   461     }
   462     Node target(const Arc& arc) const {
   463       return arc.forward ? Parent::blue(arc) : Parent::red(arc);
   464     }
   465 
   466     int id(const Arc& arc) const {
   467       return (Parent::id(static_cast<const Edge&>(arc)) << 1) +
   468         (arc.forward ? 0 : 1);
   469     }
   470     Arc arcFromId(int ix) const {
   471       return Arc(Parent::fromEdgeId(ix >> 1), (ix & 1) == 0);
   472     }
   473     int maxArcId() const {
   474       return (Parent::maxEdgeId() << 1) + 1;
   475     }
   476 
   477     bool direction(const Arc& arc) const {
   478       return arc.forward;
   479     }
   480 
   481     Arc direct(const Edge& arc, bool dir) const {
   482       return Arc(arc, dir);
   483     }
   484 
   485     int arcNum() const {
   486       return 2 * Parent::edgeNum();
   487     }
   488 
   489     int edgeNum() const {
   490       return Parent::edgeNum();
   491     }
   492 
   493 
   494   };
   495 }
   496 
   497 #endif