graph_generation.cc 19.8 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1
2
// graph-tool -- a general graph modification and manipulation thingy
//
Tiago Peixoto's avatar
Tiago Peixoto committed
3
// Copyright (C) 2007  Tiago de Paula Peixoto <tiago@forked.de>
Tiago Peixoto's avatar
Tiago Peixoto committed
4
5
6
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
Tiago Peixoto's avatar
Tiago Peixoto committed
7
// as published by the Free Software Foundation; either version 3
Tiago Peixoto's avatar
Tiago Peixoto committed
8
9
10
11
12
13
14
15
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
16
17
// along with this program. If not, see <http://www.gnu.org/licenses/>.

Tiago Peixoto's avatar
Tiago Peixoto committed
18
19
20
21

#include <tr1/unordered_set>
#include <boost/lambda/bind.hpp>
#include <boost/random.hpp>
22
#include <boost/python.hpp>
23
24
25
26
27
28
#include <boost/function.hpp>
#include <boost/iostreams/filtering_stream.hpp>
#include <boost/iostreams/filter/gzip.hpp>
#include <boost/iostreams/filter/bzip2.hpp>
#include <boost/iostreams/device/file.hpp>

Tiago Peixoto's avatar
Tiago Peixoto committed
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iomanip>
#include <map>

#include "graph.hh"
#include "histogram.hh"

using namespace std;
using namespace boost;
using namespace boost::lambda;
using namespace graph_tool;

typedef boost::mt19937 rng_t;

// this will sample a (j,k) pair from a pjk distribution given a ceil function
// and its inverse

template <class Distribution, class Ceil, class InvCeil>
struct sample_from_distribution
{
48
    sample_from_distribution(Distribution &dist, Ceil& ceil, InvCeil &inv_ceil,
49
                             double bound, rng_t& rng)
50
        : _dist(dist), _ceil(ceil), _inv_ceil(inv_ceil), _bound(bound),
51
          _rng(rng), _uniform_p(0.0, 1.0) {}
52

Tiago Peixoto's avatar
Tiago Peixoto committed
53
54
    pair<size_t, size_t> operator()()
    {
55
56
57
58
59
60
61
62
63
64
        // sample j,k from ceil
        size_t j,k;
        double u;
        do
        {
            tie(j,k) = _inv_ceil(_uniform_p(_rng), _uniform_p(_rng));
            u = _uniform_p(_rng);
        }
        while (u > _dist(j,k)/(_bound*_ceil(j,k)));
        return make_pair(j,k);
Tiago Peixoto's avatar
Tiago Peixoto committed
65
66
67
68
69
70
71
72
73
74
    }

    Distribution& _dist;
    Ceil& _ceil;
    InvCeil& _inv_ceil;
    double _bound;
    rng_t &_rng;
    boost::uniform_real<double> _uniform_p;
};

75
// desired vertex type, with desired j,k values and the index in the real graph
Tiago Peixoto's avatar
Tiago Peixoto committed
76

77
struct dvertex_t
Tiago Peixoto's avatar
Tiago Peixoto committed
78
{
79
80
    dvertex_t() {}
    dvertex_t(size_t in, size_t out): in_degree(in), out_degree(out) {}
81
    dvertex_t(const pair<size_t,size_t>& deg): in_degree(deg.first),
82
                                              out_degree(deg.second) {}
Tiago Peixoto's avatar
Tiago Peixoto committed
83
    size_t index, in_degree, out_degree;
84
    bool operator==(const dvertex_t& other) const {return other.index == index;}
Tiago Peixoto's avatar
Tiago Peixoto committed
85
86
};

87
inline std::size_t hash_value(const dvertex_t& v)
Tiago Peixoto's avatar
Tiago Peixoto committed
88
89
90
91
92
93
{
    size_t h = hash_value(v.in_degree);
    hash_combine(h, v.out_degree);
    return h;
}

94
inline size_t dist(const dvertex_t& a, const dvertex_t& b)
Tiago Peixoto's avatar
Tiago Peixoto committed
95
{
96
    return int(a.in_degree-b.in_degree)*int(a.in_degree-b.in_degree) +
97
        int(a.out_degree-b.out_degree)*int(a.out_degree-b.out_degree);
Tiago Peixoto's avatar
Tiago Peixoto committed
98
99
100
101
102
103
}

