COIN-OR::LEMON - Graph Library

Changeset 2252:133028e83940 in lemon-0.x


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

A trial to make the last test platform independent.

Location:
benchmark
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • benchmark/edge_lookup.cc

    r2242 r2252  
    7676};
    7777
    78 // class EL4
    79 // {
    80 // public:
    81 //   Graph &_g;
    82 //   EdgeLookUp4<Graph> _el;
    83 //   EL4(Graph &g) :_g(g), _el(g) {}
    84 //   void operator()()
    85 //   {
    86 //     Edge e;
     78class EL4
     79{
     80public:
     81  Graph &_g;
     82  EdgeLookUp4<Graph> _el;
     83  EL4(Graph &g) :_g(g), _el(g) {}
     84  void operator()()
     85  {
     86    Edge e;
    8787   
    88 //     for(NodeIt v(_g);v!=INVALID;++v)
    89 //       for(NodeIt u(_g);u!=INVALID;++u)
    90 //      e=_el(u,v);
    91 //   }
     88    for(NodeIt v(_g);v!=INVALID;++v)
     89      for(NodeIt u(_g);u!=INVALID;++u)
     90        e=_el(u,v);
     91  }
    9292 
    93 // };
     93};
    9494
    9595int main(int, char**argv)
  • benchmark/edge_lookup_test.h

    r2239 r2252  
    190190  };
    191191
    192 //   template<class G>
    193 //   class EdgeLookUp4
    194 //   {
    195 //   public:
    196 //     GRAPH_TYPEDEFS(typename G)
    197 //     typedef G Graph;
    198 
    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;
    204    
    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 //     };
    214    
    215 //   public:
    216    
    217 //     ///Constructor
    218 //     EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
    219    
    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 //      }
    243      
    244 //     }
    245    
    246 //     ///Find an edge between two nodes.
    247    
    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.
    253 
    254 //     Edge operator()(Node s, Node t)
    255 //     {
    256 //       Edge *a=_start[s];
    257 //       Edge *b=_end[s];
    258 //       while(a!=b)
    259 //      {
    260 //        Edge *m=(Edge*)(((unsigned int)a+(unsigned int)b)/2 & 0xfffffffc);
    261 //        Node tt = _g.target(*m);
    262 //        if(tt==t) return *m;
    263 //        else if(tt<t) a=m+1;
    264 //        else b=m;
    265 //      }
    266 //       return INVALID;
    267 //     }
    268 
    269 //     ///Find the next edge
    270      
    271 //       ///\warning This function is unimplemented.
    272 //     Edge operator()(Node s, Node t, Edge prev)
    273 //     {
    274 //       return prev==INVALID?(*this)(s,t):INVALID;
    275 //     }
    276      
    277 //   };
     192  template<class G>
     193  class EdgeLookUp4
     194  {
     195  public:
     196    GRAPH_TYPEDEFS(typename G)
     197    typedef G Graph;
     198   
     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;
     204   
     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    };
     214   
     215  public:
     216   
     217    ///Constructor
     218    EdgeLookUp4(const Graph &g) :_g(g),_start(g),_end(g) {refresh();}
     219   
     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        }
     243     
     244    }
     245   
     246    ///Find an edge between two nodes.
     247   
     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.
     253
     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    }
     274
     275    ///Find the next edge
     276     
     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    }
     282     
     283  };
    278284
    279285}
Note: See TracChangeset for help on using the changeset viewer.