1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/benchmark/edge_lookup_test.h Thu Oct 12 10:53:25 2006 +0000
1.3 @@ -0,0 +1,281 @@
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 + Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
1.264 + Node tt = _g.target(*m);
1.265 + if(tt==t) return *m;
1.266 + else if(tt<t) a=m+1;
1.267 + else b=m;
1.268 + }
1.269 + return INVALID;
1.270 + }
1.271 +
1.272 + ///Find the next edge
1.273 +
1.274 + ///\warning This function is unimplemented.
1.275 + Edge operator()(Node s, Node t, Edge prev)
1.276 + {
1.277 + return prev==INVALID?(*this)(s,t):INVALID;
1.278 + }
1.279 +
1.280 + };
1.281 +
1.282 +}
1.283 +
1.284 +#endif