COIN-OR::LEMON - Graph Library

Changeset 2271:a2ab63454152 in lemon-0.x


Ignore:
Timestamp:
10/30/06 16:23:35 (13 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3033
Message:

repository cleanup

Location:
benchmark
Files:
1 deleted
1 edited

Legend:

Unmodified
Added
Removed
  • benchmark/edge_lookup.cc

    r2252 r2271  
    1 #include"edge_lookup_test.h"
    21#include<lemon/smart_graph.h>
    32#include<vector>
    43#include<lemon/time_measure.h>
    54#include<lemon/random.h>
     5#include<lemon/graph_utils.h>
     6#include<algorithm>
    67
    78using namespace lemon;
     9
     10  template<class G>
     11  class EdgeLookUp2
     12  {
     13  public:
     14    GRAPH_TYPEDEFS(typename G)
     15    typedef G Graph;
     16
     17  private:
     18    const Graph &_g;
     19    typename Graph::template NodeMap<int> _start;
     20    typename Graph::template NodeMap<int> _end;
     21    std::vector<Edge> _edges;
     22   
     23    class EdgeLess {
     24      const Graph &g;
     25    public:
     26      EdgeLess(const Graph &_g) : g(_g) {}
     27      bool operator()(Edge a,Edge b) const
     28      {
     29        return g.target(a)<g.target(b);
     30      }
     31    };
     32   
     33  public:
     34   
     35    ///Constructor
     36    EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
     37   
     38  public:
     39    ///Refresh the data structure at a node.
     40    void refresh(Node n)
     41    {
     42      const int bi = _start[n] = _edges.size();
     43      for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
     44      const typename std::vector<Edge>::iterator ei=_edges.end();
     45      _end[n]=_edges.size();
     46      std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
     47    }
     48    ///Refresh the full data structure.
     49    void refresh()
     50    {
     51      _edges.clear();
     52      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
     53    }
     54   
     55    ///Find an edge between two nodes.
     56   
     57    ///Find an edge between two nodes.
     58    ///\param s The source node
     59    ///\param t The target node
     60    ///\return An edge from \c s to \c t if there exists,
     61    ///\ref INVALID otherwise.
     62
     63    Edge operator()(Node s, Node t)
     64    {
     65      int a=_start[s];
     66      int b=_end[s];
     67      while(a<b)
     68        {
     69          int n=(a+b)/2;
     70          Node tt = _g.target(_edges[n]);
     71          if(tt==t) return _edges[n];
     72          else if(tt<t) a=n+1;
     73          else b=n;
     74        }
     75      return INVALID;
     76    }
     77
     78    ///Find the next edge
     79     
     80      ///\warning This function is unimplemented.
     81    Edge operator()(Node s, Node t, Edge prev)
     82    {
     83      return prev==INVALID?(*this)(s,t):INVALID;
     84    }
     85     
     86  };
     87
     88  template<class G>
     89  class EdgeLookUp3
     90  {
     91  public:
     92    GRAPH_TYPEDEFS(typename G)
     93    typedef G Graph;
     94
     95  private:
     96    const Graph &_g;
     97    typename Graph::template NodeMap<Edge*> _start;
     98    typename Graph::template NodeMap<Edge*> _end;
     99    std::vector<Edge> _edges;
     100   
     101    class EdgeLess {
     102      const Graph &g;
     103    public:
     104      EdgeLess(const Graph &_g) : g(_g) {}
     105      bool operator()(Edge a,Edge b) const
     106      {
     107        return g.target(a)<g.target(b);
     108      }
     109    };
     110   
     111  public:
     112   
     113    ///Constructor
     114    EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
     115   
     116  public:
     117    ///Refresh the data structure at a node.
     118    void refresh(Node n)
     119    {
     120      const int bi = _start[n] = _edges.size();
     121      for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
     122      const typename std::vector<Edge>::iterator ei=_edges.end();
     123      _end[n]=_edges.size();
     124      std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
     125    }
     126    ///Refresh the full data structure.
     127    void refresh()
     128    {
     129      _edges.resize(countEdges(_g));
     130      int l=0;
     131      for(NodeIt n(_g);n!=INVALID;++n)
     132        {
     133          int ls = l;
     134          _start[n]=&(_edges[l]);       
     135          for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
     136          _end[n]=&(_edges[l]);
     137          std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
     138        }
     139     
     140    }
     141   
     142    ///Find an edge between two nodes.
     143   
     144    ///Find an edge between two nodes.
     145    ///\param s The source node
     146    ///\param t The target node
     147    ///\return An edge from \c s to \c t if there exists,
     148    ///\ref INVALID otherwise.
     149
     150    Edge operator()(Node s, Node t)
     151    {
     152      Edge *a=_start[s];
     153      Edge *b=_end[s];
     154      while(a!=b)
     155        {
     156          Edge *m=a+((b-a)/2);
     157          Node tt = _g.target(*m);
     158          if(tt==t) return *m;
     159          else if(tt<t) a=m+1;
     160          else b=m;
     161        }
     162      return INVALID;
     163    }
     164
     165    ///Find the next edge
     166     
     167      ///\warning This function is unimplemented.
     168    Edge operator()(Node s, Node t, Edge prev)
     169    {
     170      return prev==INVALID?(*this)(s,t):INVALID;
     171    }
     172     
     173  };
     174
     175  template<class G>
     176  class EdgeLookUp4
     177  {
     178  public:
     179    GRAPH_TYPEDEFS(typename G)
     180    typedef G Graph;
     181   
     182  private:
     183    const Graph &_g;
     184    typename Graph::template NodeMap<Edge*> _start;
     185    typename Graph::template NodeMap<Edge*> _end;
     186    std::vector<Edge> _edges;
     187   
     188    class EdgeLess {
     189      const Graph &g;
     190    public:
     191      EdgeLess(const Graph &_g) : g(_g) {}
     192      bool operator()(Edge a,Edge b) const
     193      {
     194        return g.target(a)<g.target(b);
     195      }
     196    };
     197   
     198  public:
     199   
     200    ///Constructor
     201    EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
     202   
     203  public:
     204    ///Refresh the data structure at a node.
     205    void refresh(Node n)
     206    {
     207      const int bi = _start[n] = _edges.size();
     208      for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
     209      const typename std::vector<Edge>::iterator ei=_edges.end();
     210      _end[n]=_edges.size();
     211      std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
     212    }
     213    ///Refresh the full data structure.
     214    void refresh()
     215    {
     216      _edges.resize(countEdges(_g));
     217      int l=0;
     218      for(NodeIt n(_g);n!=INVALID;++n)
     219        {
     220          int ls = l;
     221          _start[n]=&(_edges[l]);       
     222          for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
     223          _end[n]=&(_edges[l]);
     224          std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
     225        }
     226     
     227    }
     228   
     229    ///Find an edge between two nodes.
     230   
     231    ///Find an edge between two nodes.
     232    ///\param s The source node
     233    ///\param t The target node
     234    ///\return An edge from \c s to \c t if there exists,
     235    ///\ref INVALID otherwise.
     236
     237    Edge operator()(Node s, Node t)
     238    {
     239      Edge *a=_start[s];
     240      Edge *b=_end[s];
     241      while(a!=b)
     242        {
     243// #ifdef X86
     244          Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
     245// #elif X86_64
     246//        Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc);
     247// #else
     248//        Edge *m=a+((b-a)/2);
     249// #endif
     250          Node tt = _g.target(*m);
     251          if(tt==t) return *m;
     252          else if(tt<t) a=m+1;
     253          else b=m;
     254        }
     255      return INVALID;
     256    }
     257
     258    ///Find the next edge
     259     
     260      ///\warning This function is unimplemented.
     261    Edge operator()(Node s, Node t, Edge prev)
     262    {
     263      return prev==INVALID?(*this)(s,t):INVALID;
     264    }
     265     
     266  };
     267
     268  template<class G>
     269  class EdgeLookUp5
     270  {
     271  public:
     272    GRAPH_TYPEDEFS(typename G)
     273    typedef G Graph;
     274   
     275  private:
     276    const Graph &_g;
     277    typename Graph::template NodeMap<Edge*> _start;
     278    typename Graph::template NodeMap<Edge*> _end;
     279    std::vector<Edge> _edges;
     280   
     281    class EdgeLess {
     282      const Graph &g;
     283    public:
     284      EdgeLess(const Graph &_g) : g(_g) {}
     285      bool operator()(Edge a,Edge b) const
     286      {
     287        return g.target(a)<g.target(b);
     288      }
     289    };
     290   
     291  public:
     292   
     293    ///Constructor
     294    EdgeLookUp5(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
     295   
     296  public:
     297    ///Refresh the data structure at a node.
     298    void refresh(Node n)
     299    {
     300      const int bi = _start[n] = _edges.size();
     301      for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);
     302      const typename std::vector<Edge>::iterator ei=_edges.end();
     303      _end[n]=_edges.size();
     304      std::sort(_edges.begin()+bi,ei,EdgeLess(_g));
     305    }
     306    ///Refresh the full data structure.
     307    void refresh()
     308    {
     309      _edges.resize(countEdges(_g));
     310      int l=0;
     311      for(NodeIt n(_g);n!=INVALID;++n)
     312        {
     313          int ls = l;
     314          _start[n]=&(_edges[l]);       
     315          for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;
     316          _end[n]=&(_edges[l]);
     317          std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));
     318        }
     319     
     320    }
     321   
     322    ///Find an edge between two nodes.
     323   
     324    ///Find an edge between two nodes.
     325    ///\param s The source node
     326    ///\param t The target node
     327    ///\return An edge from \c s to \c t if there exists,
     328    ///\ref INVALID otherwise.
     329
     330    Edge operator()(Node s, Node t)
     331    {
     332      Edge *a=_start[s];
     333      Edge *b=_end[s];
     334      while(a!=b)
     335        {
     336// #ifdef X86
     337          Edge *m=(Edge*)((((unsigned int)a>>1)+((unsigned int)b)>>1)
     338                          & 0xfffffffc);
     339// #elif X86_64
     340//        Edge *m=(Edge*)(((unsigned long)a>>1+(undigned long)b)>>1)&0xfffffffc);
     341// #else
     342//        Edge *m=a+((b-a)/2);
     343// #endif
     344          Node tt = _g.target(*m);
     345          if(tt==t) return *m;
     346          else if(tt<t) a=m+1;
     347          else b=m;
     348        }
     349      return INVALID;
     350    }
     351
     352    ///Find the next edge
     353     
     354      ///\warning This function is unimplemented.
     355    Edge operator()(Node s, Node t, Edge prev)
     356    {
     357      return prev==INVALID?(*this)(s,t):INVALID;
     358    }
     359     
     360  };
    8361
    9362GRAPH_TYPEDEFS(SmartGraph)
     
    82435  EdgeLookUp4<Graph> _el;
    83436  EL4(Graph &g) :_g(g), _el(g) {}
     437  void operator()()
     438  {
     439    Edge e;
     440   
     441    for(NodeIt v(_g);v!=INVALID;++v)
     442      for(NodeIt u(_g);u!=INVALID;++u)
     443        e=_el(u,v);
     444  }
     445 
     446};
     447
     448class EL5
     449{
     450public:
     451  Graph &_g;
     452  EdgeLookUp5<Graph> _el;
     453  EL5(Graph &g) :_g(g), _el(g) {}
    84454  void operator()()
    85455  {
     
    127497  TimeStamp t3 = runningTimeTest(EL2(g),1);
    128498  TimeStamp t4 = runningTimeTest(EL3(g),1);
    129 //   TimeStamp t5 = runningTimeTest(EL4(g),1);
     499  TimeStamp t5 = runningTimeTest(EL4(g),1);
     500  TimeStamp t6 = runningTimeTest(EL5(g),1);
    130501
    131502  std::cout << t1.userTime()/N/N << ' '
     
    133504            << t3.userTime()/N/N << ' '
    134505            << t4.userTime()/N/N << ' '
    135 //          << t5.userTime()/N/N
     506            << t5.userTime()/N/N << ' '
     507            << t6.userTime()/N/N
    136508            << std::endl;
    137509}
Note: See TracChangeset for help on using the changeset viewer.