source: lemon-0.x/benchmark/edge_lookup_test.h @ 2255:4a9cc8c800ae

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2006
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#ifndef LEMON_EDGE_LOOKUP_H
#define LEMON_EDGE_LOOKUP_H

#include<lemon/graph_utils.h>
#include<algorithm>
#include<vector>

namespace lemon {
  template<class G>
  class EdgeLookUp2
  {
  public:
    GRAPH_TYPEDEFS(typename G)
    typedef G Graph;

  private:
    const Graph &_g;
    typename Graph::template NodeMap<int> _start;
    typename Graph::template NodeMap<int> _end;
    std::vector<Edge> _edges;
    
    class EdgeLess {
      const Graph &g;
    public:
      EdgeLess(const Graph &_g) : g(_g) {}
      bool operator()(Edge a,Edge b) const 
      {
        return g.target(a)<g.target(b);
      }
    };
    
  public:
    
    ///Constructor
    EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
    
  public:
    ///Refresh the data structure at a node.
    void refresh(Node n) 
    {
      const int bi = _start[n] = _edges.size();
      for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
      const typename std::vector<Edge>::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<b) 
        {
          int n=(a+b)/2;
          Node tt = _g.target(_edges[n]);
          if(tt==t) return _edges[n];
          else if(tt<t) a=n+1;
          else b=n;
        }
      return INVALID;
    }

    ///Find the next edge
      
      ///\warning This function is unimplemented.
    Edge operator()(Node s, Node t, Edge prev) 
    {
      return prev==INVALID?(*this)(s,t):INVALID;
    }
      
  };

  template<class G>
  class EdgeLookUp3
  {
  public:
    GRAPH_TYPEDEFS(typename G)
    typedef G Graph;

  private:
    const Graph &_g;
    typename Graph::template NodeMap<Edge*> _start;
    typename Graph::template NodeMap<Edge*> _end;
    std::vector<Edge> _edges;
    
    class EdgeLess {
      const Graph &g;
    public:
      EdgeLess(const Graph &_g) : g(_g) {}
      bool operator()(Edge a,Edge b) const 
      {
        return g.target(a)<g.target(b);
      }
    };
    
  public:
    
    ///Constructor
    EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
    
  public:
    ///Refresh the data structure at a node.
    void refresh(Node n) 
    {
      const int bi = _start[n] = _edges.size();
      for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
      const typename std::vector<Edge>::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<t) a=m+1;
          else b=m;
        }
      return INVALID;
    }

    ///Find the next edge
      
      ///\warning This function is unimplemented.
    Edge operator()(Node s, Node t, Edge prev) 
    {
      return prev==INVALID?(*this)(s,t):INVALID;
    }
      
  };

  template<class G>
  class EdgeLookUp4
  {
  public:
    GRAPH_TYPEDEFS(typename G)
    typedef G Graph;
    
  private:
    const Graph &_g;
    typename Graph::template NodeMap<Edge*> _start;
    typename Graph::template NodeMap<Edge*> _end;
    std::vector<Edge> _edges;
    
    class EdgeLess {
      const Graph &g;
    public:
      EdgeLess(const Graph &_g) : g(_g) {}
      bool operator()(Edge a,Edge b) const 
      {
        return g.target(a)<g.target(b);
      }
    };
    
  public:
    
    ///Constructor
    EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
    
  public:
    ///Refresh the data structure at a node.
    void refresh(Node n) 
    {
      const int bi = _start[n] = _edges.size();
      for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
      const typename std::vector<Edge>::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<t) a=m+1;
          else b=m;
        }
      return INVALID;
    }

    ///Find the next edge
      
      ///\warning This function is unimplemented.
    Edge operator()(Node s, Node t, Edge prev) 
    {
      return prev==INVALID?(*this)(s,t):INVALID;
    }
      
  };

}

#endif