COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 2272:f6b352fdc6b1 in lemon-0.x for benchmark


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

Turn off 32 bit only tests.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • benchmark/edge_lookup.cc

    r2271 r2272  
    173173  };
    174174
    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   };
     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//   };
    361361
    362362GRAPH_TYPEDEFS(SmartGraph)
    … …  
    497497  TimeStamp t3 = runningTimeTest(EL2(g),1);
    498498  TimeStamp t4 = runningTimeTest(EL3(g),1);
    499   TimeStamp t5 = runningTimeTest(EL4(g),1);
    500   TimeStamp t6 = runningTimeTest(EL5(g),1);
     499//   TimeStamp t5 = runningTimeTest(EL4(g),1);
     500//   TimeStamp t6 = runningTimeTest(EL5(g),1);
    501501
    502502  std::cout << t1.userTime()/N/N << ' '
    … …  
    504504            << t3.userTime()/N/N << ' '
    505505            << t4.userTime()/N/N << ' '
    506             << t5.userTime()/N/N << ' '
    507             << t6.userTime()/N/N
     506//          << t5.userTime()/N/N << ' '
     507//          << t6.userTime()/N/N
    508508            << std::endl;
    509509}
Note: See TracChangeset for help on using the changeset viewer.