1.1 --- a/benchmark/bfs-bench.cc Sat Dec 03 18:30:31 2005 +0000
1.2 +++ b/benchmark/bfs-bench.cc Mon Dec 05 17:03:31 2005 +0000
1.3 @@ -114,25 +114,25 @@
1.4 // cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
1.5 // << dim*(1<<dim) << " edges):";
1.6
1.7 - T.reset();
1.8 + T.restart();
1.9 vector<Node> nodes;
1.10 addBiDirHyperCube(G,dim,nodes);
1.11
1.12 PrintTime("GENGRAPH",T);
1.13
1.14 - T.reset();
1.15 + T.restart();
1.16 {
1.17 for(int i=0;i<mul;i++)
1.18 bfsStlQueue(G,nodes[0]);
1.19 }
1.20 PrintTime("BFS-STL",T);
1.21 - T.reset();
1.22 + T.restart();
1.23 {
1.24 for(int i=0;i<mul;i++)
1.25 bfsOwnQueue(G,nodes[0]);
1.26 }
1.27 PrintTime("BFS-OWN",T);
1.28 - T.reset();
1.29 + T.restart();
1.30 {
1.31 for(int i=0;i<mul;i++)
1.32 iteratorBench(G);
2.1 --- a/benchmark/graph-bench.cc Sat Dec 03 18:30:31 2005 +0000
2.2 +++ b/benchmark/graph-bench.cc Mon Dec 05 17:03:31 2005 +0000
2.3 @@ -48,7 +48,7 @@
2.4 makeFullGraph<ListGraph>(nextPrim(1000),nextPrim(300),nextPrim(100));
2.5
2.6 PrintTime("BIG",T);
2.7 - T.reset();
2.8 + T.restart();
2.9 makeFullGraph<ListGraph>(nextPrim(100),nextPrim(30000),nextPrim(150));
2.10
2.11 PrintTime("SMALL",T);
3.1 --- a/benchmark/hcube.cc Sat Dec 03 18:30:31 2005 +0000
3.2 +++ b/benchmark/hcube.cc Mon Dec 05 17:03:31 2005 +0000
3.3 @@ -52,13 +52,13 @@
3.4 // cout << "Creating Hipercube ("<< (1<<dim) << " nodes, "
3.5 // << dim*(1<<dim) << " edges):";
3.6
3.7 - T.reset();
3.8 + T.restart();
3.9 vector<Node> nodes;
3.10 addBiDirHyperCube(G,dim,nodes);
3.11
3.12 PrintTime("GENGRAPH",T);
3.13
3.14 - T.reset();
3.15 + T.restart();
3.16 Graph::EdgeMap<int> map(G);
3.17 for(int i=0;i<5;i++) {
3.18 Primes P;
3.19 @@ -84,7 +84,7 @@
3.20
3.21 PrintTime("GENLENGTHS",T);
3.22
3.23 - T.reset();
3.24 + T.restart();
3.25 {
3.26 Dijkstra<Graph> Dij(G,map);
3.27 for(int i=0;i<10;i++)
3.28 @@ -92,7 +92,7 @@
3.29 }
3.30 PrintTime("DIJKSTRA",T);
3.31
3.32 - T.reset();
3.33 + T.restart();
3.34 {
3.35 Graph::EdgeMap<int> flow(G);
3.36
4.1 --- a/doc/groups.dox Sat Dec 03 18:30:31 2005 +0000
4.2 +++ b/doc/groups.dox Mon Dec 05 17:03:31 2005 +0000
4.3 @@ -143,6 +143,13 @@
4.4 */
4.5
4.6 /**
4.7 +@defgroup timecount Time measuring and Counting
4.8 +@ingroup misc
4.9 +Here you can find simple tools for measuring the performance
4.10 +of algorithms.
4.11 +*/
4.12 +
4.13 +/**
4.14 @defgroup io_group Input Output
4.15 Here you can find tools for imporing and exporting graphs and graph related
4.16 data
5.1 --- a/lemon/Makefile.am Sat Dec 03 18:30:31 2005 +0000
5.2 +++ b/lemon/Makefile.am Mon Dec 05 17:03:31 2005 +0000
5.3 @@ -27,6 +27,7 @@
5.4 dfs.h \
5.5 bin_heap.h \
5.6 config.h \
5.7 + counter.h \
5.8 dijkstra.h \
5.9 dimacs.h \
5.10 edge_set.h \
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/lemon/counter.h Mon Dec 05 17:03:31 2005 +0000
6.3 @@ -0,0 +1,171 @@
6.4 +/* -*- C++ -*-
6.5 + * lemon/counter.h -
6.6 + * Part of LEMON, a generic C++ optimization library
6.7 + *
6.8 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
6.9 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
6.10 + *
6.11 + * Permission to use, modify and distribute this software is granted
6.12 + * provided that this copyright notice appears in all copies. For
6.13 + * precise terms see the accompanying LICENSE file.
6.14 + *
6.15 + * This software is provided "AS IS" with no warranty of any kind,
6.16 + * express or implied, and with no claim as to its suitability for any
6.17 + * purpose.
6.18 + *
6.19 + */
6.20 +
6.21 +#ifndef LEMON_COUNTER_H
6.22 +#define LEMON_COUNTER_H
6.23 +
6.24 +#include <string>
6.25 +#include <iostream>
6.26 +
6.27 +///\ingroup timecount
6.28 +///\file
6.29 +///\brief Tools for counting steps and events
6.30 +
6.31 +namespace lemon
6.32 +{
6.33 +
6.34 + template<class P> class _SubNoCounter;
6.35 +
6.36 + template<class P>
6.37 + class _SubCounter
6.38 + {
6.39 + P &_parent;
6.40 + std::string _title;
6.41 + std::ostream &_os;
6.42 + int count;
6.43 + public:
6.44 +
6.45 + typedef _SubCounter<_SubCounter<P> > SubCounter;
6.46 + typedef _SubNoCounter<_SubCounter<P> > SubNoCounter;
6.47 +
6.48 + _SubCounter(P &parent)
6.49 + : _parent(parent), _title(), _os(std::cerr), count(0) {}
6.50 + _SubCounter(P &parent,std::string title,std::ostream &os=std::cerr)
6.51 + : _parent(parent), _title(title), _os(os), count(0) {}
6.52 + _SubCounter(P &parent,const char *title,std::ostream &os=std::cerr)
6.53 + : _parent(parent), _title(title), _os(os), count(0) {}
6.54 + ~_SubCounter() {
6.55 + _os << _title << count <<std::endl;
6.56 + _parent+=count;
6.57 + }
6.58 + _SubCounter &operator++() { count++; return *this;}
6.59 + int operator++(int) { return count++; }
6.60 + _SubCounter &operator--() { count--; return *this;}
6.61 + int operator--(int) { return count--; }
6.62 + _SubCounter &operator+=(int c) { count+=c; return *this;}
6.63 + _SubCounter &operator-=(int c) { count-=c; return *this;}
6.64 + void reset(int c=0) {count=c;}
6.65 + operator int() {return count;}
6.66 + };
6.67 +
6.68 + template<class P>
6.69 + class _SubNoCounter
6.70 + {
6.71 + P &_parent;
6.72 + public:
6.73 + typedef _SubNoCounter<_SubNoCounter<P> > SubCounter;
6.74 + typedef _SubNoCounter<_SubNoCounter<P> > SubNoCounter;
6.75 +
6.76 + _SubNoCounter(P &parent) :_parent(parent) {}
6.77 + _SubNoCounter(P &parent,std::string title,std::ostream &os=std::cerr)
6.78 + :_parent(parent) {}
6.79 + _SubNoCounter(P &parent,const char *title,std::ostream &os=std::cerr)
6.80 + :_parent(parent) {}
6.81 + ~_SubNoCounter() {}
6.82 + _SubNoCounter &operator++() { ++_parent; return *this;}
6.83 + int operator++(int) { _parent++; return 0;}
6.84 + _SubNoCounter &operator--() { --_parent; return *this;}
6.85 + int operator--(int) { _parent--; return 0;}
6.86 + _SubNoCounter &operator+=(int c) { _parent+=c; return *this;}
6.87 + _SubNoCounter &operator-=(int c) { _parent-=c; return *this;}
6.88 + void reset(int c=0) {}
6.89 + operator int() {return 0;}
6.90 + };
6.91 +
6.92 +
6.93 + /// \addtogroup timecount
6.94 + /// @{
6.95 +
6.96 + ///A counter class
6.97 +
6.98 + ///This class makes it easier to count certain events. You can increment
6.99 + ///or decrement the counter using operator++ and operator--.
6.100 + ///A report is automatically printed on destruction.
6.101 + class Counter
6.102 + {
6.103 + std::string _title;
6.104 + std::ostream &_os;
6.105 + int count;
6.106 + public:
6.107 + ///\e
6.108 +
6.109 + ///\todo document please.
6.110 + ///
6.111 + typedef _SubCounter<Counter> SubCounter;
6.112 + ///\e
6.113 +
6.114 + ///\todo document please.
6.115 + ///
6.116 + typedef _SubNoCounter<Counter> SubNoCounter;
6.117 +
6.118 + ///\e
6.119 + Counter() : _title(), _os(std::cerr), count(0) {}
6.120 + ///\e
6.121 + Counter(std::string title,std::ostream &os=std::cerr)
6.122 + : _title(title), _os(os), count(0) {}
6.123 + ///\e
6.124 + Counter(const char *title,std::ostream &os=std::cerr)
6.125 + : _title(title), _os(os), count(0) {}
6.126 + ///Destructor. Prints the given title and the value of the counter.
6.127 + ~Counter() {
6.128 + _os << _title << count <<std::endl;
6.129 + }
6.130 + ///\e
6.131 + Counter &operator++() { count++; return *this;}
6.132 + ///\e
6.133 + int operator++(int) { return count++;}
6.134 + ///\e
6.135 + Counter &operator--() { count--; return *this;}
6.136 + ///\e
6.137 + int operator--(int) { return count--;}
6.138 + ///\e
6.139 + Counter &operator+=(int c) { count+=c; return *this;}
6.140 + ///\e
6.141 + Counter &operator-=(int c) { count-=c; return *this;}
6.142 + ///\e
6.143 + void reset(int c=0) {count=c;}
6.144 + ///\e
6.145 + operator int() {return count;}
6.146 + };
6.147 +
6.148 + ///'Do nothing' version of \ref Counter
6.149 +
6.150 + ///'Do nothing' version of \ref Counter.
6.151 + ///\sa Counter
6.152 + class NoCounter
6.153 + {
6.154 + public:
6.155 + typedef _SubNoCounter<NoCounter> SubCounter;
6.156 + typedef _SubNoCounter<NoCounter> SubNoCounter;
6.157 +
6.158 + NoCounter() {}
6.159 + NoCounter(std::string title,std::ostream &os=std::cerr) {}
6.160 + NoCounter(const char *title,std::ostream &os=std::cerr) {}
6.161 + NoCounter &operator++() { return *this; }
6.162 + int operator++(int) { return 0; }
6.163 + NoCounter &operator--() { return *this; }
6.164 + int operator--(int) { return 0; }
6.165 + NoCounter &operator+=(int c) { return *this;}
6.166 + NoCounter &operator-=(int c) { return *this;}
6.167 + void reset(int c=0) {}
6.168 + operator int() {return 0;}
6.169 + };
6.170 +
6.171 + ///@}
6.172 +}
6.173 +
6.174 +#endif
7.1 --- a/lemon/simann.h Sat Dec 03 18:30:31 2005 +0000
7.2 +++ b/lemon/simann.h Mon Dec 05 17:03:31 2005 +0000
7.3 @@ -4,6 +4,9 @@
7.4 /// \ingroup experimental
7.5 /// \file
7.6 /// \brief Simulated annealing framework.
7.7 +///
7.8 +/// \todo A test and some demo should be added
7.9 +/// \todo Doc should be improved
7.10 /// \author Akos Ladanyi
7.11
7.12 #include <cstdlib>
7.13 @@ -298,7 +301,7 @@
7.14 start_threshold = 5.0 * fabs(simann->getBestCost() - avg_cost);
7.15 temp = 10000.0;
7.16 warmup = false;
7.17 - timer.reset();
7.18 + timer.restart();
7.19 }
7.20 }
7.21 }
8.1 --- a/lemon/time_measure.h Sat Dec 03 18:30:31 2005 +0000
8.2 +++ b/lemon/time_measure.h Mon Dec 05 17:03:31 2005 +0000
8.3 @@ -17,7 +17,7 @@
8.4 #ifndef LEMON_TIME_MEASURE_H
8.5 #define LEMON_TIME_MEASURE_H
8.6
8.7 -///\ingroup misc
8.8 +///\ingroup timecount
8.9 ///\file
8.10 ///\brief Tools for measuring cpu usage
8.11
8.12 @@ -29,7 +29,7 @@
8.13
8.14 namespace lemon {
8.15
8.16 - /// \addtogroup misc
8.17 + /// \addtogroup timecount
8.18 /// @{
8.19
8.20 /// A class to store (cpu)time instances.
8.21 @@ -209,7 +209,7 @@
8.22 /// Timer T;
8.23 /// doSomething();
8.24 /// std::cout << T << '\n';
8.25 - /// T.reset();
8.26 + /// T.restart();
8.27 /// doSomethingElse();
8.28 /// std::cout << T << '\n';
8.29 ///
8.30 @@ -223,7 +223,8 @@
8.31 ///running times.
8.32 ///
8.33 ///\warning Depending on the operation system and its actual configuration
8.34 - ///the time counters have a certain (relatively big) granularity.
8.35 + ///the time counters have a certain (10ms on a typical Linux system)
8.36 + ///granularity.
8.37 ///Therefore this tool is not appropriate to measure very short times.
8.38 ///Also, if you start and stop the timer very frequently, it could lead
8.39 ///distorted results.
8.40 @@ -238,18 +239,18 @@
8.41 ///\author Alpar Juttner
8.42 class Timer
8.43 {
8.44 - int running; //Timer is running iff running>0; (running>=0 always holds)
8.45 + int _running; //Timer is running iff _running>0; (_running>=0 always holds)
8.46 TimeStamp start_time; //This is the relativ start-time if the timer
8.47 - //is running, the collected running time otherwise.
8.48 + //is _running, the collected _running time otherwise.
8.49
8.50 - void _reset() {if(running) start_time.stamp(); else start_time.reset();}
8.51 + void _reset() {if(_running) start_time.stamp(); else start_time.reset();}
8.52
8.53 public:
8.54 ///Constructor.
8.55
8.56 ///\param _running indicates whether or not the timer starts immediately.
8.57 ///
8.58 - Timer(bool _running=true) :running(_running) {_reset();}
8.59 + Timer(bool run=true) :_running(run) {_reset();}
8.60
8.61 ///Computes the ellapsed time
8.62
8.63 @@ -259,15 +260,16 @@
8.64 {
8.65 TimeStamp t;
8.66 t.stamp();
8.67 - return running?t-start_time:start_time;
8.68 + return _running?t-start_time:start_time;
8.69 }
8.70
8.71 - ///Resets the time counters
8.72 + ///Reset and stop the time counters
8.73
8.74 - ///Resets the time counters
8.75 - ///
8.76 + ///This function resets and stops the time counters
8.77 + ///\sa restart()
8.78 void reset()
8.79 {
8.80 + _running=0;
8.81 _reset();
8.82 }
8.83
8.84 @@ -280,27 +282,74 @@
8.85 ///\sa stop()
8.86 void start()
8.87 {
8.88 - if(running) running++;
8.89 + if(_running) _running++;
8.90 else {
8.91 TimeStamp t;
8.92 t.stamp();
8.93 start_time=t-start_time;
8.94 }
8.95 }
8.96 +
8.97
8.98 ///Stop the time counters
8.99
8.100 - ///This function stops the time counters.
8.101 - ///
8.102 - ///\sa stop()
8.103 + ///This function stops the time counters. If start() was executed more than
8.104 + ///once, then the same number of stop() execution is necessary the really
8.105 + ///stop the timer.
8.106 + ///
8.107 + ///\sa halt()
8.108 + ///\sa start()
8.109 + ///\sa restart()
8.110 + ///\sa reset()
8.111 +
8.112 void stop()
8.113 {
8.114 - if(running && !--running) {
8.115 + if(_running && !--_running) {
8.116 TimeStamp t;
8.117 t.stamp();
8.118 start_time=t-start_time;
8.119 }
8.120 }
8.121 +
8.122 + ///Halt (i.e stop immediately) the time counters
8.123 +
8.124 + ///This function stops immediately the time counters.
8.125 + ///
8.126 + ///\sa stop()
8.127 + ///\sa restart()
8.128 + ///\sa reset()
8.129 +
8.130 + void halt()
8.131 + {
8.132 + if(_running) {
8.133 + _running=0;
8.134 + TimeStamp t;
8.135 + t.stamp();
8.136 + start_time=t-start_time;
8.137 + }
8.138 + }
8.139 +
8.140 + ///Returns the running state of the timer
8.141 +
8.142 + ///This function returns the number of stop() exections that is
8.143 + ///necessary to really stop the timer.
8.144 + ///For example the timer
8.145 + ///is running if and only if the return value is \c true
8.146 + ///(i.e. greater than
8.147 + ///zero).
8.148 + int running() { return _running; }
8.149 +
8.150 +
8.151 + ///Restart the time counters
8.152 +
8.153 + ///This function is a shorthand for
8.154 + ///a reset() and a start() calls.
8.155 + ///
8.156 + void restart()
8.157 + {
8.158 + reset();
8.159 + start();
8.160 + }
8.161
8.162 ///Gives back the ellapsed user time of the process
8.163 double userTime() const
8.164 @@ -330,6 +379,25 @@
8.165
8.166 };
8.167
8.168 + ///Same as \ref Timer but prints a report on destruction.
8.169 +
8.170 + ///Same as \ref Timer but prints a report on destruction.
8.171 + ///\todo Untested
8.172 + class TimeReport : public Timer
8.173 + {
8.174 + std::string _title;
8.175 + std::ostream &_os;
8.176 + public:
8.177 + ///\e
8.178 +
8.179 + TimeReport(std::string title,std::ostream &os,bool run)
8.180 + : Timer(run), _title(title), _os(os){}
8.181 + ~TimeReport()
8.182 + {
8.183 + _os << _title << this << std::endl;
8.184 + }
8.185 + };
8.186 +
8.187 ///Prints the time counters
8.188
8.189 ///Prints the time counters in the following form:
9.1 --- a/test/Makefile.am Sat Dec 03 18:30:31 2005 +0000
9.2 +++ b/test/Makefile.am Mon Dec 05 17:03:31 2005 +0000
9.3 @@ -13,6 +13,7 @@
9.4 check_PROGRAMS = \
9.5 all_pairs_shortest_path_test \
9.6 bfs_test \
9.7 + counter_test \
9.8 dfs_test \
9.9 dijkstra_test \
9.10 graph_test \
9.11 @@ -48,6 +49,7 @@
9.12
9.13 all_pairs_shortest_path_test_SOURCES = all_pairs_shortest_path_test.cc
9.14 bfs_test_SOURCES = bfs_test.cc
9.15 +counter_test_SOURCES = counter_test.cc
9.16 dfs_test_SOURCES = dfs_test.cc
9.17 dijkstra_test_SOURCES = dijkstra_test.cc
9.18 graph_test_SOURCES = graph_test.cc
10.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
10.2 +++ b/test/counter_test.cc Mon Dec 05 17:03:31 2005 +0000
10.3 @@ -0,0 +1,64 @@
10.4 +/* -*- C++ -*-
10.5 + * test/counter_test.cc - Part of LEMON, a generic C++ optimization library
10.6 + *
10.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
10.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
10.9 + *
10.10 + * Permission to use, modify and distribute this software is granted
10.11 + * provided that this copyright notice appears in all copies. For
10.12 + * precise terms see the accompanying LICENSE file.
10.13 + *
10.14 + * This software is provided "AS IS" with no warranty of any kind,
10.15 + * express or implied, and with no claim as to its suitability for any
10.16 + * purpose.
10.17 + *
10.18 + */
10.19 +
10.20 +#include <lemon/counter.h>
10.21 +
10.22 +///\file \brief Test cases for time_measure.h
10.23 +///
10.24 +///\todo To be extended
10.25 +
10.26 +
10.27 +int fibonacci(int f)
10.28 +{
10.29 + static lemon::Counter count("Fibonacci steps: ");
10.30 + count++;
10.31 + if(f<1) return 0;
10.32 + else if(f==1) return 1;
10.33 + else return fibonacci(f-1)+fibonacci(f-2);
10.34 +}
10.35 +
10.36 +int main()
10.37 +{
10.38 + fibonacci(10);
10.39 +
10.40 + {
10.41 + typedef lemon::Counter MyCounter;
10.42 + MyCounter c("Main counter: ");
10.43 + c++;
10.44 + c++;
10.45 + MyCounter::SubCounter d(c,"Subcounter: ");
10.46 + d++;
10.47 + d++;
10.48 + MyCounter::SubCounter::SubCounter e(d,"SubSubCounter: ");
10.49 + e++;
10.50 + e++;
10.51 + }
10.52 +
10.53 + {
10.54 + typedef lemon::NoCounter MyCounter;
10.55 + MyCounter c("Main counter: ");
10.56 + c++;
10.57 + c++;
10.58 + MyCounter::SubCounter d(c,"Subcounter: ");
10.59 + d++;
10.60 + d++;
10.61 + MyCounter::SubCounter::SubCounter e(d,"SubSubCounter: ");
10.62 + e++;
10.63 + e++;
10.64 + }
10.65 +
10.66 + return 0;
10.67 +}
11.1 --- a/test/time_measure_test.cc Sat Dec 03 18:30:31 2005 +0000
11.2 +++ b/test/time_measure_test.cc Mon Dec 05 17:03:31 2005 +0000
11.3 @@ -36,7 +36,7 @@
11.4 int n;
11.5 for(n=0;T.realTime()<1.0;n++) ;
11.6 std::cout << T << " (" << n << " time queries)\n";
11.7 - T.reset();
11.8 + T.restart();
11.9 while(T.realTime()<2.0) ;
11.10 std::cout << T << '\n';
11.11 TimeStamp full;