struct total_deg_comp
{
    bool operator()(const pair<size_t,size_t>& a, const pair<size_t,size_t>& b)
    {
104
        return a.first + a.second < b.first + b.second;
Tiago Peixoto's avatar
Tiago Peixoto committed
105
106
107
108
109
110
    }
};

// this structure will keep the existing (j,k) pairs in the graph in a matrix,
// so that the nearest (j,k) to a given target can be found easily.

111
class degree_matrix_t
Tiago Peixoto's avatar
Tiago Peixoto committed
112
{
113
114
public:
    degree_matrix_t(size_t N, size_t minj, size_t mink, size_t maxj,
115
                    size_t maxk)
Tiago Peixoto's avatar
Tiago Peixoto committed
116
    {
117
118
119
120
121
122
123
124
125
        _L = max(size_t(pow(2,ceil(log2(sqrt(N))))),size_t(2));
        _minj = minj;
        _mink = mink;
        _maxj = max(maxj,_L);
        _maxk = max(maxk,_L);
        _bins.resize(_L, vector<vector<pair<size_t,size_t> > >(_L));
        _high_bins.resize(size_t(log2(_L)));
        for(size_t i = 0; i < _high_bins.size(); ++i)
            _high_bins[i].resize(_L/(1<<(i+1)), vector<size_t>(_L/(1<<(i+1))));
Tiago Peixoto's avatar
Tiago Peixoto committed
126
    }
127

Tiago Peixoto's avatar
Tiago Peixoto committed
128
129
    void insert(const pair<size_t, size_t>& v)
    {
130
131
132
133
134
135
136
137
138
        size_t j_bin, k_bin;
        tie(j_bin, k_bin) = get_bin(v.first, v.second, 0);
        _bins[j_bin][k_bin].push_back(v);
        for (size_t i = 0; i < _high_bins.size(); ++i)
        {
            size_t hj,hk;
            tie(hj,hk) = get_bin(j_bin,k_bin, i+1);
            _high_bins[i][hj][hk]++;
        }
Tiago Peixoto's avatar
Tiago Peixoto committed
139
    }
140

Tiago Peixoto's avatar
Tiago Peixoto committed
141
142
    void erase(const pair<size_t,size_t>& v)
    {
143
144
145
146
147
148
        size_t j_bin, k_bin;
        tie(j_bin, k_bin) = get_bin(v.first, v.second, 0);
        for(size_t i = 0; i < _bins[j_bin][k_bin].size(); ++i)
        {
            if (_bins[j_bin][k_bin][i] == v)
            {
149
150
                _bins[j_bin][k_bin].erase(_bins[j_bin][k_bin].begin()+i);
                break;
151
152
            }
        }
153

154
155
156
157
158
159
        for (size_t i = 0; i < _high_bins.size(); ++i)
        {
            size_t hj,hk;
            tie(hj,hk) = get_bin(j_bin,k_bin, i+1);
            _high_bins[i][hj][hk]--;
        }
160

Tiago Peixoto's avatar
Tiago Peixoto committed
161
162
    }

163
    pair<size_t,size_t> find_closest(size_t j, size_t k, rng_t& rng)
Tiago Peixoto's avatar
Tiago Peixoto committed
164
    {
165
166
167
168
169
170
171
172
173
174
175
        vector<pair<size_t,size_t> > candidates;

        size_t level;

        // find the appropriate level on which to operate
        for (level = _high_bins.size(); level <= 0; --level)
        {
            size_t hj, hk;
            tie(hj,hk) = get_bin(j,k,level);
            if (get_bin_count(hj,hk,level) == 0)
            {
176
177
178
                if (level < _high_bins.size())
                    level++;
                break;
179
180
181
182
183
184
            }
        }

        size_t j_bin, k_bin;
        tie(j_bin, k_bin) = get_bin(j, k, level);

185
        for (size_t hj = ((j_bin>0)?j_bin-1:j_bin);
186
             hj < j_bin + 1 && hj <= get_bin(_maxj, _maxk, level).first; ++hj)
187
188
            for (size_t hk = ((k_bin>0)?k_bin-1:k_bin);
                 hk < k_bin + 1 && hk <= get_bin(_maxj, _maxk, level).second;
189
                 ++hk)
190
                search_bin(hj,hk,j,k,level,candidates);
191

192
193
        uniform_int<size_t> sample(0, candidates.size() - 1);
        return candidates[sample(rng)];
Tiago Peixoto's avatar
Tiago Peixoto committed
194
195
    }

196
197
private:
    pair<size_t,size_t> get_bin(size_t j, size_t k, size_t level)
Tiago Peixoto's avatar
Tiago Peixoto committed
198
    {
199
        if (level == 0)
200
            return make_pair(((j-_minj)*(_L-1))/_maxj,
201
                             ((k-_mink)*(_L-1))/_maxk);
202

203
204
205
206
        pair<size_t, size_t> bin = get_bin(j,k,0);
        bin.first /=  1 << level;
        bin.second /= 1 << level;
        return bin;
207
208
209
210
    }

    size_t get_bin_count(size_t bin_j, size_t bin_k, size_t level)
    {
211
212
213
214
        if (level == 0)
            return _bins[bin_j][bin_k].size();
        else
            return _high_bins[level-1][bin_j][bin_k];
Tiago Peixoto's avatar
Tiago Peixoto committed
215
    }
216

217
    void search_bin(size_t hj, size_t hk, size_t j, size_t k, size_t level,
218
                    vector<pair<size_t,size_t> >& candidates)
Tiago Peixoto's avatar
Tiago Peixoto committed
219
    {
220
221
222
223
        size_t w = 1 << level;
        for (size_t j_bin = hj*w; j_bin < (hj+1)*w; ++j_bin)
            for (size_t k_bin = hk*w; k_bin < (hk+1)*w; ++k_bin)
            {
224
225
226
227
228
229
230
231
                for (size_t i = 0; i < _bins[j_bin][k_bin].size(); ++i)
                {
                    pair<size_t, size_t>& v = _bins[j_bin][k_bin][i];
                    if (candidates.empty())
                    {
                        candidates.push_back(v);
                        continue;
                    }
232
                    if (dist(dvertex_t(v), dvertex_t(j,k)) <
233
                        dist(dvertex_t(candidates.front()),dvertex_t(j,k)))
234
235
236
237
                    {
                        candidates.clear();
                        candidates.push_back(v);
                    }
238
                    else if (dist(dvertex_t(v), dvertex_t(j,k)) ==
239
                             dist(dvertex_t(candidates.front()),dvertex_t(j,k)))
240
241
242
243
                    {
                        candidates.push_back(v);
                    }
                }
244
            }
Tiago Peixoto's avatar
Tiago Peixoto committed
245
246
247
    }

    size_t _L;
248
249
250
251
252
253
    vector<vector<vector<pair<size_t,size_t> > > > _bins;
    vector<vector<vector<size_t> > > _high_bins;
    size_t _minj;
    size_t _mink;
    size_t _maxj;
    size_t _maxk;
Tiago Peixoto's avatar
Tiago Peixoto committed
254
255
};

