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