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