1.1 --- a/benchmark/edge_lookup_test.h Mon Oct 30 12:25:43 2006 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,287 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - *
1.6 - * This file is a part of LEMON, a generic C++ optimization library
1.7 - *
1.8 - * Copyright (C) 2003-2006
1.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 - *
1.12 - * Permission to use, modify and distribute this software is granted
1.13 - * provided that this copyright notice appears in all copies. For
1.14 - * precise terms see the accompanying LICENSE file.
1.15 - *
1.16 - * This software is provided "AS IS" with no warranty of any kind,
1.17 - * express or implied, and with no claim as to its suitability for any
1.18 - * purpose.
1.19 - *
1.20 - */
1.21 -
1.22 -#ifndef LEMON_EDGE_LOOKUP_H
1.23 -#define LEMON_EDGE_LOOKUP_H
1.24 -
1.25 -#include<lemon/graph_utils.h>
1.26 -#include<algorithm>
1.27 -#include<vector>
1.28 -
1.29 -namespace lemon {
1.30 - template<class G>
1.31 - class EdgeLookUp2
1.32 - {
1.33 - public:
1.34 - GRAPH_TYPEDEFS(typename G)
1.35 - typedef G Graph;
1.36 -
1.37 - private:
1.38 - const Graph &_g;
1.39 - typename Graph::template NodeMap<int> _start;
1.40 - typename Graph::template NodeMap<int> _end;
1.41 - std::vector<Edge> _edges;
1.42 -
1.43 - class EdgeLess {
1.44 - const Graph &g;
1.45 - public:
1.46 - EdgeLess(const Graph &_g) : g(_g) {}
1.47 - bool operator()(Edge a,Edge b) const
1.48 - {
1.49 - return g.target(a)<g.target(b);
1.50 - }
1.51 - };
1.52 -
1.53 - public:
1.54 -
1.55 - ///Constructor
1.56 - EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
1.57 -
1.58 - public:
1.59 - ///Refresh the data structure at a node.
1.60 - void refresh(Node n)
1.61 - {
1.62 - const int bi = _start[n] = _edges.size();
1.63 - for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
1.64 - const typename std::vector<Edge>::iterator ei=_edges.end();
1.65 - _end[n]=_edges.size();
1.66 - std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
1.67 - }
1.68 - ///Refresh the full data structure.
1.69 - void refresh()
1.70 - {
1.71 - _edges.clear();
1.72 - for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
1.73 - }
1.74 -
1.75 - ///Find an edge between two nodes.
1.76 -
1.77 - ///Find an edge between two nodes.
1.78 - ///\param s The source node
1.79 - ///\param t The target node
1.80 - ///\return An edge from \c s to \c t if there exists,
1.81 - ///\ref INVALID otherwise.
1.82 -
1.83 - Edge operator()(Node s, Node t)
1.84 - {
1.85 - int a=_start[s];
1.86 - int b=_end[s];
1.87 - while(a<b)
1.88 - {
1.89 - int n=(a+b)/2;
1.90 - Node tt = _g.target(_edges[n]);
1.91 - if(tt==t) return _edges[n];
1.92 - else if(tt<t) a=n+1;
1.93 - else b=n;
1.94 - }
1.95 - return INVALID;
1.96 - }
1.97 -
1.98 - ///Find the next edge
1.99 -
1.100 - ///\warning This function is unimplemented.
1.101 - Edge operator()(Node s, Node t, Edge prev)
1.102 - {
1.103 - return prev==INVALID?(*this)(s,t):INVALID;
1.104 - }
1.105 -
1.106 - };
1.107 -
1.108 - template<class G>
1.109 - class EdgeLookUp3
1.110 - {
1.111 - public:
1.112 - GRAPH_TYPEDEFS(typename G)
1.113 - typedef G Graph;
1.114 -
1.115 - private:
1.116 - const Graph &_g;
1.117 - typename Graph::template NodeMap<Edge*> _start;
1.118 - typename Graph::template NodeMap<Edge*> _end;
1.119 - std::vector<Edge> _edges;
1.120 -
1.121 - class EdgeLess {
1.122 - const Graph &g;
1.123 - public:
1.124 - EdgeLess(const Graph &_g) : g(_g) {}
1.125 - bool operator()(Edge a,Edge b) const
1.126 - {
1.127 - return g.target(a)<g.target(b);
1.128 - }
1.129 - };
1.130 -
1.131 - public:
1.132 -
1.133 - ///Constructor
1.134 - EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
1.135 -
1.136 - public:
1.137 - ///Refresh the data structure at a node.
1.138 - void refresh(Node n)
1.139 - {
1.140 - const int bi = _start[n] = _edges.size();
1.141 - for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
1.142 - const typename std::vector<Edge>::iterator ei=_edges.end();
1.143 - _end[n]=_edges.size();
1.144 - std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
1.145 - }
1.146 - ///Refresh the full data structure.
1.147 - void refresh()
1.148 - {
1.149 - _edges.resize(countEdges(_g));
1.150 - int l=0;
1.151 - for(NodeIt n(_g);n!=INVALID;++n)
1.152 - {
1.153 - int ls = l;
1.154 - _start[n]=&(_edges[l]);
1.155 - for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
1.156 - _end[n]=&(_edges[l]);
1.157 - std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
1.158 - }
1.159 -
1.160 - }
1.161 -
1.162 - ///Find an edge between two nodes.
1.163 -
1.164 - ///Find an edge between two nodes.
1.165 - ///\param s The source node
1.166 - ///\param t The target node
1.167 - ///\return An edge from \c s to \c t if there exists,
1.168 - ///\ref INVALID otherwise.
1.169 -
1.170 - Edge operator()(Node s, Node t)
1.171 - {
1.172 - Edge *a=_start[s];
1.173 - Edge *b=_end[s];
1.174 - while(a!=b)
1.175 - {
1.176 - Edge *m=a+((b-a)/2);
1.177 - Node tt = _g.target(*m);
1.178 - if(tt==t) return *m;
1.179 - else if(tt<t) a=m+1;
1.180 - else b=m;
1.181 - }
1.182 - return INVALID;
1.183 - }
1.184 -
1.185 - ///Find the next edge
1.186 -
1.187 - ///\warning This function is unimplemented.
1.188 - Edge operator()(Node s, Node t, Edge prev)
1.189 - {
1.190 - return prev==INVALID?(*this)(s,t):INVALID;
1.191 - }
1.192 -
1.193 - };
1.194 -
1.195 - template<class G>
1.196 - class EdgeLookUp4
1.197 - {
1.198 - public:
1.199 - GRAPH_TYPEDEFS(typename G)
1.200 - typedef G Graph;
1.201 -
1.202 - private:
1.203 - const Graph &_g;
1.204 - typename Graph::template NodeMap<Edge*> _start;
1.205 - typename Graph::template NodeMap<Edge*> _end;
1.206 - std::vector<Edge> _edges;
1.207 -
1.208 - class EdgeLess {
1.209 - const Graph &g;
1.210 - public:
1.211 - EdgeLess(const Graph &_g) : g(_g) {}
1.212 - bool operator()(Edge a,Edge b) const
1.213 - {
1.214 - return g.target(a)<g.target(b);
1.215 - }
1.216 - };
1.217 -
1.218 - public:
1.219 -
1.220 - ///Constructor
1.221 - EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
1.222 -
1.223 - public:
1.224 - ///Refresh the data structure at a node.
1.225 - void refresh(Node n)
1.226 - {
1.227 - const int bi = _start[n] = _edges.size();
1.228 - for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
1.229 - const typename std::vector<Edge>::iterator ei=_edges.end();
1.230 - _end[n]=_edges.size();
1.231 - std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
1.232 - }
1.233 - ///Refresh the full data structure.
1.234 - void refresh()
1.235 - {
1.236 - _edges.resize(countEdges(_g));
1.237 - int l=0;
1.238 - for(NodeIt n(_g);n!=INVALID;++n)
1.239 - {
1.240 - int ls = l;
1.241 - _start[n]=&(_edges[l]);
1.242 - for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
1.243 - _end[n]=&(_edges[l]);
1.244 - std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
1.245 - }
1.246 -
1.247 - }
1.248 -
1.249 - ///Find an edge between two nodes.
1.250 -
1.251 - ///Find an edge between two nodes.
1.252 - ///\param s The source node
1.253 - ///\param t The target node
1.254 - ///\return An edge from \c s to \c t if there exists,
1.255 - ///\ref INVALID otherwise.
1.256 -
1.257 - Edge operator()(Node s, Node t)
1.258 - {
1.259 - Edge *a=_start[s];
1.260 - Edge *b=_end[s];
1.261 - while(a!=b)
1.262 - {
1.263 -#ifdef X86
1.264 - Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
1.265 -#elif X86_64
1.266 - Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc);
1.267 -#else
1.268 - Edge *m=a+((b-a)/2);
1.269 -#endif
1.270 - Node tt = _g.target(*m);
1.271 - if(tt==t) return *m;
1.272 - else if(tt<t) a=m+1;
1.273 - else b=m;
1.274 - }
1.275 - return INVALID;
1.276 - }
1.277 -
1.278 - ///Find the next edge
1.279 -
1.280 - ///\warning This function is unimplemented.
1.281 - Edge operator()(Node s, Node t, Edge prev)
1.282 - {
1.283 - return prev==INVALID?(*this)(s,t):INVALID;
1.284 - }
1.285 -
1.286 - };
1.287 -
1.288 -}
1.289 -
1.290 -#endif