1.1 --- a/benchmark/edge_lookup.cc Tue Oct 17 11:02:05 2006 +0000
1.2 +++ b/benchmark/edge_lookup.cc Tue Oct 17 11:02:30 2006 +0000
1.3 @@ -75,22 +75,22 @@
1.4
1.5 };
1.6
1.7 -// class EL4
1.8 -// {
1.9 -// public:
1.10 -// Graph &_g;
1.11 -// EdgeLookUp4<Graph> _el;
1.12 -// EL4(Graph &g) :_g(g), _el(g) {}
1.13 -// void operator()()
1.14 -// {
1.15 -// Edge e;
1.16 +class EL4
1.17 +{
1.18 +public:
1.19 + Graph &_g;
1.20 + EdgeLookUp4<Graph> _el;
1.21 + EL4(Graph &g) :_g(g), _el(g) {}
1.22 + void operator()()
1.23 + {
1.24 + Edge e;
1.25
1.26 -// for(NodeIt v(_g);v!=INVALID;++v)
1.27 -// for(NodeIt u(_g);u!=INVALID;++u)
1.28 -// e=_el(u,v);
1.29 -// }
1.30 + for(NodeIt v(_g);v!=INVALID;++v)
1.31 + for(NodeIt u(_g);u!=INVALID;++u)
1.32 + e=_el(u,v);
1.33 + }
1.34
1.35 -// };
1.36 +};
1.37
1.38 int main(int, char**argv)
1.39 {
2.1 --- a/benchmark/edge_lookup_test.h Tue Oct 17 11:02:05 2006 +0000
2.2 +++ b/benchmark/edge_lookup_test.h Tue Oct 17 11:02:30 2006 +0000
2.3 @@ -189,92 +189,98 @@
2.4
2.5 };
2.6
2.7 -// template<class G>
2.8 -// class EdgeLookUp4
2.9 -// {
2.10 -// public:
2.11 -// GRAPH_TYPEDEFS(typename G)
2.12 -// typedef G Graph;
2.13 + template<class G>
2.14 + class EdgeLookUp4
2.15 + {
2.16 + public:
2.17 + GRAPH_TYPEDEFS(typename G)
2.18 + typedef G Graph;
2.19 +
2.20 + private:
2.21 + const Graph &_g;
2.22 + typename Graph::template NodeMap<Edge*> _start;
2.23 + typename Graph::template NodeMap<Edge*> _end;
2.24 + std::vector<Edge> _edges;
2.25 +
2.26 + class EdgeLess {
2.27 + const Graph &g;
2.28 + public:
2.29 + EdgeLess(const Graph &_g) : g(_g) {}
2.30 + bool operator()(Edge a,Edge b) const
2.31 + {
2.32 + return g.target(a)<g.target(b);
2.33 + }
2.34 + };
2.35 +
2.36 + public:
2.37 +
2.38 + ///Constructor
2.39 + EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
2.40 +
2.41 + public:
2.42 + ///Refresh the data structure at a node.
2.43 + void refresh(Node n)
2.44 + {
2.45 + const int bi = _start[n] = _edges.size();
2.46 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
2.47 + const typename std::vector<Edge>::iterator ei=_edges.end();
2.48 + _end[n]=_edges.size();
2.49 + std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
2.50 + }
2.51 + ///Refresh the full data structure.
2.52 + void refresh()
2.53 + {
2.54 + _edges.resize(countEdges(_g));
2.55 + int l=0;
2.56 + for(NodeIt n(_g);n!=INVALID;++n)
2.57 + {
2.58 + int ls = l;
2.59 + _start[n]=&(_edges[l]);
2.60 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
2.61 + _end[n]=&(_edges[l]);
2.62 + std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
2.63 + }
2.64 +
2.65 + }
2.66 +
2.67 + ///Find an edge between two nodes.
2.68 +
2.69 + ///Find an edge between two nodes.
2.70 + ///\param s The source node
2.71 + ///\param t The target node
2.72 + ///\return An edge from \c s to \c t if there exists,
2.73 + ///\ref INVALID otherwise.
2.74
2.75 -// private:
2.76 -// const Graph &_g;
2.77 -// typename Graph::template NodeMap<Edge*> _start;
2.78 -// typename Graph::template NodeMap<Edge*> _end;
2.79 -// std::vector<Edge> _edges;
2.80 -
2.81 -// class EdgeLess {
2.82 -// const Graph &g;
2.83 -// public:
2.84 -// EdgeLess(const Graph &_g) : g(_g) {}
2.85 -// bool operator()(Edge a,Edge b) const
2.86 -// {
2.87 -// return g.target(a)<g.target(b);
2.88 -// }
2.89 -// };
2.90 -
2.91 -// public:
2.92 -
2.93 -// ///Constructor
2.94 -// EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
2.95 -
2.96 -// public:
2.97 -// ///Refresh the data structure at a node.
2.98 -// void refresh(Node n)
2.99 -// {
2.100 -// const int bi = _start[n] = _edges.size();
2.101 -// for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
2.102 -// const typename std::vector<Edge>::iterator ei=_edges.end();
2.103 -// _end[n]=_edges.size();
2.104 -// std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
2.105 -// }
2.106 -// ///Refresh the full data structure.
2.107 -// void refresh()
2.108 -// {
2.109 -// _edges.resize(countEdges(_g));
2.110 -// int l=0;
2.111 -// for(NodeIt n(_g);n!=INVALID;++n)
2.112 -// {
2.113 -// int ls = l;
2.114 -// _start[n]=&(_edges[l]);
2.115 -// for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
2.116 -// _end[n]=&(_edges[l]);
2.117 -// std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
2.118 -// }
2.119 + Edge operator()(Node s, Node t)
2.120 + {
2.121 + Edge *a=_start[s];
2.122 + Edge *b=_end[s];
2.123 + while(a!=b)
2.124 + {
2.125 +#ifdef X86
2.126 + Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
2.127 +#elif X86_64
2.128 + Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc);
2.129 +#else
2.130 + Edge *m=a+((b-a)/2);
2.131 +#endif
2.132 + Node tt = _g.target(*m);
2.133 + if(tt==t) return *m;
2.134 + else if(tt<t) a=m+1;
2.135 + else b=m;
2.136 + }
2.137 + return INVALID;
2.138 + }
2.139 +
2.140 + ///Find the next edge
2.141
2.142 -// }
2.143 -
2.144 -// ///Find an edge between two nodes.
2.145 -
2.146 -// ///Find an edge between two nodes.
2.147 -// ///\param s The source node
2.148 -// ///\param t The target node
2.149 -// ///\return An edge from \c s to \c t if there exists,
2.150 -// ///\ref INVALID otherwise.
2.151 -
2.152 -// Edge operator()(Node s, Node t)
2.153 -// {
2.154 -// Edge *a=_start[s];
2.155 -// Edge *b=_end[s];
2.156 -// while(a!=b)
2.157 -// {
2.158 -// Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
2.159 -// Node tt = _g.target(*m);
2.160 -// if(tt==t) return *m;
2.161 -// else if(tt<t) a=m+1;
2.162 -// else b=m;
2.163 -// }
2.164 -// return INVALID;
2.165 -// }
2.166 -
2.167 -// ///Find the next edge
2.168 + ///\warning This function is unimplemented.
2.169 + Edge operator()(Node s, Node t, Edge prev)
2.170 + {
2.171 + return prev==INVALID?(*this)(s,t):INVALID;
2.172 + }
2.173
2.174 -// ///\warning This function is unimplemented.
2.175 -// Edge operator()(Node s, Node t, Edge prev)
2.176 -// {
2.177 -// return prev==INVALID?(*this)(s,t):INVALID;
2.178 -// }
2.179 -
2.180 -// };
2.181 + };
2.182
2.183 }
2.184