[2335] | 1 | /* -*- C++ -*- |
---|
| 2 | * |
---|
| 3 | * This file is a part of LEMON, a generic C++ optimization library |
---|
| 4 | * |
---|
[2553] | 5 | * Copyright (C) 2003-2008 |
---|
[2335] | 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 _Graph, typename _PredMap> |
---|
| 25 | class PredMapPath { |
---|
| 26 | public: |
---|
| 27 | typedef True RevPathTag; |
---|
| 28 | |
---|
| 29 | typedef _Graph Graph; |
---|
| 30 | typedef typename Graph::Edge Edge; |
---|
| 31 | typedef _PredMap PredMap; |
---|
| 32 | |
---|
| 33 | PredMapPath(const Graph& _graph, const PredMap& _predMap, |
---|
| 34 | typename Graph::Node _target) |
---|
| 35 | : graph(_graph), predMap(_predMap), target(_target) {} |
---|
| 36 | |
---|
| 37 | int length() const { |
---|
| 38 | int len = 0; |
---|
| 39 | typename Graph::Node node = target; |
---|
| 40 | typename Graph::Edge edge; |
---|
| 41 | while ((edge = predMap[node]) != INVALID) { |
---|
| 42 | node = graph.source(edge); |
---|
| 43 | ++len; |
---|
| 44 | } |
---|
| 45 | return len; |
---|
| 46 | } |
---|
| 47 | |
---|
| 48 | bool empty() const { |
---|
| 49 | return predMap[target] != INVALID; |
---|
| 50 | } |
---|
| 51 | |
---|
[2357] | 52 | class RevEdgeIt { |
---|
[2335] | 53 | public: |
---|
[2357] | 54 | RevEdgeIt() {} |
---|
| 55 | RevEdgeIt(Invalid) : path(0), current(INVALID) {} |
---|
| 56 | RevEdgeIt(const PredMapPath& _path) |
---|
[2467] | 57 | : path(&_path), current(_path.target) { |
---|
| 58 | if (path->predMap[current] == INVALID) current = INVALID; |
---|
| 59 | } |
---|
[2335] | 60 | |
---|
| 61 | operator const typename Graph::Edge() const { |
---|
| 62 | return path->predMap[current]; |
---|
| 63 | } |
---|
| 64 | |
---|
[2357] | 65 | RevEdgeIt& operator++() { |
---|
[2335] | 66 | current = path->graph.source(path->predMap[current]); |
---|
| 67 | if (path->predMap[current] == INVALID) current = INVALID; |
---|
| 68 | return *this; |
---|
| 69 | } |
---|
| 70 | |
---|
[2357] | 71 | bool operator==(const RevEdgeIt& e) const { |
---|
[2335] | 72 | return current == e.current; |
---|
| 73 | } |
---|
| 74 | |
---|
[2357] | 75 | bool operator!=(const RevEdgeIt& e) const { |
---|
[2335] | 76 | return current != e.current; |
---|
| 77 | } |
---|
| 78 | |
---|
[2357] | 79 | bool operator<(const RevEdgeIt& e) const { |
---|
[2335] | 80 | return current < e.current; |
---|
| 81 | } |
---|
| 82 | |
---|
| 83 | private: |
---|
| 84 | const PredMapPath* path; |
---|
| 85 | typename Graph::Node current; |
---|
| 86 | }; |
---|
| 87 | |
---|
| 88 | private: |
---|
| 89 | const Graph& graph; |
---|
| 90 | const PredMap& predMap; |
---|
| 91 | typename Graph::Node target; |
---|
| 92 | }; |
---|
| 93 | |
---|
| 94 | |
---|
| 95 | template <typename _Graph, typename _PredMatrixMap> |
---|
| 96 | class PredMatrixMapPath { |
---|
| 97 | public: |
---|
| 98 | typedef True RevPathTag; |
---|
| 99 | |
---|
| 100 | typedef _Graph Graph; |
---|
| 101 | typedef typename Graph::Edge Edge; |
---|
| 102 | typedef _PredMatrixMap PredMatrixMap; |
---|
| 103 | |
---|
| 104 | PredMatrixMapPath(const Graph& _graph, |
---|
| 105 | const PredMatrixMap& _predMatrixMap, |
---|
| 106 | typename Graph::Node _source, |
---|
| 107 | typename Graph::Node _target) |
---|
| 108 | : graph(_graph), predMatrixMap(_predMatrixMap), |
---|
| 109 | source(_source), target(_target) {} |
---|
| 110 | |
---|
| 111 | int length() const { |
---|
| 112 | int len = 0; |
---|
| 113 | typename Graph::Node node = target; |
---|
| 114 | typename Graph::Edge edge; |
---|
| 115 | while ((edge = predMatrixMap(source, node)) != INVALID) { |
---|
| 116 | node = graph.source(edge); |
---|
| 117 | ++len; |
---|
| 118 | } |
---|
| 119 | return len; |
---|
| 120 | } |
---|
| 121 | |
---|
| 122 | bool empty() const { |
---|
| 123 | return source != target; |
---|
| 124 | } |
---|
| 125 | |
---|
[2357] | 126 | class RevEdgeIt { |
---|
[2335] | 127 | public: |
---|
[2357] | 128 | RevEdgeIt() {} |
---|
| 129 | RevEdgeIt(Invalid) : path(0), current(INVALID) {} |
---|
| 130 | RevEdgeIt(const PredMatrixMapPath& _path) |
---|
[2467] | 131 | : path(&_path), current(_path.target) { |
---|
| 132 | if (path->predMatrixMap(path->source, current) == INVALID) |
---|
| 133 | current = INVALID; |
---|
| 134 | } |
---|
[2335] | 135 | |
---|
| 136 | operator const typename Graph::Edge() const { |
---|
| 137 | return path->predMatrixMap(path->source, current); |
---|
| 138 | } |
---|
| 139 | |
---|
[2357] | 140 | RevEdgeIt& operator++() { |
---|
[2335] | 141 | current = |
---|
| 142 | path->graph.source(path->predMatrixMap(path->source, current)); |
---|
| 143 | if (path->predMatrixMap(path->source, current) == INVALID) |
---|
| 144 | current = INVALID; |
---|
| 145 | return *this; |
---|
| 146 | } |
---|
| 147 | |
---|
[2357] | 148 | bool operator==(const RevEdgeIt& e) const { |
---|
[2335] | 149 | return current == e.current; |
---|
| 150 | } |
---|
| 151 | |
---|
[2357] | 152 | bool operator!=(const RevEdgeIt& e) const { |
---|
[2335] | 153 | return current != e.current; |
---|
| 154 | } |
---|
| 155 | |
---|
[2357] | 156 | bool operator<(const RevEdgeIt& e) const { |
---|
[2335] | 157 | return current < e.current; |
---|
| 158 | } |
---|
| 159 | |
---|
| 160 | private: |
---|
| 161 | const PredMatrixMapPath* path; |
---|
| 162 | typename Graph::Node current; |
---|
| 163 | }; |
---|
| 164 | |
---|
| 165 | private: |
---|
| 166 | const Graph& graph; |
---|
| 167 | const PredMatrixMap& predMatrixMap; |
---|
| 168 | typename Graph::Node source; |
---|
| 169 | typename Graph::Node target; |
---|
| 170 | }; |
---|
| 171 | |
---|
| 172 | } |
---|
| 173 | |
---|
| 174 | #endif |
---|