# Changeset 2271:a2ab63454152 in lemon-0.x for benchmark

Ignore:
Timestamp:
10/30/06 16:23:35 (15 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3033
Message:

repository cleanup

Location:
benchmark
Files:
1 deleted
1 edited

Unmodified
Added
Removed
• ## benchmark/edge_lookup.cc

 r2252 #include"edge_lookup_test.h" #include #include #include #include #include #include using namespace lemon; template class EdgeLookUp2 { public: GRAPH_TYPEDEFS(typename G) typedef G Graph; private: const Graph &_g; typename Graph::template NodeMap _start; typename Graph::template NodeMap _end; std::vector _edges; class EdgeLess { const Graph &g; public: EdgeLess(const Graph &_g) : g(_g) {} bool operator()(Edge a,Edge b) const { return g.target(a)::iterator ei=_edges.end(); _end[n]=_edges.size(); std::sort(_edges.begin()+bi,ei,EdgeLess(_g)); } ///Refresh the full data structure. void refresh() { _edges.clear(); for(NodeIt n(_g);n!=INVALID;++n) refresh(n); } ///Find an edge between two nodes. ///Find an edge between two nodes. ///\param s The source node ///\param t The target node ///\return An edge from \c s to \c t if there exists, ///\ref INVALID otherwise. Edge operator()(Node s, Node t) { int a=_start[s]; int b=_end[s]; while(a class EdgeLookUp3 { public: GRAPH_TYPEDEFS(typename G) typedef G Graph; private: const Graph &_g; typename Graph::template NodeMap _start; typename Graph::template NodeMap _end; std::vector _edges; class EdgeLess { const Graph &g; public: EdgeLess(const Graph &_g) : g(_g) {} bool operator()(Edge a,Edge b) const { return g.target(a)::iterator ei=_edges.end(); _end[n]=_edges.size(); std::sort(_edges.begin()+bi,ei,EdgeLess(_g)); } ///Refresh the full data structure. void refresh() { _edges.resize(countEdges(_g)); int l=0; for(NodeIt n(_g);n!=INVALID;++n) { int ls = l; _start[n]=&(_edges[l]); for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e; _end[n]=&(_edges[l]); std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g)); } } ///Find an edge between two nodes. ///Find an edge between two nodes. ///\param s The source node ///\param t The target node ///\return An edge from \c s to \c t if there exists, ///\ref INVALID otherwise. Edge operator()(Node s, Node t) { Edge *a=_start[s]; Edge *b=_end[s]; while(a!=b) { Edge *m=a+((b-a)/2); Node tt = _g.target(*m); if(tt==t) return *m; else if(tt class EdgeLookUp4 { public: GRAPH_TYPEDEFS(typename G) typedef G Graph; private: const Graph &_g; typename Graph::template NodeMap _start; typename Graph::template NodeMap _end; std::vector _edges; class EdgeLess { const Graph &g; public: EdgeLess(const Graph &_g) : g(_g) {} bool operator()(Edge a,Edge b) const { return g.target(a)::iterator ei=_edges.end(); _end[n]=_edges.size(); std::sort(_edges.begin()+bi,ei,EdgeLess(_g)); } ///Refresh the full data structure. void refresh() { _edges.resize(countEdges(_g)); int l=0; for(NodeIt n(_g);n!=INVALID;++n) { int ls = l; _start[n]=&(_edges[l]); for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e; _end[n]=&(_edges[l]); std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g)); } } ///Find an edge between two nodes. ///Find an edge between two nodes. ///\param s The source node ///\param t The target node ///\return An edge from \c s to \c t if there exists, ///\ref INVALID otherwise. Edge operator()(Node s, Node t) { Edge *a=_start[s]; Edge *b=_end[s]; while(a!=b) { // #ifdef X86 Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc); // #elif X86_64 //        Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc); // #else //        Edge *m=a+((b-a)/2); // #endif Node tt = _g.target(*m); if(tt==t) return *m; else if(tt class EdgeLookUp5 { public: GRAPH_TYPEDEFS(typename G) typedef G Graph; private: const Graph &_g; typename Graph::template NodeMap _start; typename Graph::template NodeMap _end; std::vector _edges; class EdgeLess { const Graph &g; public: EdgeLess(const Graph &_g) : g(_g) {} bool operator()(Edge a,Edge b) const { return g.target(a)::iterator ei=_edges.end(); _end[n]=_edges.size(); std::sort(_edges.begin()+bi,ei,EdgeLess(_g)); } ///Refresh the full data structure. void refresh() { _edges.resize(countEdges(_g)); int l=0; for(NodeIt n(_g);n!=INVALID;++n) { int ls = l; _start[n]=&(_edges[l]); for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e; _end[n]=&(_edges[l]); std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g)); } } ///Find an edge between two nodes. ///Find an edge between two nodes. ///\param s The source node ///\param t The target node ///\return An edge from \c s to \c t if there exists, ///\ref INVALID otherwise. Edge operator()(Node s, Node t) { Edge *a=_start[s]; Edge *b=_end[s]; while(a!=b) { // #ifdef X86 Edge *m=(Edge*)((((unsigned int)a>>1)+((unsigned int)b)>>1) & 0xfffffffc); // #elif X86_64 //        Edge *m=(Edge*)(((unsigned long)a>>1+(undigned long)b)>>1)&0xfffffffc); // #else //        Edge *m=a+((b-a)/2); // #endif Node tt = _g.target(*m); if(tt==t) return *m; else if(tt _el; EL4(Graph &g) :_g(g), _el(g) {} void operator()() { Edge e; for(NodeIt v(_g);v!=INVALID;++v) for(NodeIt u(_g);u!=INVALID;++u) e=_el(u,v); } }; class EL5 { public: Graph &_g; EdgeLookUp5 _el; EL5(Graph &g) :_g(g), _el(g) {} void operator()() { TimeStamp t3 = runningTimeTest(EL2(g),1); TimeStamp t4 = runningTimeTest(EL3(g),1); //   TimeStamp t5 = runningTimeTest(EL4(g),1); TimeStamp t5 = runningTimeTest(EL4(g),1); TimeStamp t6 = runningTimeTest(EL5(g),1); std::cout << t1.userTime()/N/N << ' ' << t3.userTime()/N/N << ' ' << t4.userTime()/N/N << ' ' //          << t5.userTime()/N/N << t5.userTime()/N/N << ' ' << t6.userTime()/N/N << std::endl; }
Note: See TracChangeset for help on using the changeset viewer.