alpar@699: #include<math.h> alpar@921: #include<lemon/list_graph.h> alpar@711: alpar@711: #include"bench_tools.h" alpar@699: alpar@921: using namespace lemon; alpar@699: alpar@699: ///Makes a full graph by adding and deleting a lot of edges; alpar@699: alpar@699: ///\param n Number of nodes. alpar@699: ///\param rat The funcion will make \f$rat\timesn^2\f$ edge addition and alpar@699: ///\f$(rat-1)\timesn^2\f$ deletion. alpar@699: ///\param p Tuning parameters. alpar@699: ///\warning \c rat, \c p, and \c n must be pairwise relative primes. alpar@699: template <class Graph> alpar@699: void makeFullGraph(int n, int rat, int p) alpar@699: { alpar@699: GRAPH_TYPEDEF_FACTORY(Graph); alpar@699: alpar@699: Graph G; alpar@699: alpar@708: // Node nodes[n]; alpar@708: std::vector<Node> nodes(n); alpar@699: for(int i=0;i<n;i++) nodes[i]=G.addNode(); alpar@699: alpar@708: //Edge equ[rat]; alpar@708: std::vector<Edge> equ(rat); alpar@699: alpar@718: long long int count; alpar@699: alpar@699: for(count=0;count<rat;count++) { alpar@699: equ[count%rat]=G.addEdge(nodes[(count*p)%n],nodes[(count*p/n)%n]); alpar@699: } alpar@699: for(;(count%rat)||((count*p)%n)||((count*p/n)%n);count++) { alpar@699: // if(!(count%1000000)) fprintf(stderr,"%d\r",count); alpar@699: if(count%rat) G.erase(equ[count%rat]); alpar@699: equ[count%rat]=G.addEdge(nodes[(count*p)%n],nodes[(count*p/n)%n]); alpar@699: } alpar@718: // std::cout << "Added " << count alpar@718: // << " ( " << n << "^2 * " << rat << " ) edges\n"; alpar@718: alpar@718: alpar@699: // for(int i=0;1;i++) ; alpar@699: } alpar@699: alpar@699: int main() alpar@699: { alpar@921: lemon::Timer T; alpar@699: makeFullGraph<ListGraph>(nextPrim(1000),nextPrim(300),nextPrim(100)); alpar@718: alpar@718: PrintTime("BIG",T); alpar@699: T.reset(); alpar@699: makeFullGraph<ListGraph>(nextPrim(100),nextPrim(30000),nextPrim(150)); alpar@718: alpar@718: PrintTime("SMALL",T); alpar@699: }