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<lemon/graph_utils.h>
alpar@2235: #include<algorithm>
alpar@2235: #include<vector>
alpar@2235: 
alpar@2235: namespace lemon {
alpar@2235:   template<class G>
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<int> _start;
alpar@2235:     typename Graph::template NodeMap<int> _end;
alpar@2235:     std::vector<Edge> _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)<g.target(b);
alpar@2235:       }
alpar@2235:     };
alpar@2235:     
alpar@2235:   public:
alpar@2235:     
alpar@2235:     ///Constructor
alpar@2235:     EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
alpar@2235:     
alpar@2235:   public:
alpar@2235:     ///Refresh the data structure at a node.
alpar@2235:     void refresh(Node n) 
alpar@2235:     {
alpar@2235:       const int bi = _start[n] = _edges.size();
alpar@2235:       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
alpar@2235:       const typename std::vector<Edge>::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<b) 
alpar@2235: 	{
alpar@2235: 	  int n=(a+b)/2;
alpar@2235: 	  Node tt = _g.target(_edges[n]);
alpar@2235: 	  if(tt==t) return _edges[n];
alpar@2235: 	  else if(tt<t) a=n+1;
alpar@2235: 	  else b=n;
alpar@2235: 	}
alpar@2235:       return INVALID;
alpar@2235:     }
alpar@2235: 
alpar@2235:     ///Find the next edge
alpar@2235:       
alpar@2235:       ///\warning This function is unimplemented.
alpar@2235:     Edge operator()(Node s, Node t, Edge prev) 
alpar@2235:     {
alpar@2235:       return prev==INVALID?(*this)(s,t):INVALID;
alpar@2235:     }
alpar@2235:       
alpar@2235:   };
alpar@2235: 
alpar@2235:   template<class G>
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<Edge*> _start;
alpar@2235:     typename Graph::template NodeMap<Edge*> _end;
alpar@2235:     std::vector<Edge> _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)<g.target(b);
alpar@2235:       }
alpar@2235:     };
alpar@2235:     
alpar@2235:   public:
alpar@2235:     
alpar@2235:     ///Constructor
alpar@2235:     EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
alpar@2235:     
alpar@2235:   public:
alpar@2235:     ///Refresh the data structure at a node.
alpar@2235:     void refresh(Node n) 
alpar@2235:     {
alpar@2235:       const int bi = _start[n] = _edges.size();
alpar@2235:       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
alpar@2235:       const typename std::vector<Edge>::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<t) a=m+1;
alpar@2235: 	  else b=m;
alpar@2235: 	}
alpar@2235:       return INVALID;
alpar@2235:     }
alpar@2235: 
alpar@2235:     ///Find the next edge
alpar@2235:       
alpar@2235:       ///\warning This function is unimplemented.
alpar@2235:     Edge operator()(Node s, Node t, Edge prev) 
alpar@2235:     {
alpar@2235:       return prev==INVALID?(*this)(s,t):INVALID;
alpar@2235:     }
alpar@2235:       
alpar@2235:   };
alpar@2235: 
alpar@2252:   template<class G>
alpar@2252:   class EdgeLookUp4
alpar@2252:   {
alpar@2252:   public:
alpar@2252:     GRAPH_TYPEDEFS(typename G)
alpar@2252:     typedef G Graph;
alpar@2252:     
alpar@2252:   private:
alpar@2252:     const Graph &_g;
alpar@2252:     typename Graph::template NodeMap<Edge*> _start;
alpar@2252:     typename Graph::template NodeMap<Edge*> _end;
alpar@2252:     std::vector<Edge> _edges;
alpar@2252:     
alpar@2252:     class EdgeLess {
alpar@2252:       const Graph &g;
alpar@2252:     public:
alpar@2252:       EdgeLess(const Graph &_g) : g(_g) {}
alpar@2252:       bool operator()(Edge a,Edge b) const 
alpar@2252:       {
alpar@2252: 	return g.target(a)<g.target(b);
alpar@2252:       }
alpar@2252:     };
alpar@2252:     
alpar@2252:   public:
alpar@2252:     
alpar@2252:     ///Constructor
alpar@2252:     EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
alpar@2252:     
alpar@2252:   public:
alpar@2252:     ///Refresh the data structure at a node.
alpar@2252:     void refresh(Node n) 
alpar@2252:     {
alpar@2252:       const int bi = _start[n] = _edges.size();
alpar@2252:       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
alpar@2252:       const typename std::vector<Edge>::iterator ei=_edges.end();
alpar@2252:       _end[n]=_edges.size();
alpar@2252:       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
alpar@2252:     }
alpar@2252:     ///Refresh the full data structure.
alpar@2252:     void refresh() 
alpar@2252:     {
alpar@2252:       _edges.resize(countEdges(_g));
alpar@2252:       int l=0;
alpar@2252:       for(NodeIt n(_g);n!=INVALID;++n)
alpar@2252: 	{
alpar@2252: 	  int ls = l;
alpar@2252: 	  _start[n]=&(_edges[l]);	
alpar@2252: 	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
alpar@2252: 	  _end[n]=&(_edges[l]);
alpar@2252: 	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
alpar@2252: 	}
alpar@2252:       
alpar@2252:     }
alpar@2252:     
alpar@2252:     ///Find an edge between two nodes.
alpar@2252:     
alpar@2252:     ///Find an edge between two nodes.
alpar@2252:     ///\param s The source node
alpar@2252:     ///\param t The target node
alpar@2252:     ///\return An edge from \c s to \c t if there exists,
alpar@2252:     ///\ref INVALID otherwise.
alpar@2235: 
alpar@2252:     Edge operator()(Node s, Node t) 
alpar@2252:     {
alpar@2252:       Edge *a=_start[s];
alpar@2252:       Edge *b=_end[s];
alpar@2252:       while(a!=b) 
alpar@2252: 	{
alpar@2252: #ifdef X86
alpar@2252:  	  Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
alpar@2252: #elif X86_64
alpar@2252: 	  Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc);
alpar@2252: #else
alpar@2252:  	  Edge *m=a+((b-a)/2);
alpar@2252: #endif
alpar@2252: 	  Node tt = _g.target(*m);
alpar@2252: 	  if(tt==t) return *m;
alpar@2252: 	  else if(tt<t) a=m+1;
alpar@2252: 	  else b=m;
alpar@2252: 	}
alpar@2252:       return INVALID;
alpar@2252:     }
alpar@2252: 
alpar@2252:     ///Find the next edge
alpar@2235:       
alpar@2252:       ///\warning This function is unimplemented.
alpar@2252:     Edge operator()(Node s, Node t, Edge prev) 
alpar@2252:     {
alpar@2252:       return prev==INVALID?(*this)(s,t):INVALID;
alpar@2252:     }
alpar@2235:       
alpar@2252:   };
alpar@2235: 
alpar@2235: }
alpar@2235: 
alpar@2235: #endif