Location: LEMON/LEMON-official/lemon/bits/windows.cc - annotation
Load file history
Rework and fix the implementation of MinMeanCycle (#179)
- Fix the handling of the cycle means.
- Many implementation improvements:
- More efficient data storage for the strongly connected
components.
- Better handling of BFS queues.
- Merge consecutive BFS searches (perform two BFS searches
instead of three).
This version is about two times faster on average and an order of
magnitude faster if there are a lot of strongly connected components.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 | r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r513:3f0ddf255524 r513:3f0ddf255524 r513:3f0ddf255524 r511:879c55700cd4 r513:3f0ddf255524 r513:3f0ddf255524 r513:3f0ddf255524 r513:3f0ddf255524 r513:3f0ddf255524 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r513:3f0ddf255524 r513:3f0ddf255524 r513:3f0ddf255524 r513:3f0ddf255524 r513:3f0ddf255524 r513:3f0ddf255524 r513:3f0ddf255524 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 r511:879c55700cd4 | /* -*- mode: C++; indent-tabs-mode: nil; -*-
*
* This file is a part of LEMON, a generic C++ optimization library.
*
* Copyright (C) 2003-2009
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
*
* Permission to use, modify and distribute this software is granted
* provided that this copyright notice appears in all copies. For
* precise terms see the accompanying LICENSE file.
*
* This software is provided "AS IS" with no warranty of any kind,
* express or implied, and with no claim as to its suitability for any
* purpose.
*
*/
///\file
///\brief Some basic non-inline functions and static global data.
#include<lemon/bits/windows.h>
#ifdef WIN32
#ifndef WIN32_LEAN_AND_MEAN
#define WIN32_LEAN_AND_MEAN
#endif
#ifndef NOMINMAX
#define NOMINMAX
#endif
#ifdef UNICODE
#undef UNICODE
#endif
#include <windows.h>
#ifdef LOCALE_INVARIANT
#define MY_LOCALE LOCALE_INVARIANT
#else
#define MY_LOCALE LOCALE_NEUTRAL
#endif
#else
#include <unistd.h>
#include <ctime>
#include <sys/times.h>
#include <sys/time.h>
#endif
#include <cmath>
#include <sstream>
namespace lemon {
namespace bits {
void getWinProcTimes(double &rtime,
double &utime, double &stime,
double &cutime, double &cstime)
{
#ifdef WIN32
static const double ch = 4294967296.0e-7;
static const double cl = 1.0e-7;
FILETIME system;
GetSystemTimeAsFileTime(&system);
rtime = ch * system.dwHighDateTime + cl * system.dwLowDateTime;
FILETIME create, exit, kernel, user;
if (GetProcessTimes(GetCurrentProcess(),&create, &exit, &kernel, &user)) {
utime = ch * user.dwHighDateTime + cl * user.dwLowDateTime;
stime = ch * kernel.dwHighDateTime + cl * kernel.dwLowDateTime;
cutime = 0;
cstime = 0;
} else {
rtime = 0;
utime = 0;
stime = 0;
cutime = 0;
cstime = 0;
}
#else
timeval tv;
gettimeofday(&tv, 0);
rtime=tv.tv_sec+double(tv.tv_usec)/1e6;
tms ts;
double tck=sysconf(_SC_CLK_TCK);
times(&ts);
utime=ts.tms_utime/tck;
stime=ts.tms_stime/tck;
cutime=ts.tms_cutime/tck;
cstime=ts.tms_cstime/tck;
#endif
}
std::string getWinFormattedDate()
{
std::ostringstream os;
#ifdef WIN32
SYSTEMTIME time;
GetSystemTime(&time);
char buf1[11], buf2[9], buf3[5];
if (GetDateFormat(MY_LOCALE, 0, &time,
("ddd MMM dd"), buf1, 11) &&
GetTimeFormat(MY_LOCALE, 0, &time,
("HH':'mm':'ss"), buf2, 9) &&
GetDateFormat(MY_LOCALE, 0, &time,
("yyyy"), buf3, 5)) {
os << buf1 << ' ' << buf2 << ' ' << buf3;
}
else os << "unknown";
#else
timeval tv;
gettimeofday(&tv, 0);
char cbuf[26];
ctime_r(&tv.tv_sec,cbuf);
os << cbuf;
#endif
return os.str();
}
int getWinRndSeed()
{
#ifdef WIN32
FILETIME time;
GetSystemTimeAsFileTime(&time);
return GetCurrentProcessId() + time.dwHighDateTime + time.dwLowDateTime;
#else
timeval tv;
gettimeofday(&tv, 0);
return getpid() + tv.tv_sec + tv.tv_usec;
#endif
}
}
}
|