alpar@2235: /* -*- C++ -*- alpar@2235: * alpar@2235: * This file is a part of LEMON, a generic C++ optimization library alpar@2235: * alpar@2235: * Copyright (C) 2003-2006 alpar@2235: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@2235: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@2235: * alpar@2235: * Permission to use, modify and distribute this software is granted alpar@2235: * provided that this copyright notice appears in all copies. For alpar@2235: * precise terms see the accompanying LICENSE file. alpar@2235: * alpar@2235: * This software is provided "AS IS" with no warranty of any kind, alpar@2235: * express or implied, and with no claim as to its suitability for any alpar@2235: * purpose. alpar@2235: * alpar@2235: */ alpar@2235: alpar@2235: #ifndef LEMON_EDGE_LOOKUP_H alpar@2235: #define LEMON_EDGE_LOOKUP_H alpar@2235: alpar@2235: #include alpar@2235: #include alpar@2235: #include alpar@2235: alpar@2235: namespace lemon { alpar@2235: template alpar@2235: class EdgeLookUp2 alpar@2235: { alpar@2235: public: alpar@2235: GRAPH_TYPEDEFS(typename G) alpar@2235: typedef G Graph; alpar@2235: alpar@2235: private: alpar@2235: const Graph &_g; alpar@2235: typename Graph::template NodeMap _start; alpar@2235: typename Graph::template NodeMap _end; alpar@2235: std::vector _edges; alpar@2235: alpar@2235: class EdgeLess { alpar@2235: const Graph &g; alpar@2235: public: alpar@2235: EdgeLess(const Graph &_g) : g(_g) {} alpar@2235: bool operator()(Edge a,Edge b) const alpar@2235: { alpar@2235: return g.target(a)::iterator ei=_edges.end(); alpar@2235: _end[n]=_edges.size(); alpar@2235: std::sort(_edges.begin()+bi,ei,EdgeLess(_g)); alpar@2235: } alpar@2235: ///Refresh the full data structure. alpar@2235: void refresh() alpar@2235: { alpar@2235: _edges.clear(); alpar@2235: for(NodeIt n(_g);n!=INVALID;++n) refresh(n); alpar@2235: } alpar@2235: alpar@2235: ///Find an edge between two nodes. alpar@2235: alpar@2235: ///Find an edge between two nodes. alpar@2235: ///\param s The source node alpar@2235: ///\param t The target node alpar@2235: ///\return An edge from \c s to \c t if there exists, alpar@2235: ///\ref INVALID otherwise. alpar@2235: alpar@2235: Edge operator()(Node s, Node t) alpar@2235: { alpar@2235: int a=_start[s]; alpar@2235: int b=_end[s]; alpar@2235: while(a alpar@2235: class EdgeLookUp3 alpar@2235: { alpar@2235: public: alpar@2235: GRAPH_TYPEDEFS(typename G) alpar@2235: typedef G Graph; alpar@2235: alpar@2235: private: alpar@2235: const Graph &_g; alpar@2235: typename Graph::template NodeMap _start; alpar@2235: typename Graph::template NodeMap _end; alpar@2235: std::vector _edges; alpar@2235: alpar@2235: class EdgeLess { alpar@2235: const Graph &g; alpar@2235: public: alpar@2235: EdgeLess(const Graph &_g) : g(_g) {} alpar@2235: bool operator()(Edge a,Edge b) const alpar@2235: { alpar@2235: return g.target(a)::iterator ei=_edges.end(); alpar@2235: _end[n]=_edges.size(); alpar@2235: std::sort(_edges.begin()+bi,ei,EdgeLess(_g)); alpar@2235: } alpar@2235: ///Refresh the full data structure. alpar@2235: void refresh() alpar@2235: { alpar@2235: _edges.resize(countEdges(_g)); alpar@2235: int l=0; alpar@2235: for(NodeIt n(_g);n!=INVALID;++n) alpar@2235: { alpar@2235: int ls = l; alpar@2235: _start[n]=&(_edges[l]); alpar@2235: for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e; alpar@2235: _end[n]=&(_edges[l]); alpar@2235: std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g)); alpar@2235: } alpar@2235: alpar@2235: } alpar@2235: alpar@2235: ///Find an edge between two nodes. alpar@2235: alpar@2235: ///Find an edge between two nodes. alpar@2235: ///\param s The source node alpar@2235: ///\param t The target node alpar@2235: ///\return An edge from \c s to \c t if there exists, alpar@2235: ///\ref INVALID otherwise. alpar@2235: alpar@2235: Edge operator()(Node s, Node t) alpar@2235: { alpar@2235: Edge *a=_start[s]; alpar@2235: Edge *b=_end[s]; alpar@2235: while(a!=b) alpar@2235: { alpar@2235: Edge *m=a+((b-a)/2); alpar@2235: Node tt = _g.target(*m); alpar@2235: if(tt==t) return *m; alpar@2235: else if(tt alpar@2235: class EdgeLookUp4 alpar@2235: { alpar@2235: public: alpar@2235: GRAPH_TYPEDEFS(typename G) alpar@2235: typedef G Graph; alpar@2235: alpar@2235: private: alpar@2235: const Graph &_g; alpar@2235: typename Graph::template NodeMap _start; alpar@2235: typename Graph::template NodeMap _end; alpar@2235: std::vector _edges; alpar@2235: alpar@2235: class EdgeLess { alpar@2235: const Graph &g; alpar@2235: public: alpar@2235: EdgeLess(const Graph &_g) : g(_g) {} alpar@2235: bool operator()(Edge a,Edge b) const alpar@2235: { alpar@2235: return g.target(a)::iterator ei=_edges.end(); alpar@2235: _end[n]=_edges.size(); alpar@2235: std::sort(_edges.begin()+bi,ei,EdgeLess(_g)); alpar@2235: } alpar@2235: ///Refresh the full data structure. alpar@2235: void refresh() alpar@2235: { alpar@2235: _edges.resize(countEdges(_g)); alpar@2235: int l=0; alpar@2235: for(NodeIt n(_g);n!=INVALID;++n) alpar@2235: { alpar@2235: int ls = l; alpar@2235: _start[n]=&(_edges[l]); alpar@2235: for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e; alpar@2235: _end[n]=&(_edges[l]); alpar@2235: std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g)); alpar@2235: } alpar@2235: alpar@2235: } alpar@2235: alpar@2235: ///Find an edge between two nodes. alpar@2235: alpar@2235: ///Find an edge between two nodes. alpar@2235: ///\param s The source node alpar@2235: ///\param t The target node alpar@2235: ///\return An edge from \c s to \c t if there exists, alpar@2235: ///\ref INVALID otherwise. alpar@2235: alpar@2235: Edge operator()(Node s, Node t) alpar@2235: { alpar@2235: Edge *a=_start[s]; alpar@2235: Edge *b=_end[s]; alpar@2235: while(a!=b) alpar@2235: { alpar@2235: Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc); alpar@2235: Node tt = _g.target(*m); alpar@2235: if(tt==t) return *m; alpar@2235: else if(tt