The CyMeAlg Software (Release 0.01)
cymealgtest.cpp
Go to the documentation of this file.
1 /// @addtogroup test
2 /// @{
3 
4 /////////////////////////////////////////////////////////////////////////////
5 ///
6 /// \file
7 ///
8 /// This is a simple program for testing selected algorithms
9 /// for the computation of the minimum cycle mean of a directed graph.
10 /// It reads the definition of a weighted graph from a text input file
11 /// and measures the time of the computation of the minimum cycle mean
12 /// using different algorithms.
13 ///
14 /////////////////////////////////////////////////////////////////////////////
15 
16 // Copyright (C) 1997-2020 by Pawel Pilarczyk.
17 //
18 // This file is part of my research software. This is free software:
19 // you can redistribute it and/or modify it under the terms of the GNU
20 // General Public License as published by the Free Software Foundation,
21 // either version 3 of the License, or (at your option) any later version.
22 //
23 // This software is distributed in the hope that it will be useful,
24 // but WITHOUT ANY WARRANTY; without even the implied warranty of
25 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
26 // GNU General Public License for more details.
27 //
28 // You should have received a copy of the GNU General Public License
29 // along with this software; see the file "license.txt". If not,
30 // please, see <http://www.gnu.org/licenses/>.
31 
32 // Started on November 24, 2014. Last revision: August 23, 2019.
33 
34 
35 // include some standard C++ header files
36 #include <iostream>
37 #include <fstream>
38 
39 // include selected header files from the CHomP library
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"
45 
46 // include relevant local header files
47 #include "cymealg.h"
48 
49 
50 // --------------------------------------------------
51 // -------------------- OVERTURE --------------------
52 // --------------------------------------------------
53 
54 /// The title of the program and licensing information.
55 const char *title = "\
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.";
58 
59 /// Brief help information on the program's usage.
60 const char *helpinfo = "\
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\
67 Call with:\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/.";
79 
80 //-o - run an older version of the memory efficient algorithm,
81 //-or - run the older version with correct rounding,
82 
83 
84 // --------------------------------------------------
85 // ---------------------- test ----------------------
86 // --------------------------------------------------
87 
88 void cymealgTest (const char *filename, bool runKarp, bool runKarpRnd,
89  bool runMem, bool runMemRnd, bool runOld, bool runOldRnd)
90 {
91  using chomp::homology::timeused;
92  using chomp::homology::sout;
93 
95  chomp::homology::diGraph<double> gOld;
96  if (runKarp || runKarpRnd || runMem || runMemRnd)
97  {
98  sout << "Reading a graph from '" << filename << "'... ";
99  timeused readingTime;
100  std::ifstream in (filename);
101  if (!in)
102  chomp::homology::fileerror (filename, "open");
103  in >> g;
104  sout << readingTime << ".\n";
105  sout << "The graph has " << g. countVertices () <<
106  " vertices and " << g. countEdges () << " edges.\n";
107  }
108  if (runOld || runOldRnd)
109  {
110  sout << "Reading a graph from '" << filename <<
111  "' to the old data structure... ";
112  timeused readingTime;
113  std::ifstream in (filename);
114  if (!in)
115  chomp::homology::fileerror (filename, "open");
116  cymealg::read (in, gOld);
117  sout << readingTime << ".\n";
118  sout << "The graph has " << gOld. countVertices () <<
119  " vertices and " << gOld. countEdges () <<
120  " edges.\n";
121  }
122 
123  const cymealg::tBoostRounding<double> rigorousRounding;
124  const cymealg::dummyRounding<double> approximateRounding;
125 
126  sout << "Computing the minimum mean cycle weight:\n";
127  sout << "========================================\n";
128 
129  double resultKarp (0);
130  if (runKarp)
131  {
132  timeused timeRun;
133  sout << "Running the 'classical' Karp's algorithm "
134  "with default rounding...\n";
135  cymealg::diGraph<double> *transposed = 0;
136  resultKarp = minMeanCycleWeight (g, transposed);
137  sout << "Result = " << resultKarp <<
138  ", computed in " << timeRun << ".\n";
139  }
140 
141  double resultKarpRnd (0);
142  if (runKarpRnd)
143  {
144  timeused timeRun;
145  sout << "Running the 'classical' Karp's algorithm "
146  "with rigorous rounding...\n";
147  cymealg::diGraph<double> *transposed = 0;
148  resultKarpRnd = minMeanCycleWeight
149  (g, rigorousRounding, transposed);
150  sout << "Result = " << resultKarpRnd <<
151  ", computed in " << timeRun << ".\n";
152  }
153 
154  double resultMem (0);
155  if (runMem)
156  {
157  timeused timeRun;
158  sout << "Running the memory efficient algorithm "
159  "with default rounding...\n";
160  cymealg::diGraph<double> *transposed = 0;
161  resultMem = minMeanCycleWeightMem
162  (g, approximateRounding, transposed);
163  sout << "Result = " << resultMem <<
164  ", computed in " << timeRun << ".\n";
165  }
166 
167  double resultMemRnd (0);
168  if (runMemRnd)
169  {
170  timeused timeRun;
171  sout << "Running the memory efficient algorithm "
172  "with rigorous rounding...\n";
173  cymealg::diGraph<double> *transposed = 0;
174  resultMemRnd = minMeanCycleWeightMem
175  (g, rigorousRounding, transposed);
176  sout << "Result = " << resultMemRnd <<
177  ", computed in " << timeRun << ".\n";
178  }
179 
180  double resultOld (0);
181  if (runOld)
182  {
183  timeused timeRun;
184  sout << "Running an old memory efficient algorithm "
185  "with approximate rounding...\n";
186  chomp::homology::diGraph<double> *transposed = 0;
187  resultOld = gOld. minMeanCycleWeightMem
188  (approximateRounding, transposed);
189  sout << "Result = " << resultOld <<
190  ", computed in " << timeRun << ".\n";
191  }
192 
193  double resultOldRnd (0);
194  if (runOldRnd)
195  {
196  timeused timeRun;
197  sout << "Running an old memory efficient algorithm "
198  "with rigorous rounding...\n";
199  chomp::homology::diGraph<double> *transposed = 0;
200  resultOldRnd = gOld. minMeanCycleWeightMem
201  (rigorousRounding, transposed);
202  sout << "Result = " << resultOldRnd <<
203  ", computed in " << timeRun << ".\n";
204  }
205 
206 // sout << g;
207 
208  return;
209 } /* cymealgTest */
210 
211 // --------------------------------------------------
212 // ---------------------- main ----------------------
213 // --------------------------------------------------
214 
215 /// The main procedure of the program.
216 /// Returns: 0 = Ok, -1 = Error, 1 = Help displayed, 2 = Wrong arguments.
217 int main (int argc, char *argv [])
218 {
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;
225 
226  // turn on a message that will appear if the program does not finish
227  chomp::homology::program_time = "Aborted after";
228 
229  // prepare user-configurable data
230  char *filename (0);
231  bool runKarp (false);
232  bool runKarpRnd (false);
233  bool runMem (false);
234  bool runMemRnd (false);
235  bool runOld (false);
236  bool runOldRnd (false);
237 
238  // analyze the command line
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);
247  arghelp (a);
248 
249  argstreamprepare (a);
250  int argresult = a. analyze (argc, argv);
251  argstreamset ();
252 
253  // show the program's title
254  if (argresult >= 0)
255  sout << title << '\n';
256 
257  // if something was incorrect, show an additional message and exit
258  if (argresult < 0)
259  {
260  sout << "Call with '--help' for help.\n";
261  return 2;
262  }
263 
264  // if help requested or no filename present, show help information
265  if ((argresult > 0) || (!filename || !*filename))
266  {
267  sout << helpinfo << '\n';
268  return 1;
269  }
270 
271  // try running the main function and catch an error message if thrown
272  try
273  {
274  // run the test with the given filename
275  if (!runKarp && !runKarpRnd && !runMem && !runMemRnd &&
276  !runOld && !runOldRnd)
277  {
278  runMem = true;
279  }
280  cymealgTest (filename, runKarp, runKarpRnd,
281  runMem, runMemRnd, runOld, runOldRnd);
282 
283  program_time = "Total time used:";
284  program_time = 1;
285  return 0;
286  }
287  catch (const char *msg)
288  {
289  sout << "ERROR: " << msg << '\n';
290  return -1;
291  }
292  catch (const std::exception &e)
293  {
294  sout << "ERROR: " << e. what () << '\n';
295  return -1;
296  }
297  catch (...)
298  {
299  sout << "ABORT: An unknown error occurred.\n";
300  return -1;
301  }
302 } /* main */
303 
304 
305 /// @}
306 
int main(int argc, char *argv [])
The main procedure of the program.
const char * title
The title of the program and licensing information.
Definition: cymealgtest.cpp:55
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...
Definition: cyclemean.h:433
This class defines a weighted directed graph with very limited number of operations.
Definition: digraph.h:75
inType & read(inType &in, Graph &g)
Reads a graph in the text mode from an input stream.
Definition: readwrite.h:47
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&#39;s usage.
Definition: cymealgtest.cpp:60
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...
Definition: cyclemean.h:48
A class for rounding operations which uses the BOOST library.
Definition: boostrnd.h:48
A dummy class for rounding operations which does not actually do any rounding.
Definition: dummyrnd.h:45
void cymealgTest(const char *filename, bool runKarp, bool runKarpRnd, bool runMem, bool runMemRnd, bool runOld, bool runOldRnd)
Definition: cymealgtest.cpp:88