Redesigned CapacityScaling algorithm with almost the same interface.
The new version does not use the ResidualGraphAdaptor for performance reasons.
Scaling can be enabled and disabled with a parameter of the run() function.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_BENCH_TEST_H
20 #define LEMON_BENCH_TEST_H
25 #include<lemon/graph_utils.h>
26 #include<lemon/time_measure.h>
28 ///A primitive primtest
30 ///\bug 2 is not a prime according to this function!
32 ///\bug This function should go out of header file. I'm making it
34 inline bool isPrim(int n)
37 for(int k=3;n/k>=k;k+=2)
38 if(!(n%k)) return false;
44 ///Finds the smallest prime not less then \c n.
46 ///\bug This function should go out of header file. I'm making it
48 inline int nextPrim(int n)
50 for(n+=!(n%2);!isPrim(n);n+=2) ;
55 /// Class to generate consecutive primes
58 std::vector<int> primes;
63 for(int i=0;m<primes[i]*primes[i];i++) if(!(m%primes[i])) return false;
71 if(primes.size()==0) {
76 do n+=2; while(!isPrime(n));
83 inline void PrintTime(const char *ID, lemon::Timer &T)
85 lemon::TimeStamp S(T);
86 std::cout << ID << ' ' << S.userTime() << ' '
87 << S.systemTime() << ' ' << S.realTime() << std::endl;
94 void addHyperCube(Graph &G,int dim,std::vector<typename Graph::Node> &nodes)
96 GRAPH_TYPEDEFS(typename Graph);
98 std::vector<int> bits(dim+1);
100 for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
102 for(int i=0;i<bits[dim];i++) {
103 nodes.push_back(G.addNode());
104 for(int j=0;j<dim;j++) if(i&bits[j]) G.addEdge(nodes[i-bits[j]],nodes[i]);
109 template<class Graph>
110 void addBiDirHyperCube(Graph &G,int dim,std::vector<typename Graph::Node>&nodes)
112 GRAPH_TYPEDEFS(typename Graph);
114 std::vector<int> bits(dim+1);
116 for(int i=1;i<=dim;i++) bits[i]=2*bits[i-1];
118 for(int i=0;i<bits[dim];i++) {
119 nodes.push_back(G.addNode());
120 for(int j=0;j<dim;j++) if(i&bits[j]) {
121 G.addEdge(nodes[i-bits[j]],nodes[i]);
122 G.addEdge(nodes[i],nodes[i-bits[j]]);