1.1 --- a/benchmark/edge_lookup_test.h Thu Oct 12 11:09:17 2006 +0000
1.2 +++ b/benchmark/edge_lookup_test.h Thu Oct 12 11:53:31 2006 +0000
1.3 @@ -189,92 +189,92 @@
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 +// private:
1.26 +// const Graph &_g;
1.27 +// typename Graph::template NodeMap<Edge*> _start;
1.28 +// typename Graph::template NodeMap<Edge*> _end;
1.29 +// std::vector<Edge> _edges;
1.30
1.31 - class EdgeLess {
1.32 - const Graph &g;
1.33 - public:
1.34 - EdgeLess(const Graph &_g) : g(_g) {}
1.35 - bool operator()(Edge a,Edge b) const
1.36 - {
1.37 - return g.target(a)<g.target(b);
1.38 - }
1.39 - };
1.40 +// class EdgeLess {
1.41 +// const Graph &g;
1.42 +// public:
1.43 +// EdgeLess(const Graph &_g) : g(_g) {}
1.44 +// bool operator()(Edge a,Edge b) const
1.45 +// {
1.46 +// return g.target(a)<g.target(b);
1.47 +// }
1.48 +// };
1.49
1.50 - public:
1.51 +// public:
1.52
1.53 - ///Constructor
1.54 - EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
1.55 +// ///Constructor
1.56 +// EdgeLookUp4(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.resize(countEdges(_g));
1.72 - int l=0;
1.73 - for(NodeIt n(_g);n!=INVALID;++n)
1.74 - {
1.75 - int ls = l;
1.76 - _start[n]=&(_edges[l]);
1.77 - for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
1.78 - _end[n]=&(_edges[l]);
1.79 - std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
1.80 - }
1.81 +// public:
1.82 +// ///Refresh the data structure at a node.
1.83 +// void refresh(Node n)
1.84 +// {
1.85 +// const int bi = _start[n] = _edges.size();
1.86 +// for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
1.87 +// const typename std::vector<Edge>::iterator ei=_edges.end();
1.88 +// _end[n]=_edges.size();
1.89 +// std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
1.90 +// }
1.91 +// ///Refresh the full data structure.
1.92 +// void refresh()
1.93 +// {
1.94 +// _edges.resize(countEdges(_g));
1.95 +// int l=0;
1.96 +// for(NodeIt n(_g);n!=INVALID;++n)
1.97 +// {
1.98 +// int ls = l;
1.99 +// _start[n]=&(_edges[l]);
1.100 +// for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
1.101 +// _end[n]=&(_edges[l]);
1.102 +// std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
1.103 +// }
1.104
1.105 - }
1.106 +// }
1.107
1.108 - ///Find an edge between two nodes.
1.109 +// ///Find an edge between two nodes.
1.110
1.111 - ///Find an edge between two nodes.
1.112 - ///\param s The source node
1.113 - ///\param t The target node
1.114 - ///\return An edge from \c s to \c t if there exists,
1.115 - ///\ref INVALID otherwise.
1.116 +// ///Find an edge between two nodes.
1.117 +// ///\param s The source node
1.118 +// ///\param t The target node
1.119 +// ///\return An edge from \c s to \c t if there exists,
1.120 +// ///\ref INVALID otherwise.
1.121
1.122 - Edge operator()(Node s, Node t)
1.123 - {
1.124 - Edge *a=_start[s];
1.125 - Edge *b=_end[s];
1.126 - while(a!=b)
1.127 - {
1.128 - Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
1.129 - Node tt = _g.target(*m);
1.130 - if(tt==t) return *m;
1.131 - else if(tt<t) a=m+1;
1.132 - else b=m;
1.133 - }
1.134 - return INVALID;
1.135 - }
1.136 +// Edge operator()(Node s, Node t)
1.137 +// {
1.138 +// Edge *a=_start[s];
1.139 +// Edge *b=_end[s];
1.140 +// while(a!=b)
1.141 +// {
1.142 +// Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
1.143 +// Node tt = _g.target(*m);
1.144 +// if(tt==t) return *m;
1.145 +// else if(tt<t) a=m+1;
1.146 +// else b=m;
1.147 +// }
1.148 +// return INVALID;
1.149 +// }
1.150
1.151 - ///Find the next edge
1.152 +// ///Find the next edge
1.153
1.154 - ///\warning This function is unimplemented.
1.155 - Edge operator()(Node s, Node t, Edge prev)
1.156 - {
1.157 - return prev==INVALID?(*this)(s,t):INVALID;
1.158 - }
1.159 +// ///\warning This function is unimplemented.
1.160 +// Edge operator()(Node s, Node t, Edge prev)
1.161 +// {
1.162 +// return prev==INVALID?(*this)(s,t):INVALID;
1.163 +// }
1.164
1.165 - };
1.166 +// };
1.167
1.168 }
1.169