COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/edge_lookup_test.h @ 2252:133028e83940

Last change on this file since 2252:133028e83940 was 2252:133028e83940, checked in by Alpar Juttner, 13 years ago

A trial to make the last test platform independent.

File size: 6.6 KB
Line 
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
26namespace 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#ifdef X86
261          Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
262#elif X86_64
263          Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc);
264#else
265          Edge *m=a+((b-a)/2);
266#endif
267          Node tt = _g.target(*m);
268          if(tt==t) return *m;
269          else if(tt<t) a=m+1;
270          else b=m;
271        }
272      return INVALID;
273    }
274
275    ///Find the next edge
276     
277      ///\warning This function is unimplemented.
278    Edge operator()(Node s, Node t, Edge prev)
279    {
280      return prev==INVALID?(*this)(s,t):INVALID;
281    }
282     
283  };
284
285}
286
287#endif
Note: See TracBrowser for help on using the repository browser.