COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/edge_lookup_test.h @ 2239:18c24fe93b99

Last change on this file since 2239:18c24fe93b99 was 2239:18c24fe93b99, checked in by Alpar Juttner, 14 years ago

Turn off 32bit specific tests.

File size: 6.7 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//        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
Note: See TracBrowser for help on using the repository browser.