A trial to make the last test platform independent.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_EDGE_LOOKUP_H
20 #define LEMON_EDGE_LOOKUP_H
22 #include<lemon/graph_utils.h>
31 GRAPH_TYPEDEFS(typename G)
36 typename Graph::template NodeMap<int> _start;
37 typename Graph::template NodeMap<int> _end;
38 std::vector<Edge> _edges;
43 EdgeLess(const Graph &_g) : g(_g) {}
44 bool operator()(Edge a,Edge b) const
46 return g.target(a)<g.target(b);
53 EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
56 ///Refresh the data structure at a node.
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));
65 ///Refresh the full data structure.
69 for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
72 ///Find an edge between two nodes.
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.
80 Edge operator()(Node s, Node t)
87 Node tt = _g.target(_edges[n]);
88 if(tt==t) return _edges[n];
97 ///\warning This function is unimplemented.
98 Edge operator()(Node s, Node t, Edge prev)
100 return prev==INVALID?(*this)(s,t):INVALID;
109 GRAPH_TYPEDEFS(typename G)
114 typename Graph::template NodeMap<Edge*> _start;
115 typename Graph::template NodeMap<Edge*> _end;
116 std::vector<Edge> _edges;
121 EdgeLess(const Graph &_g) : g(_g) {}
122 bool operator()(Edge a,Edge b) const
124 return g.target(a)<g.target(b);
131 EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
134 ///Refresh the data structure at a node.
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));
143 ///Refresh the full data structure.
146 _edges.resize(countEdges(_g));
148 for(NodeIt n(_g);n!=INVALID;++n)
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));
159 ///Find an edge between two nodes.
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.
167 Edge operator()(Node s, Node t)
174 Node tt = _g.target(*m);
182 ///Find the next edge
184 ///\warning This function is unimplemented.
185 Edge operator()(Node s, Node t, Edge prev)
187 return prev==INVALID?(*this)(s,t):INVALID;
196 GRAPH_TYPEDEFS(typename G)
201 typename Graph::template NodeMap<Edge*> _start;
202 typename Graph::template NodeMap<Edge*> _end;
203 std::vector<Edge> _edges;
208 EdgeLess(const Graph &_g) : g(_g) {}
209 bool operator()(Edge a,Edge b) const
211 return g.target(a)<g.target(b);
218 EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
221 ///Refresh the data structure at a node.
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));
230 ///Refresh the full data structure.
233 _edges.resize(countEdges(_g));
235 for(NodeIt n(_g);n!=INVALID;++n)
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));
246 ///Find an edge between two nodes.
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.
254 Edge operator()(Node s, Node t)
261 Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
263 Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc);
267 Node tt = _g.target(*m);
275 ///Find the next edge
277 ///\warning This function is unimplemented.
278 Edge operator()(Node s, Node t, Edge prev)
280 return prev==INVALID?(*this)(s,t):INVALID;