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