Consider the CPXMIP_OPTIMAL_TOL status as OPTIMAL too.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
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 #include<lemon/smart_graph.h>
21 #include<lemon/time_measure.h>
22 #include<lemon/random.h>
23 #include<lemon/graph_utils.h>
26 using namespace lemon;
32 GRAPH_TYPEDEFS(typename G)
37 typename Graph::template NodeMap<int> _start;
38 typename Graph::template NodeMap<int> _end;
39 std::vector<Edge> _edges;
44 EdgeLess(const Graph &_g) : g(_g) {}
45 bool operator()(Edge a,Edge b) const
47 return g.target(a)<g.target(b);
54 EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
57 ///Refresh the data structure at a node.
60 const int bi = _start[n] = _edges.size();
61 for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
62 const typename std::vector<Edge>::iterator ei=_edges.end();
63 _end[n]=_edges.size();
64 std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
66 ///Refresh the full data structure.
70 for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
73 ///Find an edge between two nodes.
75 ///Find an edge between two nodes.
76 ///\param s The source node
77 ///\param t The target node
78 ///\return An edge from \c s to \c t if there exists,
79 ///\ref INVALID otherwise.
81 Edge operator()(Node s, Node t)
88 Node tt = _g.target(_edges[n]);
89 if(tt==t) return _edges[n];
98 ///\warning This function is unimplemented.
99 Edge operator()(Node s, Node t, Edge prev)
101 return prev==INVALID?(*this)(s,t):INVALID;
110 GRAPH_TYPEDEFS(typename G)
115 typename Graph::template NodeMap<Edge*> _start;
116 typename Graph::template NodeMap<Edge*> _end;
117 std::vector<Edge> _edges;
122 EdgeLess(const Graph &_g) : g(_g) {}
123 bool operator()(Edge a,Edge b) const
125 return g.target(a)<g.target(b);
132 EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
135 ///Refresh the data structure at a node.
138 const int bi = _start[n] = _edges.size();
139 for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
140 const typename std::vector<Edge>::iterator ei=_edges.end();
141 _end[n]=_edges.size();
142 std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
144 ///Refresh the full data structure.
147 _edges.resize(countEdges(_g));
149 for(NodeIt n(_g);n!=INVALID;++n)
152 _start[n]=&(_edges[l]);
153 for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
154 _end[n]=&(_edges[l]);
155 std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
160 ///Find an edge between two nodes.
162 ///Find an edge between two nodes.
163 ///\param s The source node
164 ///\param t The target node
165 ///\return An edge from \c s to \c t if there exists,
166 ///\ref INVALID otherwise.
168 Edge operator()(Node s, Node t)
175 Node tt = _g.target(*m);
183 ///Find the next edge
185 ///\warning This function is unimplemented.
186 Edge operator()(Node s, Node t, Edge prev)
188 return prev==INVALID?(*this)(s,t):INVALID;
197 // GRAPH_TYPEDEFS(typename G)
202 // typename Graph::template NodeMap<Edge*> _start;
203 // typename Graph::template NodeMap<Edge*> _end;
204 // std::vector<Edge> _edges;
209 // EdgeLess(const Graph &_g) : g(_g) {}
210 // bool operator()(Edge a,Edge b) const
212 // return g.target(a)<g.target(b);
219 // EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
222 // ///Refresh the data structure at a node.
223 // void refresh(Node n)
225 // const int bi = _start[n] = _edges.size();
226 // for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
227 // const typename std::vector<Edge>::iterator ei=_edges.end();
228 // _end[n]=_edges.size();
229 // std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
231 // ///Refresh the full data structure.
234 // _edges.resize(countEdges(_g));
236 // for(NodeIt n(_g);n!=INVALID;++n)
239 // _start[n]=&(_edges[l]);
240 // for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
241 // _end[n]=&(_edges[l]);
242 // std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
247 // ///Find an edge between two nodes.
249 // ///Find an edge between two nodes.
250 // ///\param s The source node
251 // ///\param t The target node
252 // ///\return An edge from \c s to \c t if there exists,
253 // ///\ref INVALID otherwise.
255 // Edge operator()(Node s, Node t)
257 // Edge *a=_start[s];
262 // Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
264 // // Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc);
266 // // Edge *m=a+((b-a)/2);
268 // Node tt = _g.target(*m);
269 // if(tt==t) return *m;
270 // else if(tt<t) a=m+1;
276 // ///Find the next edge
278 // ///\warning This function is unimplemented.
279 // Edge operator()(Node s, Node t, Edge prev)
281 // return prev==INVALID?(*this)(s,t):INVALID;
290 // GRAPH_TYPEDEFS(typename G)
295 // typename Graph::template NodeMap<Edge*> _start;
296 // typename Graph::template NodeMap<Edge*> _end;
297 // std::vector<Edge> _edges;
302 // EdgeLess(const Graph &_g) : g(_g) {}
303 // bool operator()(Edge a,Edge b) const
305 // return g.target(a)<g.target(b);
312 // EdgeLookUp5(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
315 // ///Refresh the data structure at a node.
316 // void refresh(Node n)
318 // const int bi = _start[n] = _edges.size();
319 // for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
320 // const typename std::vector<Edge>::iterator ei=_edges.end();
321 // _end[n]=_edges.size();
322 // std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
324 // ///Refresh the full data structure.
327 // _edges.resize(countEdges(_g));
329 // for(NodeIt n(_g);n!=INVALID;++n)
332 // _start[n]=&(_edges[l]);
333 // for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
334 // _end[n]=&(_edges[l]);
335 // std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
340 // ///Find an edge between two nodes.
342 // ///Find an edge between two nodes.
343 // ///\param s The source node
344 // ///\param t The target node
345 // ///\return An edge from \c s to \c t if there exists,
346 // ///\ref INVALID otherwise.
348 // Edge operator()(Node s, Node t)
350 // Edge *a=_start[s];
355 // Edge *m=(Edge*)((((unsigned int)a>>1)+((unsigned int)b)>>1)
358 // // Edge *m=(Edge*)(((unsigned long)a>>1+(undigned long)b)>>1)&0xfffffffc);
360 // // Edge *m=a+((b-a)/2);
362 // Node tt = _g.target(*m);
363 // if(tt==t) return *m;
364 // else if(tt<t) a=m+1;
370 // ///Find the next edge
372 // ///\warning This function is unimplemented.
373 // Edge operator()(Node s, Node t, Edge prev)
375 // return prev==INVALID?(*this)(s,t):INVALID;
380 GRAPH_TYPEDEFS(SmartGraph)
381 typedef SmartGraph Graph;
387 FE(Graph &g) :_g(g) {}
392 for(NodeIt v(_g);v!=INVALID;++v)
393 for(NodeIt u(_g);u!=INVALID;++u)
403 EdgeLookUp<Graph> _el;
404 EL(Graph &g) :_g(g), _el(g) {}
409 for(NodeIt v(_g);v!=INVALID;++v)
410 for(NodeIt u(_g);u!=INVALID;++u)
419 EdgeLookUp2<Graph> _el;
420 EL2(Graph &g) :_g(g), _el(g) {}
425 for(NodeIt v(_g);v!=INVALID;++v)
426 for(NodeIt u(_g);u!=INVALID;++u)
436 EdgeLookUp3<Graph> _el;
437 EL3(Graph &g) :_g(g), _el(g) {}
442 for(NodeIt v(_g);v!=INVALID;++v)
443 for(NodeIt u(_g);u!=INVALID;++u)
453 // EdgeLookUp4<Graph> _el;
454 // EL4(Graph &g) :_g(g), _el(g) {}
459 // for(NodeIt v(_g);v!=INVALID;++v)
460 // for(NodeIt u(_g);u!=INVALID;++u)
470 // EdgeLookUp5<Graph> _el;
471 // EL5(Graph &g) :_g(g), _el(g) {}
476 // for(NodeIt v(_g);v!=INVALID;++v)
477 // for(NodeIt u(_g);u!=INVALID;++u)
483 int main(int, char**argv)
486 int M=int(N*atof(argv[2]));
491 for(int i=0;i<N;i++) v.push_back(g.addNode());
492 for(int i=0;i<M;i++) g.addEdge(v[rnd[N]],v[rnd[N]]);
497 // TimeReport t("findEdge: ");
498 // for(NodeIt u(g);u!=INVALID;++u)
499 // for(NodeIt v(g);v!=INVALID;++v)
500 // e=findEdge(g,u,v);
504 // EdgeLookUp<Graph> el(g);
506 // TimeReport t("EdgeLookUp: ");
507 // for(NodeIt u(g);u!=INVALID;++u)
508 // for(NodeIt v(g);v!=INVALID;++v)
513 TimeStamp t1 = runningTimeTest(FE(g),1);
514 TimeStamp t2 = runningTimeTest(EL(g),1);
515 TimeStamp t3 = runningTimeTest(EL2(g),1);
516 TimeStamp t4 = runningTimeTest(EL3(g),1);
517 // TimeStamp t5 = runningTimeTest(EL4(g),1);
518 // TimeStamp t6 = runningTimeTest(EL5(g),1);
520 std::cout << t1.userTime()/N/N << ' '
521 << t2.userTime()/N/N << ' '
522 << t3.userTime()/N/N << ' '
523 << t4.userTime()/N/N << ' '
524 // << t5.userTime()/N/N << ' '
525 // << t6.userTime()/N/N