lemon/bits/path_dump.h
changeset 2335 27aa03cd3121
child 2357 5365600a7a5c
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/lemon/bits/path_dump.h	Mon Jan 08 10:39:59 2007 +0000
     1.3 @@ -0,0 +1,169 @@
     1.4 +/* -*- C++ -*-
     1.5 + *
     1.6 + * This file is a part of LEMON, a generic C++ optimization library
     1.7 + *
     1.8 + * Copyright (C) 2003-2006
     1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 + *
    1.12 + * Permission to use, modify and distribute this software is granted
    1.13 + * provided that this copyright notice appears in all copies. For
    1.14 + * precise terms see the accompanying LICENSE file.
    1.15 + *
    1.16 + * This software is provided "AS IS" with no warranty of any kind,
    1.17 + * express or implied, and with no claim as to its suitability for any
    1.18 + * purpose.
    1.19 + *
    1.20 + */
    1.21 +
    1.22 +#ifndef LEMON_BITS_PRED_MAP_PATH_H
    1.23 +#define LEMON_BITS_PRED_MAP_PATH_H
    1.24 +
    1.25 +namespace lemon {
    1.26 +
    1.27 +  template <typename _Graph, typename _PredMap>
    1.28 +  class PredMapPath {
    1.29 +  public:
    1.30 +    typedef True RevPathTag;
    1.31 +
    1.32 +    typedef _Graph Graph;
    1.33 +    typedef typename Graph::Edge Edge;
    1.34 +    typedef _PredMap PredMap;
    1.35 +
    1.36 +    PredMapPath(const Graph& _graph, const PredMap& _predMap,
    1.37 +                typename Graph::Node _target)
    1.38 +      : graph(_graph), predMap(_predMap), target(_target) {}
    1.39 +
    1.40 +    int length() const {
    1.41 +      int len = 0;
    1.42 +      typename Graph::Node node = target;
    1.43 +      typename Graph::Edge edge;
    1.44 +      while ((edge = predMap[node]) != INVALID) {
    1.45 +        node = graph.source(edge);
    1.46 +        ++len;
    1.47 +      }
    1.48 +      return len;
    1.49 +    }
    1.50 +
    1.51 +    bool empty() const {
    1.52 +      return predMap[target] != INVALID;
    1.53 +    }
    1.54 +
    1.55 +    class RevIt {
    1.56 +    public:
    1.57 +      RevIt() {}
    1.58 +      RevIt(Invalid) : path(0), current(INVALID) {}
    1.59 +      RevIt(const PredMapPath& _path) 
    1.60 +        : path(&_path), current(_path.target) {}
    1.61 +
    1.62 +      operator const typename Graph::Edge() const {
    1.63 +        return path->predMap[current];
    1.64 +      }
    1.65 +
    1.66 +      RevIt& operator++() {
    1.67 +        current = path->graph.source(path->predMap[current]);
    1.68 +        if (path->predMap[current] == INVALID) current = INVALID;
    1.69 +        return *this;
    1.70 +      }
    1.71 +
    1.72 +      bool operator==(const RevIt& e) const { 
    1.73 +        return current == e.current; 
    1.74 +      }
    1.75 +
    1.76 +      bool operator!=(const RevIt& e) const {
    1.77 +        return current != e.current; 
    1.78 +      }
    1.79 +
    1.80 +      bool operator<(const RevIt& e) const { 
    1.81 +        return current < e.current; 
    1.82 +      }
    1.83 +      
    1.84 +    private:
    1.85 +      const PredMapPath* path;
    1.86 +      typename Graph::Node current;
    1.87 +    };
    1.88 +
    1.89 +  private:
    1.90 +    const Graph& graph;
    1.91 +    const PredMap& predMap;
    1.92 +    typename Graph::Node target;
    1.93 +  };
    1.94 +
    1.95 +
    1.96 +  template <typename _Graph, typename _PredMatrixMap>
    1.97 +  class PredMatrixMapPath {
    1.98 +  public:
    1.99 +    typedef True RevPathTag;
   1.100 +
   1.101 +    typedef _Graph Graph;
   1.102 +    typedef typename Graph::Edge Edge;
   1.103 +    typedef _PredMatrixMap PredMatrixMap;
   1.104 +
   1.105 +    PredMatrixMapPath(const Graph& _graph, 
   1.106 +                      const PredMatrixMap& _predMatrixMap,
   1.107 +                      typename Graph::Node _source, 
   1.108 +                      typename Graph::Node _target)
   1.109 +      : graph(_graph), predMatrixMap(_predMatrixMap), 
   1.110 +        source(_source), target(_target) {}
   1.111 +
   1.112 +    int length() const {
   1.113 +      int len = 0;
   1.114 +      typename Graph::Node node = target;
   1.115 +      typename Graph::Edge edge;
   1.116 +      while ((edge = predMatrixMap(source, node)) != INVALID) {
   1.117 +        node = graph.source(edge);
   1.118 +        ++len;
   1.119 +      }
   1.120 +      return len;
   1.121 +    }
   1.122 +
   1.123 +    bool empty() const {
   1.124 +      return source != target;
   1.125 +    }
   1.126 +
   1.127 +    class RevIt {
   1.128 +    public:
   1.129 +      RevIt() {}
   1.130 +      RevIt(Invalid) : path(0), current(INVALID) {}
   1.131 +      RevIt(const PredMatrixMapPath& _path) 
   1.132 +        : path(&_path), current(_path.target) {}
   1.133 +
   1.134 +      operator const typename Graph::Edge() const {
   1.135 +        return path->predMatrixMap(path->source, current);
   1.136 +      }
   1.137 +
   1.138 +      RevIt& operator++() {
   1.139 +        current = 
   1.140 +          path->graph.source(path->predMatrixMap(path->source, current));
   1.141 +        if (path->predMatrixMap(path->source, current) == INVALID) 
   1.142 +          current = INVALID;
   1.143 +        return *this;
   1.144 +      }
   1.145 +
   1.146 +      bool operator==(const RevIt& e) const { 
   1.147 +        return current == e.current; 
   1.148 +      }
   1.149 +
   1.150 +      bool operator!=(const RevIt& e) const {
   1.151 +        return current != e.current; 
   1.152 +      }
   1.153 +
   1.154 +      bool operator<(const RevIt& e) const { 
   1.155 +        return current < e.current; 
   1.156 +      }
   1.157 +      
   1.158 +    private:
   1.159 +      const PredMatrixMapPath* path;
   1.160 +      typename Graph::Node current;
   1.161 +    };
   1.162 +
   1.163 +  private:
   1.164 +    const Graph& graph;
   1.165 +    const PredMatrixMap& predMatrixMap;
   1.166 +    typename Graph::Node source;
   1.167 +    typename Graph::Node target;
   1.168 +  };
   1.169 +
   1.170 +}
   1.171 +
   1.172 +#endif