lemon/bits/path_dump.h
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 24 Feb 2009 06:51:35 +0000
branch1.0
changeset 382 f679c1eb0163
parent 100 4f754b4cf82b
child 413 1f2a734581f8
permissions -rw-r--r--
Merge
     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_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