alpar@2391: /* -*- C++ -*- alpar@2391: * alpar@2391: * This file is a part of LEMON, a generic C++ optimization library alpar@2391: * alpar@2553: * Copyright (C) 2003-2008 alpar@2391: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@2391: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@2391: * alpar@2391: * Permission to use, modify and distribute this software is granted alpar@2391: * provided that this copyright notice appears in all copies. For alpar@2391: * precise terms see the accompanying LICENSE file. alpar@2391: * alpar@2391: * This software is provided "AS IS" with no warranty of any kind, alpar@2391: * express or implied, and with no claim as to its suitability for any alpar@2391: * purpose. alpar@2391: * alpar@2391: */ alpar@2391: alpar@2235: #include alpar@2235: #include alpar@2235: #include deba@2242: #include alpar@2271: #include alpar@2271: #include alpar@2235: alpar@2235: using namespace lemon; alpar@2235: alpar@2271: template alpar@2271: class EdgeLookUp2 alpar@2271: { alpar@2271: public: deba@2510: GRAPH_TYPEDEFS(typename G); alpar@2271: typedef G Graph; alpar@2271: alpar@2271: private: alpar@2271: const Graph &_g; alpar@2271: typename Graph::template NodeMap _start; alpar@2271: typename Graph::template NodeMap _end; alpar@2271: std::vector _edges; alpar@2271: alpar@2271: class EdgeLess { alpar@2271: const Graph &g; alpar@2271: public: alpar@2271: EdgeLess(const Graph &_g) : g(_g) {} alpar@2271: bool operator()(Edge a,Edge b) const alpar@2271: { alpar@2271: return g.target(a)::iterator ei=_edges.end(); alpar@2271: _end[n]=_edges.size(); alpar@2271: std::sort(_edges.begin()+bi,ei,EdgeLess(_g)); alpar@2271: } alpar@2271: ///Refresh the full data structure. alpar@2271: void refresh() alpar@2271: { alpar@2271: _edges.clear(); alpar@2271: for(NodeIt n(_g);n!=INVALID;++n) refresh(n); alpar@2271: } alpar@2271: alpar@2271: ///Find an edge between two nodes. alpar@2271: alpar@2271: ///Find an edge between two nodes. alpar@2271: ///\param s The source node alpar@2271: ///\param t The target node alpar@2271: ///\return An edge from \c s to \c t if there exists, alpar@2271: ///\ref INVALID otherwise. alpar@2271: alpar@2271: Edge operator()(Node s, Node t) alpar@2271: { alpar@2271: int a=_start[s]; alpar@2271: int b=_end[s]; alpar@2271: while(a alpar@2271: class EdgeLookUp3 alpar@2271: { alpar@2271: public: deba@2510: GRAPH_TYPEDEFS(typename G); alpar@2271: typedef G Graph; alpar@2271: alpar@2271: private: alpar@2271: const Graph &_g; alpar@2271: typename Graph::template NodeMap _start; alpar@2271: typename Graph::template NodeMap _end; alpar@2271: std::vector _edges; alpar@2271: alpar@2271: class EdgeLess { alpar@2271: const Graph &g; alpar@2271: public: alpar@2271: EdgeLess(const Graph &_g) : g(_g) {} alpar@2271: bool operator()(Edge a,Edge b) const alpar@2271: { alpar@2271: return g.target(a)::iterator ei=_edges.end(); alpar@2271: _end[n]=_edges.size(); alpar@2271: std::sort(_edges.begin()+bi,ei,EdgeLess(_g)); alpar@2271: } alpar@2271: ///Refresh the full data structure. alpar@2271: void refresh() alpar@2271: { alpar@2271: _edges.resize(countEdges(_g)); alpar@2271: int l=0; alpar@2271: for(NodeIt n(_g);n!=INVALID;++n) alpar@2271: { alpar@2271: int ls = l; alpar@2271: _start[n]=&(_edges[l]); alpar@2271: for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e; alpar@2271: _end[n]=&(_edges[l]); alpar@2271: std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g)); alpar@2271: } alpar@2271: alpar@2271: } alpar@2271: alpar@2271: ///Find an edge between two nodes. alpar@2271: alpar@2271: ///Find an edge between two nodes. alpar@2271: ///\param s The source node alpar@2271: ///\param t The target node alpar@2271: ///\return An edge from \c s to \c t if there exists, alpar@2271: ///\ref INVALID otherwise. alpar@2271: alpar@2271: Edge operator()(Node s, Node t) alpar@2271: { alpar@2271: Edge *a=_start[s]; alpar@2271: Edge *b=_end[s]; alpar@2271: while(a!=b) alpar@2271: { alpar@2271: Edge *m=a+((b-a)/2); alpar@2271: Node tt = _g.target(*m); alpar@2271: if(tt==t) return *m; alpar@2271: else if(tt alpar@2272: // class EdgeLookUp4 alpar@2272: // { alpar@2272: // public: deba@2510: // GRAPH_TYPEDEFS(typename G); alpar@2272: // typedef G Graph; alpar@2271: alpar@2272: // private: alpar@2272: // const Graph &_g; alpar@2272: // typename Graph::template NodeMap _start; alpar@2272: // typename Graph::template NodeMap _end; alpar@2272: // std::vector _edges; alpar@2271: alpar@2272: // class EdgeLess { alpar@2272: // const Graph &g; alpar@2272: // public: alpar@2272: // EdgeLess(const Graph &_g) : g(_g) {} alpar@2272: // bool operator()(Edge a,Edge b) const alpar@2272: // { alpar@2272: // return g.target(a)::iterator ei=_edges.end(); alpar@2272: // _end[n]=_edges.size(); alpar@2272: // std::sort(_edges.begin()+bi,ei,EdgeLess(_g)); alpar@2272: // } alpar@2272: // ///Refresh the full data structure. alpar@2272: // void refresh() alpar@2272: // { alpar@2272: // _edges.resize(countEdges(_g)); alpar@2272: // int l=0; alpar@2272: // for(NodeIt n(_g);n!=INVALID;++n) alpar@2272: // { alpar@2272: // int ls = l; alpar@2272: // _start[n]=&(_edges[l]); alpar@2272: // for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e; alpar@2272: // _end[n]=&(_edges[l]); alpar@2272: // std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g)); alpar@2272: // } alpar@2271: alpar@2272: // } alpar@2271: alpar@2272: // ///Find an edge between two nodes. alpar@2271: alpar@2272: // ///Find an edge between two nodes. alpar@2272: // ///\param s The source node alpar@2272: // ///\param t The target node alpar@2272: // ///\return An edge from \c s to \c t if there exists, alpar@2272: // ///\ref INVALID otherwise. alpar@2271: alpar@2272: // Edge operator()(Node s, Node t) alpar@2272: // { alpar@2272: // Edge *a=_start[s]; alpar@2272: // Edge *b=_end[s]; alpar@2272: // while(a!=b) alpar@2272: // { alpar@2272: // // #ifdef X86 alpar@2272: // Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc); alpar@2272: // // #elif X86_64 alpar@2272: // // Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc); alpar@2272: // // #else alpar@2272: // // Edge *m=a+((b-a)/2); alpar@2272: // // #endif alpar@2272: // Node tt = _g.target(*m); alpar@2272: // if(tt==t) return *m; alpar@2272: // else if(tt alpar@2272: // class EdgeLookUp5 alpar@2272: // { alpar@2272: // public: deba@2510: // GRAPH_TYPEDEFS(typename G); alpar@2272: // typedef G Graph; alpar@2271: alpar@2272: // private: alpar@2272: // const Graph &_g; alpar@2272: // typename Graph::template NodeMap _start; alpar@2272: // typename Graph::template NodeMap _end; alpar@2272: // std::vector _edges; alpar@2271: alpar@2272: // class EdgeLess { alpar@2272: // const Graph &g; alpar@2272: // public: alpar@2272: // EdgeLess(const Graph &_g) : g(_g) {} alpar@2272: // bool operator()(Edge a,Edge b) const alpar@2272: // { alpar@2272: // return g.target(a)::iterator ei=_edges.end(); alpar@2272: // _end[n]=_edges.size(); alpar@2272: // std::sort(_edges.begin()+bi,ei,EdgeLess(_g)); alpar@2272: // } alpar@2272: // ///Refresh the full data structure. alpar@2272: // void refresh() alpar@2272: // { alpar@2272: // _edges.resize(countEdges(_g)); alpar@2272: // int l=0; alpar@2272: // for(NodeIt n(_g);n!=INVALID;++n) alpar@2272: // { alpar@2272: // int ls = l; alpar@2272: // _start[n]=&(_edges[l]); alpar@2272: // for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e; alpar@2272: // _end[n]=&(_edges[l]); alpar@2272: // std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g)); alpar@2272: // } alpar@2271: alpar@2272: // } alpar@2271: alpar@2272: // ///Find an edge between two nodes. alpar@2271: alpar@2272: // ///Find an edge between two nodes. alpar@2272: // ///\param s The source node alpar@2272: // ///\param t The target node alpar@2272: // ///\return An edge from \c s to \c t if there exists, alpar@2272: // ///\ref INVALID otherwise. alpar@2271: alpar@2272: // Edge operator()(Node s, Node t) alpar@2272: // { alpar@2272: // Edge *a=_start[s]; alpar@2272: // Edge *b=_end[s]; alpar@2272: // while(a!=b) alpar@2272: // { alpar@2272: // // #ifdef X86 alpar@2272: // Edge *m=(Edge*)((((unsigned int)a>>1)+((unsigned int)b)>>1) alpar@2272: // & 0xfffffffc); alpar@2272: // // #elif X86_64 alpar@2272: // // Edge *m=(Edge*)(((unsigned long)a>>1+(undigned long)b)>>1)&0xfffffffc); alpar@2272: // // #else alpar@2272: // // Edge *m=a+((b-a)/2); alpar@2272: // // #endif alpar@2272: // Node tt = _g.target(*m); alpar@2272: // if(tt==t) return *m; alpar@2272: // else if(tt _el; alpar@2235: EL(Graph &g) :_g(g), _el(g) {} alpar@2235: void operator()() alpar@2235: { alpar@2235: Edge e; alpar@2235: alpar@2235: for(NodeIt v(_g);v!=INVALID;++v) alpar@2235: for(NodeIt u(_g);u!=INVALID;++u) alpar@2235: e=_el(u,v); alpar@2235: } alpar@2235: alpar@2235: }; deba@2539: deba@2539: class DEL deba@2539: { deba@2539: public: deba@2539: Graph &_g; deba@2539: DynEdgeLookUp _el; deba@2539: DEL(Graph &g) :_g(g), _el(g) {} deba@2539: void operator()() deba@2539: { deba@2539: Edge e; deba@2539: deba@2539: for(NodeIt v(_g);v!=INVALID;++v) deba@2539: for(NodeIt u(_g);u!=INVALID;++u) deba@2539: e=_el(u,v); deba@2539: } deba@2539: deba@2539: }; deba@2539: alpar@2235: class EL2 alpar@2235: { alpar@2235: public: alpar@2235: Graph &_g; alpar@2235: EdgeLookUp2 _el; alpar@2235: EL2(Graph &g) :_g(g), _el(g) {} alpar@2235: void operator()() alpar@2235: { alpar@2235: Edge e; alpar@2235: alpar@2235: for(NodeIt v(_g);v!=INVALID;++v) alpar@2235: for(NodeIt u(_g);u!=INVALID;++u) alpar@2235: e=_el(u,v); alpar@2235: } alpar@2235: alpar@2235: }; alpar@2235: alpar@2235: class EL3 alpar@2235: { alpar@2235: public: alpar@2235: Graph &_g; alpar@2235: EdgeLookUp3 _el; alpar@2235: EL3(Graph &g) :_g(g), _el(g) {} alpar@2235: void operator()() alpar@2235: { alpar@2235: Edge e; alpar@2235: alpar@2235: for(NodeIt v(_g);v!=INVALID;++v) alpar@2235: for(NodeIt u(_g);u!=INVALID;++u) alpar@2235: e=_el(u,v); alpar@2235: } alpar@2235: alpar@2235: }; alpar@2235: alpar@2274: // class EL4 alpar@2274: // { alpar@2274: // public: alpar@2274: // Graph &_g; alpar@2274: // EdgeLookUp4 _el; alpar@2274: // EL4(Graph &g) :_g(g), _el(g) {} alpar@2274: // void operator()() alpar@2274: // { alpar@2274: // Edge e; alpar@2235: alpar@2274: // for(NodeIt v(_g);v!=INVALID;++v) alpar@2274: // for(NodeIt u(_g);u!=INVALID;++u) alpar@2274: // e=_el(u,v); alpar@2274: // } alpar@2235: alpar@2274: // }; alpar@2235: alpar@2274: // class EL5 alpar@2274: // { alpar@2274: // public: alpar@2274: // Graph &_g; alpar@2274: // EdgeLookUp5 _el; alpar@2274: // EL5(Graph &g) :_g(g), _el(g) {} alpar@2274: // void operator()() alpar@2274: // { alpar@2274: // Edge e; alpar@2271: alpar@2274: // for(NodeIt v(_g);v!=INVALID;++v) alpar@2274: // for(NodeIt u(_g);u!=INVALID;++u) alpar@2274: // e=_el(u,v); alpar@2274: // } alpar@2271: alpar@2274: // }; alpar@2271: alpar@2238: int main(int, char**argv) alpar@2235: { alpar@2235: int N=atoi(argv[1]); alpar@2235: int M=int(N*atof(argv[2])); alpar@2235: alpar@2235: Graph g; alpar@2235: alpar@2235: std::vector v; alpar@2235: for(int i=0;i el(g); alpar@2235: alpar@2235: // TimeReport t("EdgeLookUp: "); alpar@2235: // for(NodeIt u(g);u!=INVALID;++u) alpar@2235: // for(NodeIt v(g);v!=INVALID;++v) alpar@2235: // e=el(u,v); alpar@2235: // } alpar@2235: alpar@2235: alpar@2235: TimeStamp t1 = runningTimeTest(FE(g),1); alpar@2235: TimeStamp t2 = runningTimeTest(EL(g),1); deba@2539: TimeStamp t3 = runningTimeTest(DEL(g),1); deba@2539: TimeStamp t4 = runningTimeTest(EL2(g),1); deba@2539: TimeStamp t5 = runningTimeTest(EL3(g),1); alpar@2272: // TimeStamp t5 = runningTimeTest(EL4(g),1); alpar@2272: // TimeStamp t6 = runningTimeTest(EL5(g),1); alpar@2235: deba@2539: std::cout << t1.userTime() << ' ' deba@2539: << t2.userTime() << ' ' deba@2539: << t3.userTime() << ' ' deba@2539: << t4.userTime() << ' ' deba@2539: << t5.userTime() << ' ' deba@2539: // << t5.userTime() << ' ' deba@2539: // << t6.userTime() deba@2539: << std::endl; alpar@2235: std::cout << t1.userTime()/N/N << ' ' alpar@2235: << t2.userTime()/N/N << ' ' alpar@2235: << t3.userTime()/N/N << ' ' alpar@2235: << t4.userTime()/N/N << ' ' deba@2539: << t5.userTime()/N/N << ' ' alpar@2272: // << t5.userTime()/N/N << ' ' alpar@2272: // << t6.userTime()/N/N alpar@2240: << std::endl; alpar@2235: } alpar@2235: