40 #include "chomp/system/config.h" 41 #include "chomp/system/textfile.h" 42 #include "chomp/system/timeused.h" 43 #include "chomp/system/arg.h" 44 #include "chomp/struct/digraph.h" 56 CyMeAlg Test 1.0. January 26, 2020. (C) 1997-2020 by Pawel Pilarczyk.\n\ 57 This is free software. No warranty. Consult 'license.txt' for details.";
61 This is a simple program for testing selected algorithms\n\ 62 for the computation of the minimum cycle mean of a directed graph.\n\ 63 It reads the definition of a weighted graph from a text input file\n\ 64 and measures the time of the computation of the minimum cycle mean\n\ 65 using different algorithms. The algorithms must be selected with the\n\ 66 additional switches (see below); assumes '-m' if none provided.\n\ 68 filename.txt - the name of a file that contains the definition of the graph.\n\ 69 Switches and additional arguments:\n\ 70 -k - run the classical Karp's algorithm,\n\ 71 -kr - run the Karp's algorithm with correct rounding,\n\ 72 -m - run the memory efficient algorithm,\n\ 73 -mr - run the memory efficient algorithm with correct rounding,\n\ 74 --log filename - save the output to a file (without progress indicators),\n\ 75 --quiet - suppress data output to the screen (whcih can be still logged),\n\ 76 --help - display this brief help information only and exit.\n\ 77 For more information please consult the accompanying documentation\n\ 78 or ask the program's author at http://www.PawelPilarczyk.com/.";
88 void cymealgTest (
const char *filename,
bool runKarp,
bool runKarpRnd,
89 bool runMem,
bool runMemRnd,
bool runOld,
bool runOldRnd)
91 using chomp::homology::timeused;
92 using chomp::homology::sout;
95 chomp::homology::diGraph<double> gOld;
96 if (runKarp || runKarpRnd || runMem || runMemRnd)
98 sout <<
"Reading a graph from '" << filename <<
"'... ";
100 std::ifstream in (filename);
102 chomp::homology::fileerror (filename,
"open");
104 sout << readingTime <<
".\n";
105 sout <<
"The graph has " << g. countVertices () <<
106 " vertices and " << g. countEdges () <<
" edges.\n";
108 if (runOld || runOldRnd)
110 sout <<
"Reading a graph from '" << filename <<
111 "' to the old data structure... ";
112 timeused readingTime;
113 std::ifstream in (filename);
115 chomp::homology::fileerror (filename,
"open");
117 sout << readingTime <<
".\n";
118 sout <<
"The graph has " << gOld. countVertices () <<
119 " vertices and " << gOld. countEdges () <<
126 sout <<
"Computing the minimum mean cycle weight:\n";
127 sout <<
"========================================\n";
129 double resultKarp (0);
133 sout <<
"Running the 'classical' Karp's algorithm " 134 "with default rounding...\n";
137 sout <<
"Result = " << resultKarp <<
138 ", computed in " << timeRun <<
".\n";
141 double resultKarpRnd (0);
145 sout <<
"Running the 'classical' Karp's algorithm " 146 "with rigorous rounding...\n";
149 (g, rigorousRounding, transposed);
150 sout <<
"Result = " << resultKarpRnd <<
151 ", computed in " << timeRun <<
".\n";
154 double resultMem (0);
158 sout <<
"Running the memory efficient algorithm " 159 "with default rounding...\n";
162 (g, approximateRounding, transposed);
163 sout <<
"Result = " << resultMem <<
164 ", computed in " << timeRun <<
".\n";
167 double resultMemRnd (0);
171 sout <<
"Running the memory efficient algorithm " 172 "with rigorous rounding...\n";
175 (g, rigorousRounding, transposed);
176 sout <<
"Result = " << resultMemRnd <<
177 ", computed in " << timeRun <<
".\n";
180 double resultOld (0);
184 sout <<
"Running an old memory efficient algorithm " 185 "with approximate rounding...\n";
186 chomp::homology::diGraph<double> *transposed = 0;
188 (approximateRounding, transposed);
189 sout <<
"Result = " << resultOld <<
190 ", computed in " << timeRun <<
".\n";
193 double resultOldRnd (0);
197 sout <<
"Running an old memory efficient algorithm " 198 "with rigorous rounding...\n";
199 chomp::homology::diGraph<double> *transposed = 0;
201 (rigorousRounding, transposed);
202 sout <<
"Result = " << resultOldRnd <<
203 ", computed in " << timeRun <<
".\n";
217 int main (
int argc,
char *argv [])
219 using chomp::homology::sout;
220 using chomp::homology::slog;
221 using chomp::homology::setstreams;
222 using chomp::homology::program_time;
223 using chomp::homology::commandline;
224 using chomp::homology::currenttime;
227 chomp::homology::program_time =
"Aborted after";
231 bool runKarp (
false);
232 bool runKarpRnd (
false);
234 bool runMemRnd (
false);
236 bool runOldRnd (
false);
239 chomp::homology::arguments a;
240 arg (a, NULL, filename);
241 argswitch (a,
"kr", runKarpRnd,
true);
242 argswitch (a,
"k", runKarp,
true);
243 argswitch (a,
"mr", runMemRnd,
true);
244 argswitch (a,
"m", runMem,
true);
245 argswitch (a,
"or", runOldRnd,
true);
246 argswitch (a,
"o", runOld,
true);
249 argstreamprepare (a);
250 int argresult = a. analyze (argc, argv);
255 sout <<
title <<
'\n';
260 sout <<
"Call with '--help' for help.\n";
265 if ((argresult > 0) || (!filename || !*filename))
275 if (!runKarp && !runKarpRnd && !runMem && !runMemRnd &&
276 !runOld && !runOldRnd)
281 runMem, runMemRnd, runOld, runOldRnd);
283 program_time =
"Total time used:";
287 catch (
const char *msg)
289 sout <<
"ERROR: " << msg <<
'\n';
292 catch (
const std::exception &e)
294 sout <<
"ERROR: " << e. what () <<
'\n';
299 sout <<
"ABORT: An unknown error occurred.\n";
int main(int argc, char *argv [])
The main procedure of the program.
const char * title
The title of the program and licensing information.
wType minMeanCycleWeightMem(const diGraph< wType > &g, const roundType &rounding, diGraph< wType > *transposed)
A rigorous numerics version of Karp algorithm modified in such a way that the memory usage is minimiz...
This class defines a weighted directed graph with very limited number of operations.
inType & read(inType &in, Graph &g)
Reads a graph in the text mode from an input stream.
This header file includes all the header files necessary to use the CyMeAlg implementation of the min...
const char * helpinfo
Brief help information on the program's usage.
wType minMeanCycleWeight(const diGraph< wType > &g, diGraph< wType > *transposed=0)
Runs the Karp algorithm for each strongly connected component of the graph and returns the minimum me...
A class for rounding operations which uses the BOOST library.
A dummy class for rounding operations which does not actually do any rounding.
void cymealgTest(const char *filename, bool runKarp, bool runKarpRnd, bool runMem, bool runMemRnd, bool runOld, bool runOldRnd)