256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
struct python_function
{
    python_function(python::object o): _o(o) {}
    double operator()(size_t j, size_t k)
    {
        return python::extract<double>(_o(j,k));
    }
    double operator()(size_t jl, size_t kl, size_t j, size_t k)
    {
        return python::extract<double>(_o(jl,kl,j,k));
    }
    pair<size_t,size_t> operator()(double r1, double r2)
    {
        python::object retval = _o(r1,r2);
        return make_pair(size_t(max(int(python::extract<int>(retval[0])),0)),
                         size_t(max(int(python::extract<int>(retval[1])),0)));
    }
    pair<size_t,size_t> operator()(double r1, double r2, size_t j, size_t k)
    {
        python::object retval = _o(r1,r2,j,k);
        return make_pair(size_t(max(int(python::extract<int>(retval[0])),0)),
                         size_t(max(int(python::extract<int>(retval[1])),0)));
    }
    python::object _o;
};

Tiago Peixoto's avatar
Tiago Peixoto committed
282
// generates a directed graph with given pjk and degree correlation
283
284

void GraphInterface::GenerateCorrelatedConfigurationalModel
285
286
287
288
    (size_t N, python::object ppjk, python::object pceil_pjk,
     python::object pinv_ceil_pjk, double ceil_pjk_bound, python::object pcorr,
     python::object pceil_corr, python::object pinv_ceil_corr,
     double ceil_corr_bound, bool undirected_corr, size_t seed, bool verbose)
