lemon-0.x: benchmark/edge_lookup

     1 /* -*- C++ -*-

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library

     4  *

     5  * Copyright (C) 2003-2006

     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     8  *

     9  * Permission to use, modify and distribute this software is granted

    10  * provided that this copyright notice appears in all copies. For

    11  * precise terms see the accompanying LICENSE file.

    12  *

    13  * This software is provided "AS IS" with no warranty of any kind,

    14  * express or implied, and with no claim as to its suitability for any

    15  * purpose.

    16  *

    17  */

    19 #ifndef LEMON_EDGE_LOOKUP_H

    20 #define LEMON_EDGE_LOOKUP_H

    22 #include<lemon/graph_utils.h>

    23 #include<algorithm>

    24 #include<vector>

    26 namespace lemon {

    27   template<class G>

    28   class EdgeLookUp2

    29   {

    30   public:

    31     GRAPH_TYPEDEFS(typename G)

    32     typedef G Graph;

    34   private:

    35     const Graph &_g;

    36     typename Graph::template NodeMap<int> _start;

    37     typename Graph::template NodeMap<int> _end;

    38     std::vector<Edge> _edges;

    40     class EdgeLess {

    41       const Graph &g;

    42     public:

    43       EdgeLess(const Graph &_g) : g(_g) {}

    44       bool operator()(Edge a,Edge b) const

    45       {

    46 	return g.target(a)<g.target(b);

    47       }

    48     };

    50   public:

    52     ///Constructor

    53     EdgeLookUp2(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}

    55   public:

    56     ///Refresh the data structure at a node.

    57     void refresh(Node n)

    58     {

    59       const int bi = _start[n] = _edges.size();

    60       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);

    61       const typename std::vector<Edge>::iterator ei=_edges.end();

    62       _end[n]=_edges.size();

    63       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));

    64     }

    65     ///Refresh the full data structure.

    66     void refresh()

    67     {

    68       _edges.clear();

    69       for(NodeIt n(_g);n!=INVALID;++n) refresh(n);

    70     }

    72     ///Find an edge between two nodes.

    74     ///Find an edge between two nodes.

    75     ///\param s The source node

    76     ///\param t The target node

    77     ///\return An edge from \c s to \c t if there exists,

    78     ///\ref INVALID otherwise.

    80     Edge operator()(Node s, Node t)

    81     {

    82       int a=_start[s];

    83       int b=_end[s];

    84       while(a<b)

    85 	{

    86 	  int n=(a+b)/2;

    87 	  Node tt = _g.target(_edges[n]);

    88 	  if(tt==t) return _edges[n];

    89 	  else if(tt<t) a=n+1;

    90 	  else b=n;

    91 	}

    92       return INVALID;

    93     }

    95     ///Find the next edge

    97       ///\warning This function is unimplemented.

    98     Edge operator()(Node s, Node t, Edge prev)

    99     {

   100       return prev==INVALID?(*this)(s,t):INVALID;

   101     }

   103   };

   105   template<class G>

   106   class EdgeLookUp3

   107   {

   108   public:

   109     GRAPH_TYPEDEFS(typename G)

   110     typedef G Graph;

   112   private:

   113     const Graph &_g;

   114     typename Graph::template NodeMap<Edge*> _start;

   115     typename Graph::template NodeMap<Edge*> _end;

   116     std::vector<Edge> _edges;

   118     class EdgeLess {

   119       const Graph &g;

   120     public:

   121       EdgeLess(const Graph &_g) : g(_g) {}

   122       bool operator()(Edge a,Edge b) const

   123       {

   124 	return g.target(a)<g.target(b);

   125       }

   126     };

   128   public:

   130     ///Constructor

   131     EdgeLookUp3(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}

   133   public:

   134     ///Refresh the data structure at a node.

   135     void refresh(Node n)

   136     {

   137       const int bi = _start[n] = _edges.size();

   138       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);

   139       const typename std::vector<Edge>::iterator ei=_edges.end();

   140       _end[n]=_edges.size();

   141       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));

   142     }

   143     ///Refresh the full data structure.

   144     void refresh()

   145     {

   146       _edges.resize(countEdges(_g));

   147       int l=0;

   148       for(NodeIt n(_g);n!=INVALID;++n)

   149 	{

   150 	  int ls = l;

   151 	  _start[n]=&(_edges[l]);

   152 	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;

   153 	  _end[n]=&(_edges[l]);

   154 	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));

   155 	}

   157     }

   159     ///Find an edge between two nodes.

   161     ///Find an edge between two nodes.

   162     ///\param s The source node

   163     ///\param t The target node

   164     ///\return An edge from \c s to \c t if there exists,

   165     ///\ref INVALID otherwise.

   167     Edge operator()(Node s, Node t)

   168     {

   169       Edge *a=_start[s];

   170       Edge *b=_end[s];

   171       while(a!=b)

   172 	{

   173  	  Edge *m=a+((b-a)/2);

   174 	  Node tt = _g.target(*m);

   175 	  if(tt==t) return *m;

   176 	  else if(tt<t) a=m+1;

   177 	  else b=m;

   178 	}

   179       return INVALID;

   180     }

   182     ///Find the next edge

   184       ///\warning This function is unimplemented.

   185     Edge operator()(Node s, Node t, Edge prev)

   186     {

   187       return prev==INVALID?(*this)(s,t):INVALID;

   188     }

   190   };

   192   template<class G>

   193   class EdgeLookUp4

   194   {

   195   public:

   196     GRAPH_TYPEDEFS(typename G)

   197     typedef G Graph;

   199   private:

   200     const Graph &_g;

   201     typename Graph::template NodeMap<Edge*> _start;

   202     typename Graph::template NodeMap<Edge*> _end;

   203     std::vector<Edge> _edges;

   205     class EdgeLess {

   206       const Graph &g;

   207     public:

   208       EdgeLess(const Graph &_g) : g(_g) {}

   209       bool operator()(Edge a,Edge b) const

   210       {

   211 	return g.target(a)<g.target(b);

   212       }

   213     };

   215   public:

   217     ///Constructor

   218     EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}

   220   public:

   221     ///Refresh the data structure at a node.

   222     void refresh(Node n)

   223     {

   224       const int bi = _start[n] = _edges.size();

   225       for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges.push_back(e);

   226       const typename std::vector<Edge>::iterator ei=_edges.end();

   227       _end[n]=_edges.size();

   228       std::sort(_edges.begin()+bi,ei,EdgeLess(_g));

   229     }

   230     ///Refresh the full data structure.

   231     void refresh()

   232     {

   233       _edges.resize(countEdges(_g));

   234       int l=0;

   235       for(NodeIt n(_g);n!=INVALID;++n)

   236 	{

   237 	  int ls = l;

   238 	  _start[n]=&(_edges[l]);

   239 	  for(OutEdgeIt e(_g,n);e!=INVALID;++e) _edges[l++]=e;

   240 	  _end[n]=&(_edges[l]);

   241 	  std::sort(_edges.begin()+ls,_edges.begin()+l,EdgeLess(_g));

   242 	}

   244     }

   246     ///Find an edge between two nodes.

   248     ///Find an edge between two nodes.

   249     ///\param s The source node

   250     ///\param t The target node

   251     ///\return An edge from \c s to \c t if there exists,

   252     ///\ref INVALID otherwise.

   254     Edge operator()(Node s, Node t)

   255     {

   256       Edge *a=_start[s];

   257       Edge *b=_end[s];

   258       while(a!=b)

   259 	{

   260 #ifdef X86

   261  	  Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);

   262 #elif X86_64

   263 	  Edge *m=(Edge*)(((unsigned long)a+(undigned long)b)/2 & 0xfffffffc);

   264 #else

   265  	  Edge *m=a+((b-a)/2);

   266 #endif

   267 	  Node tt = _g.target(*m);

   268 	  if(tt==t) return *m;

   269 	  else if(tt<t) a=m+1;

   270 	  else b=m;

   271 	}

   272       return INVALID;

   273     }

   275     ///Find the next edge

   277       ///\warning This function is unimplemented.

   278     Edge operator()(Node s, Node t, Edge prev)

   279     {

   280       return prev==INVALID?(*this)(s,t):INVALID;

   281     }

   283   };

   285 }

   287 #endif

author	alpar
	Sun, 22 Oct 2006 19:45:57 +0000
changeset 2258	741995f3dbc4
parent 2239	18c24fe93b99
permissions	-rw-r--r--