1.1 --- a/benchmark/edge_lookup_test.h Tue Oct 17 11:02:05 2006 +0000
1.2 +++ b/benchmark/edge_lookup_test.h Tue Oct 17 11:02:30 2006 +0000
1.3 @@ -189,92 +189,98 @@
1.4
1.5 };
1.6
1.7 -// template<class G>
1.8 -// class EdgeLookUp4
1.9 -// {
1.10 -// public:
1.11 -// GRAPH_TYPEDEFS(typename G)
1.12 -// typedef G Graph;
1.13 + template<class G>
1.14 + class EdgeLookUp4
1.15 + {
1.16 + public:
1.17 + GRAPH_TYPEDEFS(typename G)
1.18 + typedef G Graph;
1.19 +
1.20 + private:
1.21 + const Graph &_g;
1.22 + typename Graph::template NodeMap<Edge*> _start;
1.23 + typename Graph::template NodeMap<Edge*> _end;
1.24 + std::vector<Edge> _edges;
1.25 +
1.26 + class EdgeLess {
1.27 + const Graph &g;
1.28 + public:
1.29 + EdgeLess(const Graph &_g) : g(_g) {}
1.30 + bool operator()(Edge a,Edge b) const
1.31 + {
1.32 + return g.target(a)<g.target(b);
1.33 + }
1.34 + };
1.35 +
1.36 + public:
1.37 +
1.38 + ///Constructor
1.39 + EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
1.40 +
1.41 + public:
1.42 + ///Refresh the data structure at a node.
1.43 + void refresh(Node n)
1.44 + {
1.45 + const int bi = _start[n] = _edges.size();
1.46 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
1.47 + const typename std::vector<Edge>::iterator ei=_edges.end();
1.48 + _end[n]=_edges.size();
1.49 + std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
1.50 + }
1.51 + ///Refresh the full data structure.
1.52 + void refresh()
1.53 + {
1.54 + _edges.resize(countEdges(_g));
1.55 + int l=0;
1.56 + for(NodeIt n(_g);n!=INVALID;++n)
1.57 + {
1.58 + int ls = l;
1.59 + _start[n]=&(_edges[l]);
1.60 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
1.61 + _end[n]=&(_edges[l]);
1.62 + std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
1.63 + }
1.64 +
1.65 + }
1.66 +
1.67 + ///Find an edge between two nodes.
1.68 +
1.69 + ///Find an edge between two nodes.
1.70 + ///\param s The source node
1.71 + ///\param t The target node
1.72 + ///\return An edge from \c s to \c t if there exists,
1.73 + ///\ref INVALID otherwise.
1.74
1.75 -// private:
1.76 -// const Graph &_g;
1.77 -// typename Graph::template NodeMap<Edge*> _start;
1.78 -// typename Graph::template NodeMap<Edge*> _end;
1.79 -// std::vector<Edge> _edges;
1.80 -
1.81 -// class EdgeLess {
1.82 -// const Graph &g;
1.83 -// public:
1.84 -// EdgeLess(const Graph &_g) : g(_g) {}
1.85 -// bool operator()(Edge a,Edge b) const
1.86 -// {
1.87 -// return g.target(a)<g.target(b);
1.88 -// }
1.89 -// };
1.90 -
1.91 -// public:
1.92 -
1.93 -// ///Constructor
1.94 -// EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
1.95 -
1.96 -// public:
1.97 -// ///Refresh the data structure at a node.
1.98 -// void refresh(Node n)
1.99 -// {
1.100 -// const int bi = _start[n] = _edges.size();
1.101 -// for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
1.102 -// const typename std::vector<Edge>::iterator ei=_edges.end();
1.103 -// _end[n]=_edges.size();
1.104 -// std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
1.105 -// }
1.106 -// ///Refresh the full data structure.
1.107 -// void refresh()
1.108 -// {
1.109 -// _edges.resize(countEdges(_g));
1.110 -// int l=0;
1.111 -// for(NodeIt n(_g);n!=INVALID;++n)
1.112 -// {
1.113 -// int ls = l;
1.114 -// _start[n]=&(_edges[l]);
1.115 -// for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
1.116 -// _end[n]=&(_edges[l]);
1.117 -// std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
1.118 -// }
1.119 + Edge operator()(Node s, Node t)
1.120 + {
1.121 + Edge *a=_start[s];
1.122 + Edge *b=_end[s];
1.123 + while(a!=b)
1.124 + {
1.125 +#ifdef X86
1.126 + Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
1.127 +#elif X86_64
1.128 + Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc);
1.129 +#else
1.130 + Edge *m=a+((b-a)/2);
1.131 +#endif
1.132 + Node tt = _g.target(*m);
1.133 + if(tt==t) return *m;
1.134 + else if(tt<t) a=m+1;
1.135 + else b=m;
1.136 + }
1.137 + return INVALID;
1.138 + }
1.139 +
1.140 + ///Find the next edge
1.141
1.142 -// }
1.143 -
1.144 -// ///Find an edge between two nodes.
1.145 -
1.146 -// ///Find an edge between two nodes.
1.147 -// ///\param s The source node
1.148 -// ///\param t The target node
1.149 -// ///\return An edge from \c s to \c t if there exists,
1.150 -// ///\ref INVALID otherwise.
1.151 -
1.152 -// Edge operator()(Node s, Node t)
1.153 -// {
1.154 -// Edge *a=_start[s];
1.155 -// Edge *b=_end[s];
1.156 -// while(a!=b)
1.157 -// {
1.158 -// Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
1.159 -// Node tt = _g.target(*m);
1.160 -// if(tt==t) return *m;
1.161 -// else if(tt<t) a=m+1;
1.162 -// else b=m;
1.163 -// }
1.164 -// return INVALID;
1.165 -// }
1.166 -
1.167 -// ///Find the next edge
1.168 + ///\warning This function is unimplemented.
1.169 + Edge operator()(Node s, Node t, Edge prev)
1.170 + {
1.171 + return prev==INVALID?(*this)(s,t):INVALID;
1.172 + }
1.173
1.174 -// ///\warning This function is unimplemented.
1.175 -// Edge operator()(Node s, Node t, Edge prev)
1.176 -// {
1.177 -// return prev==INVALID?(*this)(s,t):INVALID;
1.178 -// }
1.179 -
1.180 -// };
1.181 + };
1.182
1.183 }
1.184