source: lemon-0.x/benchmark/edge_lookup.cc @ 2569:12c2c5c4330b

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2008
 * 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.
 *
 */

#include<lemon/smart_graph.h>
#include<vector>
#include<lemon/time_measure.h>
#include<lemon/random.h>
#include<lemon/graph_utils.h>
#include<algorithm>

using 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;
//     }
      
//   };

//   template<class G>
//   class EdgeLookUp5
//   {
//   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
//     EdgeLookUp5(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>>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<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;
//     }
      
//   };

GRAPH_TYPEDEFS(SmartGraph);
typedef SmartGraph Graph;

class FE 
{
public:
  Graph &_g;
  FE(Graph &g) :_g(g) {}
  void operator()() 
  {
    Edge e;
    
    for(NodeIt v(_g);v!=INVALID;++v)
      for(NodeIt u(_g);u!=INVALID;++u)
        e=findEdge(_g,u,v);
  }
  
};

class EL 
{
public:
  Graph &_g;
  EdgeLookUp<Graph> _el;
  EL(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 DEL 
{
public:
  Graph &_g;
  DynEdgeLookUp<Graph> _el;
  DEL(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 EL2
{
public:
  Graph &_g;
  EdgeLookUp2<Graph> _el;
  EL2(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 EL3
{
public:
  Graph &_g;
  EdgeLookUp3<Graph> _el;
  EL3(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 EL4
// {
// public:
//   Graph &_g;
//   EdgeLookUp4<Graph> _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<Graph> _el;
//   EL5(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);
//   }
  
// };

int main(int, char**argv)
{
  int N=atoi(argv[1]);
  int M=int(N*atof(argv[2]));
  
  Graph g;
  
  std::vector<Node> v;
  for(int i=0;i<N;i++) v.push_back(g.addNode());
  for(int i=0;i<M;i++) g.addEdge(v[rnd[N]],v[rnd[N]]);

//   {
//     Edge e;
    
//     TimeReport t("findEdge: ");
//     for(NodeIt u(g);u!=INVALID;++u)
//       for(NodeIt v(g);v!=INVALID;++v)
//      e=findEdge(g,u,v);
//   }
//   {
//     Edge e;
//     EdgeLookUp<Graph> el(g);
    
//     TimeReport t("EdgeLookUp: ");
//     for(NodeIt u(g);u!=INVALID;++u)
//       for(NodeIt v(g);v!=INVALID;++v)
//      e=el(u,v);
//   }


  TimeStamp t1 = runningTimeTest(FE(g),1);
  TimeStamp t2 = runningTimeTest(EL(g),1);
  TimeStamp t3 = runningTimeTest(DEL(g),1);
  TimeStamp t4 = runningTimeTest(EL2(g),1);
  TimeStamp t5 = runningTimeTest(EL3(g),1);
//   TimeStamp t5 = runningTimeTest(EL4(g),1);
//   TimeStamp t6 = runningTimeTest(EL5(g),1);

  std::cout << t1.userTime() << ' ' 
            << t2.userTime() << ' '
            << t3.userTime() << ' '
            << t4.userTime() << ' '
            << t5.userTime() << ' '
//          << t5.userTime() << ' '
//          << t6.userTime()
            << std::endl;
  std::cout << t1.userTime()/N/N << ' ' 
            << t2.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;
}