|
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_EDGE_LOOKUP_H |
|
20 #define LEMON_EDGE_LOOKUP_H |
|
21 |
|
22 #include<lemon/graph_utils.h> |
|
23 #include<algorithm> |
|
24 #include<vector> |
|
25 |
|
26 namespace lemon { |
|
27 template<class G> |
|
28 class EdgeLookUp2 |
|
29 { |
|
30 public: |
|
31 GRAPH_TYPEDEFS(typename G) |
|
32 typedef G Graph; |
|
33 |
|
34 private: |
|
35 const Graph &_g; |
|
36 typename Graph::template NodeMap<int> _start; |
|
37 typename Graph::template NodeMap<int> _end; |
|
38 std::vector<Edge> _edges; |
|
39 |
|
40 class EdgeLess { |
|
41 const Graph &g; |
|
42 public: |
|
43 EdgeLess(const Graph &_g) : g(_g) {} |
|
44 bool operator()(Edge a,Edge b) const |
|
45 { |
|
46 return g.target(a)<g.target(b); |
|
47 } |
|
48 }; |
|
49 |
|
50 public: |
|
51 |
|
52 ///Constructor |
|
53 EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();} |
|
54 |
|
55 public: |
|
56 ///Refresh the data structure at a node. |
|
57 void refresh(Node n) |
|
58 { |
|
59 const int bi = _start[n] = _edges.size(); |
|
60 for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e); |
|
61 const typename std::vector<Edge>::iterator ei=_edges.end(); |
|
62 _end[n]=_edges.size(); |
|
63 std::sort(_edges.begin()+bi,ei,EdgeLess(_g)); |
|
64 } |
|
65 ///Refresh the full data structure. |
|
66 void refresh() |
|
67 { |
|
68 _edges.clear(); |
|
69 for(NodeIt n(_g);n!=INVALID;++n) refresh(n); |
|
70 } |
|
71 |
|
72 ///Find an edge between two nodes. |
|
73 |
|
74 ///Find an edge between two nodes. |
|
75 ///\param s The source node |
|
76 ///\param t The target node |
|
77 ///\return An edge from \c s to \c t if there exists, |
|
78 ///\ref INVALID otherwise. |
|
79 |
|
80 Edge operator()(Node s, Node t) |
|
81 { |
|
82 int a=_start[s]; |
|
83 int b=_end[s]; |
|
84 while(a<b) |
|
85 { |
|
86 int n=(a+b)/2; |
|
87 Node tt = _g.target(_edges[n]); |
|
88 if(tt==t) return _edges[n]; |
|
89 else if(tt<t) a=n+1; |
|
90 else b=n; |
|
91 } |
|
92 return INVALID; |
|
93 } |
|
94 |
|
95 ///Find the next edge |
|
96 |
|
97 ///\warning This function is unimplemented. |
|
98 Edge operator()(Node s, Node t, Edge prev) |
|
99 { |
|
100 return prev==INVALID?(*this)(s,t):INVALID; |
|
101 } |
|
102 |
|
103 }; |
|
104 |
|
105 template<class G> |
|
106 class EdgeLookUp3 |
|
107 { |
|
108 public: |
|
109 GRAPH_TYPEDEFS(typename G) |
|
110 typedef G Graph; |
|
111 |
|
112 private: |
|
113 const Graph &_g; |
|
114 typename Graph::template NodeMap<Edge*> _start; |
|
115 typename Graph::template NodeMap<Edge*> _end; |
|
116 std::vector<Edge> _edges; |
|
117 |
|
118 class EdgeLess { |
|
119 const Graph &g; |
|
120 public: |
|
121 EdgeLess(const Graph &_g) : g(_g) {} |
|
122 bool operator()(Edge a,Edge b) const |
|
123 { |
|
124 return g.target(a)<g.target(b); |
|
125 } |
|
126 }; |
|
127 |
|
128 public: |
|
129 |
|
130 ///Constructor |
|
131 EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();} |
|
132 |
|
133 public: |
|
134 ///Refresh the data structure at a node. |
|
135 void refresh(Node n) |
|
136 { |
|
137 const int bi = _start[n] = _edges.size(); |
|
138 for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e); |
|
139 const typename std::vector<Edge>::iterator ei=_edges.end(); |
|
140 _end[n]=_edges.size(); |
|
141 std::sort(_edges.begin()+bi,ei,EdgeLess(_g)); |
|
142 } |
|
143 ///Refresh the full data structure. |
|
144 void refresh() |
|
145 { |
|
146 _edges.resize(countEdges(_g)); |
|
147 int l=0; |
|
148 for(NodeIt n(_g);n!=INVALID;++n) |
|
149 { |
|
150 int ls = l; |
|
151 _start[n]=&(_edges[l]); |
|
152 for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e; |
|
153 _end[n]=&(_edges[l]); |
|
154 std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g)); |
|
155 } |
|
156 |
|
157 } |
|
158 |
|
159 ///Find an edge between two nodes. |
|
160 |
|
161 ///Find an edge between two nodes. |
|
162 ///\param s The source node |
|
163 ///\param t The target node |
|
164 ///\return An edge from \c s to \c t if there exists, |
|
165 ///\ref INVALID otherwise. |
|
166 |
|
167 Edge operator()(Node s, Node t) |
|
168 { |
|
169 Edge *a=_start[s]; |
|
170 Edge *b=_end[s]; |
|
171 while(a!=b) |
|
172 { |
|
173 Edge *m=a+((b-a)/2); |
|
174 Node tt = _g.target(*m); |
|
175 if(tt==t) return *m; |
|
176 else if(tt<t) a=m+1; |
|
177 else b=m; |
|
178 } |
|
179 return INVALID; |
|
180 } |
|
181 |
|
182 ///Find the next edge |
|
183 |
|
184 ///\warning This function is unimplemented. |
|
185 Edge operator()(Node s, Node t, Edge prev) |
|
186 { |
|
187 return prev==INVALID?(*this)(s,t):INVALID; |
|
188 } |
|
189 |
|
190 }; |
|
191 |
|
192 template<class G> |
|
193 class EdgeLookUp4 |
|
194 { |
|
195 public: |
|
196 GRAPH_TYPEDEFS(typename G) |
|
197 typedef G Graph; |
|
198 |
|
199 private: |
|
200 const Graph &_g; |
|
201 typename Graph::template NodeMap<Edge*> _start; |
|
202 typename Graph::template NodeMap<Edge*> _end; |
|
203 std::vector<Edge> _edges; |
|
204 |
|
205 class EdgeLess { |
|
206 const Graph &g; |
|
207 public: |
|
208 EdgeLess(const Graph &_g) : g(_g) {} |
|
209 bool operator()(Edge a,Edge b) const |
|
210 { |
|
211 return g.target(a)<g.target(b); |
|
212 } |
|
213 }; |
|
214 |
|
215 public: |
|
216 |
|
217 ///Constructor |
|
218 EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();} |
|
219 |
|
220 public: |
|
221 ///Refresh the data structure at a node. |
|
222 void refresh(Node n) |
|
223 { |
|
224 const int bi = _start[n] = _edges.size(); |
|
225 for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e); |
|
226 const typename std::vector<Edge>::iterator ei=_edges.end(); |
|
227 _end[n]=_edges.size(); |
|
228 std::sort(_edges.begin()+bi,ei,EdgeLess(_g)); |
|
229 } |
|
230 ///Refresh the full data structure. |
|
231 void refresh() |
|
232 { |
|
233 _edges.resize(countEdges(_g)); |
|
234 int l=0; |
|
235 for(NodeIt n(_g);n!=INVALID;++n) |
|
236 { |
|
237 int ls = l; |
|
238 _start[n]=&(_edges[l]); |
|
239 for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e; |
|
240 _end[n]=&(_edges[l]); |
|
241 std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g)); |
|
242 } |
|
243 |
|
244 } |
|
245 |
|
246 ///Find an edge between two nodes. |
|
247 |
|
248 ///Find an edge between two nodes. |
|
249 ///\param s The source node |
|
250 ///\param t The target node |
|
251 ///\return An edge from \c s to \c t if there exists, |
|
252 ///\ref INVALID otherwise. |
|
253 |
|
254 Edge operator()(Node s, Node t) |
|
255 { |
|
256 Edge *a=_start[s]; |
|
257 Edge *b=_end[s]; |
|
258 while(a!=b) |
|
259 { |
|
260 Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc); |
|
261 Node tt = _g.target(*m); |
|
262 if(tt==t) return *m; |
|
263 else if(tt<t) a=m+1; |
|
264 else b=m; |
|
265 } |
|
266 return INVALID; |
|
267 } |
|
268 |
|
269 ///Find the next edge |
|
270 |
|
271 ///\warning This function is unimplemented. |
|
272 Edge operator()(Node s, Node t, Edge prev) |
|
273 { |
|
274 return prev==INVALID?(*this)(s,t):INVALID; |
|
275 } |
|
276 |
|
277 }; |
|
278 |
|
279 } |
|
280 |
|
281 #endif |