[209] | 1 | /* -*- mode: C++; indent-tabs-mode: nil; -*- |
---|
[100] | 2 | * |
---|
[209] | 3 | * This file is a part of LEMON, a generic C++ optimization library. |
---|
[100] | 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) {} |
---|
[209] | 56 | RevArcIt(const PredMapPath& _path) |
---|
[100] | 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 | |
---|
[209] | 71 | bool operator==(const RevArcIt& e) const { |
---|
| 72 | return current == e.current; |
---|
[100] | 73 | } |
---|
| 74 | |
---|
| 75 | bool operator!=(const RevArcIt& e) const { |
---|
[209] | 76 | return current != e.current; |
---|
[100] | 77 | } |
---|
| 78 | |
---|
[209] | 79 | bool operator<(const RevArcIt& e) const { |
---|
| 80 | return current < e.current; |
---|
[100] | 81 | } |
---|
[209] | 82 | |
---|
[100] | 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 | |
---|
[209] | 104 | PredMatrixMapPath(const Digraph& _digraph, |
---|
[100] | 105 | const PredMatrixMap& _predMatrixMap, |
---|
[209] | 106 | typename Digraph::Node _source, |
---|
[100] | 107 | typename Digraph::Node _target) |
---|
[209] | 108 | : digraph(_digraph), predMatrixMap(_predMatrixMap), |
---|
[100] | 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) {} |
---|
[209] | 130 | RevArcIt(const PredMatrixMapPath& _path) |
---|
[100] | 131 | : path(&_path), current(_path.target) { |
---|
[209] | 132 | if (path->predMatrixMap(path->source, current) == INVALID) |
---|
[100] | 133 | current = INVALID; |
---|
| 134 | } |
---|
| 135 | |
---|
| 136 | operator const typename Digraph::Arc() const { |
---|
| 137 | return path->predMatrixMap(path->source, current); |
---|
| 138 | } |
---|
| 139 | |
---|
| 140 | RevArcIt& operator++() { |
---|
[209] | 141 | current = |
---|
[100] | 142 | path->digraph.source(path->predMatrixMap(path->source, current)); |
---|
[209] | 143 | if (path->predMatrixMap(path->source, current) == INVALID) |
---|
[100] | 144 | current = INVALID; |
---|
| 145 | return *this; |
---|
| 146 | } |
---|
| 147 | |
---|
[209] | 148 | bool operator==(const RevArcIt& e) const { |
---|
| 149 | return current == e.current; |
---|
[100] | 150 | } |
---|
| 151 | |
---|
| 152 | bool operator!=(const RevArcIt& e) const { |
---|
[209] | 153 | return current != e.current; |
---|
[100] | 154 | } |
---|
| 155 | |
---|
[209] | 156 | bool operator<(const RevArcIt& e) const { |
---|
| 157 | return current < e.current; |
---|
[100] | 158 | } |
---|
[209] | 159 | |
---|
[100] | 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 |
---|