Tiago Peixoto's avatar
Tiago Peixoto committed
289
{
290
291
292
293
294
295
296
297
298
299
300
    typedef function<double (size_t j, size_t k)> pjk_t;
    typedef function<pair<size_t,size_t> (double r1, double r2)> inv_ceil_t;
    typedef function<double (size_t jl, size_t kl, size_t j, size_t k)> corr_t;
    typedef function<pair<size_t,size_t>(double r1,
                                         double r2,
                                         size_t j,
                                         size_t k)> inv_corr_t;

    pjk_t pjk = python_function(ppjk);
    pjk_t ceil_pjk = python_function(pceil_pjk);
    inv_ceil_t inv_ceil_pjk = python_function(pinv_ceil_pjk);
301
    corr_t corr = python_function(pcorr);
302
303
304
    corr_t ceil_corr = python_function(pceil_corr);
    inv_corr_t inv_ceil_corr = python_function(pinv_ceil_corr);

Tiago Peixoto's avatar
Tiago Peixoto committed
305
306
    _mg.clear();
    _properties = dynamic_properties();
307
    rng_t rng(static_cast<rng_t::result_type>(seed));
Tiago Peixoto's avatar
Tiago Peixoto committed
308
309
310

    // sample the N (j,k) pairs

311
    sample_from_distribution<pjk_t, pjk_t, inv_ceil_t>
312
313
        pjk_sample(pjk, ceil_pjk, inv_ceil_pjk, ceil_pjk_bound, rng);
    vector<dvertex_t> vertices(N);
314
    size_t sum_j=0, sum_k=0, min_j=0, min_k=0, max_j=0, max_k=0;
Tiago Peixoto's avatar
Tiago Peixoto committed
315
316
    if (verbose)
    {
317
        cout << "adding vertices: " << flush;
Tiago Peixoto's avatar
Tiago Peixoto committed
318
319
320
    }
    for(size_t i = 0; i < N; ++i)
    {
321
322
323
324
        if (verbose)
        {
            static stringstream str;
            for (size_t j = 0; j < str.str().length(); ++j)
325
                cout << "\b";
326
327
328
329
            str.str("");
            str << i+1 << " of " << N << " (" << (i+1)*100/N << "%)";
            cout << str.str() << flush;
        }
330
        dvertex_t& v = vertices[i];
331
332
333
334
335
336
337
        v.index = _vertex_index[add_vertex(_mg)];
        tie(v.in_degree, v.out_degree) = pjk_sample();
        sum_j += v.in_degree;
        sum_k += v.out_degree;
        min_j = min(v.in_degree,min_j);
        min_k = min(v.out_degree,min_k);
        max_j = max(v.in_degree,max_j);
338
        max_k = max(v.out_degree,max_k);
Tiago Peixoto's avatar
Tiago Peixoto committed
339
340
341
    }

    if (verbose)
342
        cout << "\nfixing average degrees: " << flush;
Tiago Peixoto's avatar
Tiago Peixoto committed
343
344
345
346
347

    // <j> and <k> must be the same. Resample random pairs until this holds.
    uniform_int<size_t> vertex_sample(0, N-1);
    while (sum_j != sum_k)
    {
348
        dvertex_t& v = vertices[vertex_sample(rng)];
349
350
351
352
        sum_j -= v.in_degree;
        sum_k -= v.out_degree;
        tie(v.in_degree, v.out_degree) = pjk_sample();
        sum_j += v.in_degree;
Tiago Peixoto's avatar
Tiago Peixoto committed
353
        sum_k +=  v.out_degree;
354
355
356
357
358
359
        max_j = max(v.in_degree,max_j);
        max_k = max(v.out_degree,max_k);
        if (verbose)
        {
            static stringstream str;
            for (size_t j = 0; j < str.str().length(); ++j)
360
                cout << "\b";
361
            for (size_t j = 0; j < str.str().length(); ++j)
362
                cout << " ";
363
            for (size_t j = 0; j < str.str().length(); ++j)
364
                cout << "\b";
365
366
367
368
            str.str("");
            str << min(sum_j-sum_k, sum_k-sum_j);
            cout << str.str() << flush;
        }
Tiago Peixoto's avatar
Tiago Peixoto committed
369
370
371
    }

    size_t E = sum_k;
372

373
    vector<dvertex_t> sources; // sources of edges
374
    typedef tr1::unordered_multimap<pair<size_t,size_t>, dvertex_t,
375
                                    hash<pair<size_t,size_t> > > targets_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
376
    targets_t targets; // vertices with j > 0
377
    typedef tr1::unordered_set<pair<size_t,size_t>, hash<pair<size_t,size_t> > >
378
        target_degrees_t;
Tiago Peixoto's avatar
Tiago Peixoto committed
379
    target_degrees_t target_degrees; // existing (j,k) pairs
380

Tiago Peixoto's avatar
Tiago Peixoto committed
381
382
383
384
    // fill up sources, targets and target_degrees
    sources.reserve(E);
    for(size_t i = 0; i < N; ++i)
    {
385
386
387
388
        for(size_t k = 0; k < vertices[i].out_degree; ++k)
            sources.push_back(vertices[i]);
        if (vertices[i].in_degree > 0)
        {
389
390
            targets.insert(make_pair(make_pair(vertices[i].in_degree,
                                               vertices[i].out_degree),
391
                                     vertices[i]));
392
            target_degrees.insert(make_pair(vertices[i].in_degree,
393
                                            vertices[i].out_degree));
394
        }
Tiago Peixoto's avatar
Tiago Peixoto committed
395
396
397
    }

    typedef multiset<pair<size_t,size_t>, total_deg_comp> ordered_degrees_t;
398
399
    ordered_degrees_t ordered_degrees; // (j,k) pairs ordered by (j+k), i.e,
                                       // total degree
400
401
    degree_matrix_t degree_matrix(target_degrees.size(),
                                  min_j, min_k,
402
403
404
405
                                  max_j, max_k); // (j,k) pairs layed out in a 2
                                                 // dimensional matrix
    for(typeof(target_degrees.begin()) iter = target_degrees.begin();
        iter != target_degrees.end(); ++iter)
406
407
408
409
        if (undirected_corr)
            ordered_degrees.insert(*iter);
        else
            degree_matrix.insert(*iter);
410
411

    // shuffle sources
Tiago Peixoto's avatar
Tiago Peixoto committed
412
413
    for (size_t i = 0; i < sources.size(); ++i)
    {
414
415
        uniform_int<size_t> source_sample(i, sources.size()-1);
        swap(sources[i], sources[source_sample(rng)]);
Tiago Peixoto's avatar
Tiago Peixoto committed
416
417
418
    }

    if (verbose)
419
        cout << "\nadding edges: " << flush;
Tiago Peixoto's avatar
Tiago Peixoto committed
420
421

    // connect the sources to targets
422
    uniform_real<double> sample_probability(0.0, 1.0);
Tiago Peixoto's avatar
Tiago Peixoto committed
423
424
    for (size_t i = 0; i < sources.size(); ++i)
    {
425
        dvertex_t source = sources[i], target;
426
427
        size_t j = source.in_degree;
        size_t k = source.out_degree;
428

429
        //choose the target vertex according to correlation
430

431
432
        pjk_t prob_func = lambda::bind(corr,lambda::_1,lambda::_2,j,k);
        pjk_t ceil = lambda::bind(ceil_corr,lambda::_1,lambda::_2,j,k);
433
434
        inv_ceil_t inv_ceil = lambda::bind(inv_ceil_corr,
                                           lambda::_1,lambda::_2,j,k);
435
        sample_from_distribution<pjk_t, pjk_t, inv_ceil_t>
436
            corr_sample(prob_func, ceil, inv_ceil, ceil_corr_bound, rng);
437

438
439
        size_t jl,kl;
        tie(jl,kl) = corr_sample(); // target (j,k)
440

441
442
443
        target_degrees_t::iterator iter = target_degrees.find(make_pair(jl,kl));
        if (iter != target_degrees.end())
        {
444
445
            target = targets.find(*iter)->second; // if an (jl,kl) pair exists,
                                                  // just use that
446
447
        }
        else
448
        {
449
450
451
            pair<size_t, size_t> deg;
            if (undirected_corr)
            {
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
                // select the (j,k) pair with the closest total degree (j+k)
                ordered_degrees_t::iterator upper;
                upper = ordered_degrees.upper_bound(make_pair(jl,kl));
                if (upper == ordered_degrees.end())
                {
                    --upper;
                    deg = *upper;
                }
                else if (upper == ordered_degrees.begin())
                {
                    deg = *upper;
                }
                else
                {
                    ordered_degrees_t::iterator lower = upper;
                    --lower;
468
                    if (jl + kl - (lower->first + lower->second) <
469
                        upper->first + upper->second - (jl + kl))
470
                        deg = *lower;
471
                    else if (jl + kl - (lower->first + lower->second) !=
472
                             upper->first + upper->second - (jl + kl))
473
474
475
476
477
478
479
480
481
482
483
484
                        deg = *upper;
                    else
                    {
                        // if equal, choose randomly with equal probability
                        uniform_int<size_t> sample(0, 1);
                        if (sample(rng))
                            deg = *lower;
                        else
                            deg = *upper;
                    }
                }
                target = targets.find(deg)->second;
485
486
            }
            else
487
            {
488
489
490
491
492
                // select the (j,k) which is the closest in the j,k plane.
                deg = degree_matrix.find_closest(jl, kl, rng);
                target = targets.find(deg)->second;
//                cerr << "wanted: " << jl << ", " << kl
//                     << " got: " << deg.first << ", " << deg.second << "\n";
493
494

            }
495
496
497
498
        }

        //add edge
        graph_traits<multigraph_t>::edge_descriptor e;
499
        e = add_edge(vertex(source.index, _mg),
500
                     vertex(target.index, _mg), _mg).first;
501
502
503
504
505
506
        _edge_index[e] = i;

        // if target received all the edges it should, remove it from target
        if (in_degree(vertex(target.index, _mg), _mg) == target.in_degree)
        {
            targets_t::iterator iter,end;
507
508
509
            for(tie(iter,end) =
                    targets.equal_range(make_pair(target.in_degree,
                                                  target.out_degree));
510
                iter != end; ++iter)
511
512
513
514
515
                if (iter->second == target)
                {
                    targets.erase(iter);
                    break;
                }
516

517
518
519
520
            // if there are no more targets with (jl,kl), remove pair from
            // target_degrees, etc.
            if (targets.find(make_pair(target.in_degree, target.out_degree)) ==
                targets.end())
521
            {
522
                target_degrees.erase(target_degrees.find(make_pair
523
                                                         (target.in_degree,
524
                                                          target.out_degree)));
525
526
527
                if (target_degrees.bucket_count() > 2*target_degrees.size())
                {
                    target_degrees_t temp;
528
529
                    for(target_degrees_t::iterator iter =
                            target_degrees.begin();
530
                        iter != target_degrees.end(); ++iter)
531
532
533
534
535
                        temp.insert(*iter);
                    target_degrees = temp;
                }
                if (undirected_corr)
                {
536
537
538
                    for(ordered_degrees_t::iterator iter =
                            ordered_degrees.find(make_pair(target.in_degree,
                                                           target.out_degree));
539
                        iter != ordered_degrees.end(); ++iter)
540
                        if (*iter == make_pair(target.in_degree,
541
                                               target.out_degree))
542
543
544
545
546
547
548
                        {
                            ordered_degrees.erase(iter);
                            break;
                        }
                }
                else
                {
549
                    degree_matrix.erase(make_pair(target.in_degree,
550
                                                  target.out_degree));
551
                }
552
            }
553

554
555
556
557
        }

        if (verbose)
        {
558
            static stringstream str;
559
            for (size_t j = 0; j < str.str().length(); ++j)
560
                cout << "\b";
561
            for (size_t j = 0; j < str.str().length(); ++j)
562
                cout << " ";
563
            for (size_t j = 0; j < str.str().length(); ++j)
564
                cout << "\b";
565
566
567
568
            str.str("");
            str << (i+1) << " of " << E << " (" << (i+1)*100/E << "%)";
            cout << str.str() << flush;
        }
569

Tiago Peixoto's avatar
Tiago Peixoto committed
570
    }
571

Tiago Peixoto's avatar
Tiago Peixoto committed
572
    if (verbose)
573
        cout << "\n";
Tiago Peixoto's avatar
Tiago Peixoto committed
574
}