lemon/bits/path_dump.h
changeset 179 289266783a0b
child 209 765619b7cbb2
equal deleted inserted replaced
-1:000000000000 0:757cd130ea3e
       
     1 /* -*- C++ -*-
       
     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_PRED_MAP_PATH_H
       
    20 #define LEMON_BITS_PRED_MAP_PATH_H
       
    21 
       
    22 namespace lemon {
       
    23 
       
    24   template <typename _Digraph, typename _PredMap>
       
    25   class PredMapPath {
       
    26   public:
       
    27     typedef True RevPathTag;
       
    28 
       
    29     typedef _Digraph Digraph;
       
    30     typedef typename Digraph::Arc Arc;
       
    31     typedef _PredMap PredMap;
       
    32 
       
    33     PredMapPath(const Digraph& _digraph, const PredMap& _predMap,
       
    34                 typename Digraph::Node _target)
       
    35       : digraph(_digraph), predMap(_predMap), target(_target) {}
       
    36 
       
    37     int length() const {
       
    38       int len = 0;
       
    39       typename Digraph::Node node = target;
       
    40       typename Digraph::Arc arc;
       
    41       while ((arc = predMap[node]) != INVALID) {
       
    42         node = digraph.source(arc);
       
    43         ++len;
       
    44       }
       
    45       return len;
       
    46     }
       
    47 
       
    48     bool empty() const {
       
    49       return predMap[target] != INVALID;
       
    50     }
       
    51 
       
    52     class RevArcIt {
       
    53     public:
       
    54       RevArcIt() {}
       
    55       RevArcIt(Invalid) : path(0), current(INVALID) {}
       
    56       RevArcIt(const PredMapPath& _path) 
       
    57         : path(&_path), current(_path.target) {
       
    58         if (path->predMap[current] == INVALID) current = INVALID;
       
    59       }
       
    60 
       
    61       operator const typename Digraph::Arc() const {
       
    62         return path->predMap[current];
       
    63       }
       
    64 
       
    65       RevArcIt& operator++() {
       
    66         current = path->digraph.source(path->predMap[current]);
       
    67         if (path->predMap[current] == INVALID) current = INVALID;
       
    68         return *this;
       
    69       }
       
    70 
       
    71       bool operator==(const RevArcIt& e) const { 
       
    72         return current == e.current; 
       
    73       }
       
    74 
       
    75       bool operator!=(const RevArcIt& e) const {
       
    76         return current != e.current; 
       
    77       }
       
    78 
       
    79       bool operator<(const RevArcIt& e) const { 
       
    80         return current < e.current; 
       
    81       }
       
    82       
       
    83     private:
       
    84       const PredMapPath* path;
       
    85       typename Digraph::Node current;
       
    86     };
       
    87 
       
    88   private:
       
    89     const Digraph& digraph;
       
    90     const PredMap& predMap;
       
    91     typename Digraph::Node target;
       
    92   };
       
    93 
       
    94 
       
    95   template <typename _Digraph, typename _PredMatrixMap>
       
    96   class PredMatrixMapPath {
       
    97   public:
       
    98     typedef True RevPathTag;
       
    99 
       
   100     typedef _Digraph Digraph;
       
   101     typedef typename Digraph::Arc Arc;
       
   102     typedef _PredMatrixMap PredMatrixMap;
       
   103 
       
   104     PredMatrixMapPath(const Digraph& _digraph, 
       
   105                       const PredMatrixMap& _predMatrixMap,
       
   106                       typename Digraph::Node _source, 
       
   107                       typename Digraph::Node _target)
       
   108       : digraph(_digraph), predMatrixMap(_predMatrixMap), 
       
   109         source(_source), target(_target) {}
       
   110 
       
   111     int length() const {
       
   112       int len = 0;
       
   113       typename Digraph::Node node = target;
       
   114       typename Digraph::Arc arc;
       
   115       while ((arc = predMatrixMap(source, node)) != INVALID) {
       
   116         node = digraph.source(arc);
       
   117         ++len;
       
   118       }
       
   119       return len;
       
   120     }
       
   121 
       
   122     bool empty() const {
       
   123       return source != target;
       
   124     }
       
   125 
       
   126     class RevArcIt {
       
   127     public:
       
   128       RevArcIt() {}
       
   129       RevArcIt(Invalid) : path(0), current(INVALID) {}
       
   130       RevArcIt(const PredMatrixMapPath& _path) 
       
   131         : path(&_path), current(_path.target) {
       
   132         if (path->predMatrixMap(path->source, current) == INVALID) 
       
   133           current = INVALID;
       
   134       }
       
   135 
       
   136       operator const typename Digraph::Arc() const {
       
   137         return path->predMatrixMap(path->source, current);
       
   138       }
       
   139 
       
   140       RevArcIt& operator++() {
       
   141         current = 
       
   142           path->digraph.source(path->predMatrixMap(path->source, current));
       
   143         if (path->predMatrixMap(path->source, current) == INVALID) 
       
   144           current = INVALID;
       
   145         return *this;
       
   146       }
       
   147 
       
   148       bool operator==(const RevArcIt& e) const { 
       
   149         return current == e.current; 
       
   150       }
       
   151 
       
   152       bool operator!=(const RevArcIt& e) const {
       
   153         return current != e.current; 
       
   154       }
       
   155 
       
   156       bool operator<(const RevArcIt& e) const { 
       
   157         return current < e.current; 
       
   158       }
       
   159       
       
   160     private:
       
   161       const PredMatrixMapPath* path;
       
   162       typename Digraph::Node current;
       
   163     };
       
   164 
       
   165   private:
       
   166     const Digraph& digraph;
       
   167     const PredMatrixMap& predMatrixMap;
       
   168     typename Digraph::Node source;
       
   169     typename Digraph::Node target;
       
   170   };
       
   171 
       
   172 }
       
   173 
       
   174 #endif