1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/bits/path_dump.h Thu Feb 07 21:37:07 2008 +0000
1.3 @@ -0,0 +1,174 @@
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-2008
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 _Digraph, typename _PredMap>
1.28 + class PredMapPath {
1.29 + public:
1.30 + typedef True RevPathTag;
1.31 +
1.32 + typedef _Digraph Digraph;
1.33 + typedef typename Digraph::Arc Arc;
1.34 + typedef _PredMap PredMap;
1.35 +
1.36 + PredMapPath(const Digraph& _digraph, const PredMap& _predMap,
1.37 + typename Digraph::Node _target)
1.38 + : digraph(_digraph), predMap(_predMap), target(_target) {}
1.39 +
1.40 + int length() const {
1.41 + int len = 0;
1.42 + typename Digraph::Node node = target;
1.43 + typename Digraph::Arc arc;
1.44 + while ((arc = predMap[node]) != INVALID) {
1.45 + node = digraph.source(arc);
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 RevArcIt {
1.56 + public:
1.57 + RevArcIt() {}
1.58 + RevArcIt(Invalid) : path(0), current(INVALID) {}
1.59 + RevArcIt(const PredMapPath& _path)
1.60 + : path(&_path), current(_path.target) {
1.61 + if (path->predMap[current] == INVALID) current = INVALID;
1.62 + }
1.63 +
1.64 + operator const typename Digraph::Arc() const {
1.65 + return path->predMap[current];
1.66 + }
1.67 +
1.68 + RevArcIt& operator++() {
1.69 + current = path->digraph.source(path->predMap[current]);
1.70 + if (path->predMap[current] == INVALID) current = INVALID;
1.71 + return *this;
1.72 + }
1.73 +
1.74 + bool operator==(const RevArcIt& e) const {
1.75 + return current == e.current;
1.76 + }
1.77 +
1.78 + bool operator!=(const RevArcIt& e) const {
1.79 + return current != e.current;
1.80 + }
1.81 +
1.82 + bool operator<(const RevArcIt& e) const {
1.83 + return current < e.current;
1.84 + }
1.85 +
1.86 + private:
1.87 + const PredMapPath* path;
1.88 + typename Digraph::Node current;
1.89 + };
1.90 +
1.91 + private:
1.92 + const Digraph& digraph;
1.93 + const PredMap& predMap;
1.94 + typename Digraph::Node target;
1.95 + };
1.96 +
1.97 +
1.98 + template <typename _Digraph, typename _PredMatrixMap>
1.99 + class PredMatrixMapPath {
1.100 + public:
1.101 + typedef True RevPathTag;
1.102 +
1.103 + typedef _Digraph Digraph;
1.104 + typedef typename Digraph::Arc Arc;
1.105 + typedef _PredMatrixMap PredMatrixMap;
1.106 +
1.107 + PredMatrixMapPath(const Digraph& _digraph,
1.108 + const PredMatrixMap& _predMatrixMap,
1.109 + typename Digraph::Node _source,
1.110 + typename Digraph::Node _target)
1.111 + : digraph(_digraph), predMatrixMap(_predMatrixMap),
1.112 + source(_source), target(_target) {}
1.113 +
1.114 + int length() const {
1.115 + int len = 0;
1.116 + typename Digraph::Node node = target;
1.117 + typename Digraph::Arc arc;
1.118 + while ((arc = predMatrixMap(source, node)) != INVALID) {
1.119 + node = digraph.source(arc);
1.120 + ++len;
1.121 + }
1.122 + return len;
1.123 + }
1.124 +
1.125 + bool empty() const {
1.126 + return source != target;
1.127 + }
1.128 +
1.129 + class RevArcIt {
1.130 + public:
1.131 + RevArcIt() {}
1.132 + RevArcIt(Invalid) : path(0), current(INVALID) {}
1.133 + RevArcIt(const PredMatrixMapPath& _path)
1.134 + : path(&_path), current(_path.target) {
1.135 + if (path->predMatrixMap(path->source, current) == INVALID)
1.136 + current = INVALID;
1.137 + }
1.138 +
1.139 + operator const typename Digraph::Arc() const {
1.140 + return path->predMatrixMap(path->source, current);
1.141 + }
1.142 +
1.143 + RevArcIt& operator++() {
1.144 + current =
1.145 + path->digraph.source(path->predMatrixMap(path->source, current));
1.146 + if (path->predMatrixMap(path->source, current) == INVALID)
1.147 + current = INVALID;
1.148 + return *this;
1.149 + }
1.150 +
1.151 + bool operator==(const RevArcIt& e) const {
1.152 + return current == e.current;
1.153 + }
1.154 +
1.155 + bool operator!=(const RevArcIt& e) const {
1.156 + return current != e.current;
1.157 + }
1.158 +
1.159 + bool operator<(const RevArcIt& e) const {
1.160 + return current < e.current;
1.161 + }
1.162 +
1.163 + private:
1.164 + const PredMatrixMapPath* path;
1.165 + typename Digraph::Node current;
1.166 + };
1.167 +
1.168 + private:
1.169 + const Digraph& digraph;
1.170 + const PredMatrixMap& predMatrixMap;
1.171 + typename Digraph::Node source;
1.172 + typename Digraph::Node target;
1.173 + };
1.174 +
1.175 +}
1.176 +
1.177 +#endif