graph_generation.hh 20.7 KB
Newer Older
1 2
// graph-tool -- a general graph modification and manipulation thingy
//
Tiago Peixoto's avatar
Tiago Peixoto committed
3
// Copyright (C) 2007-2012 Tiago de Paula Peixoto <tiago@skewed.de>
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 3
// 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
// along with this program. If not, see <http://www.gnu.org/licenses/>.

#ifndef GRAPH_GENERATION_HH
#define GRAPH_GENERATION_HH

21 22 23 24 25 26 27 28 29
#if (GCC_VERSION >= 40400)
#   include <tr1/unordered_map>
#   include <tr1/random>
#   include <tr1/tuple>
#else
#   include <boost/tr1/unordered_map.hpp>
#   include <boost/tr1/random.hpp>
#   include <boost/tr1/tuple.hpp>
#endif
Tiago Peixoto's avatar
Tiago Peixoto committed
30 31 32
#include <boost/functional/hash.hpp>
#include <map>
#include <set>
33 34
#include <iostream>

35 36
#include "graph_util.hh"

37 38 39 40 41
namespace graph_tool
{
using namespace std;
using namespace boost;

42
typedef tr1::mt19937 rng_t;
43 44 45 46

// desired vertex type, with desired j,k values and the index in the real graph
struct dvertex_t
{
47
    dvertex_t(): in_degree(0), out_degree(0) {}
48 49 50 51 52 53 54
    dvertex_t(size_t in, size_t out): in_degree(in), out_degree(out) {}
    dvertex_t(const pair<size_t,size_t>& deg): in_degree(deg.first),
                                               out_degree(deg.second) {}
    size_t index, in_degree, out_degree;
    bool operator==(const dvertex_t& other) const {return other.index == index;}
};

55 56 57 58 59 60
size_t hash_value(const dvertex_t& v)
{
    return v.index;
}


61 62 63
// used for verbose display
void print_progress(size_t current, size_t total, stringstream& str)
{
64 65
    size_t atom = (total > 200) ? total/100 : 1;
    if ( ( (current+1) % atom == 0) || (current + 1) == total)
66 67 68 69
    {
        for (size_t j = 0; j < str.str().length(); ++j)
            cout << "\b";
        str.str("");
70 71
        str << current+1 << " of " << total << " ("
            << (current+1)*100 / total << "%)";
72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
        cout << str.str() << flush;
    }
}

void print_update(size_t current, stringstream& str)
{
    for (size_t j = 0; j < str.str().length(); ++j)
        cout << "\b";
    for (size_t j = 0; j < str.str().length(); ++j)
        cout << " ";
    for (size_t j = 0; j < str.str().length(); ++j)
        cout << "\b";
    str.str("");
    str << current;
    cout << str.str() << flush;
}

89 90 91 92 93 94 95 96 97 98 99 100
template <class Graph>
bool is_adjacent(typename graph_traits<Graph>::vertex_descriptor u,
                 typename graph_traits<Graph>::vertex_descriptor v,
                 const Graph& g)
{
    typename graph_traits<Graph>::adjacency_iterator a, a_end;
    for (tie(a, a_end) = adjacent_vertices(u, g); a != a_end; ++a)
        if (*a == v)
            return true;
    return false;
}

101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120
//
// Generation strategies
// =====================
//
// Directed and undirected graphs have different generation strategies, which
// are defined in the classes below.

//
// Directed graph generation strategy
//

class DirectedStrat
{
public:
    typedef pair<size_t, size_t> deg_t; // degree type

    DirectedStrat(size_t N, bool no_parallel, bool no_self_loops)
        : _N(N), _no_parallel(no_parallel), _no_self_loops(no_self_loops)
    {
        if (_no_parallel)
Tiago Peixoto's avatar
Tiago Peixoto committed
121
            _max_deg = _no_self_loops ? _N - 1 : N;
122 123 124 125
        else
            _max_deg = numeric_limits<size_t>::max();
    }

Tiago Peixoto's avatar
Tiago Peixoto committed
126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173
    // check whether a degree sequence is graphical
    template <class DegSequence>
    bool is_graphical(DegSequence& d)
    {
        size_t one = _no_self_loops ? 1 : 0;

        size_t sum_out_deg = 0;
        size_t j = 0;
        for(typeof(d.begin()) di = d.begin(); di != d.end(); ++di)
        {
            size_t out_deg = di->first.second;
            size_t count = di->second;

            j += count;
            sum_out_deg += out_deg * count;

            size_t sum_in_deg = 0;
            typeof(d.begin()) dj_end = di; ++dj_end;
            for(typeof(d.begin()) dj = d.begin(); dj != dj_end; ++dj)
                sum_in_deg += min(dj->first.first, j - one)*dj->second;

            size_t sum_rest = 0;
            typeof(d.begin()) dj = di;
            for(++dj; dj != d.end(); ++dj)
                sum_rest += min(dj->first.first, j)*dj->second;

            if (sum_out_deg > sum_in_deg + sum_rest)
                return false;
        }
        return true;
    }

    // check whether a degree sequence is graphical, when parallel loops are
    // allowed but self-loops are not
    template <class DegSequence>
    bool is_graphical_parallel(DegSequence& d)
    {
        size_t sum_in_deg = 0;
        for(typeof(d.begin()) di = d.begin(); di != d.end(); ++di)
            sum_in_deg += di->first.first * di->second;
        for(typeof(d.begin()) di = d.begin(); di != d.end(); ++di)
        {
            if (di->first.second > sum_in_deg - di->first.first)
                return false;
        }
        return true;
    }

174
    // sample the degrees of all the vertices
Tiago Peixoto's avatar
Tiago Peixoto committed
175 176
    template <class DegSample>
    size_t SampleDegrees(vector<dvertex_t>& vertices, DegSample& deg_sample,
177 178 179 180 181 182 183 184 185 186 187
                         rng_t& rng, bool verbose)
    {
        stringstream str;
        size_t sum_j=0, sum_k=0;
        for(size_t i = 0; i < _N; ++i)
        {
            if (verbose)
                print_progress(i, _N, str);
            dvertex_t& v = vertices[i];
            do
            {
188
                tie(v.in_degree, v.out_degree) = deg_sample(i);
189 190 191 192 193
            }
            while (_no_parallel &&
                   (v.in_degree > _max_deg || v.out_degree > _max_deg));
            sum_j += v.in_degree;
            sum_k += v.out_degree;
194
            if (_no_parallel || _no_self_loops)
Tiago Peixoto's avatar
Tiago Peixoto committed
195
                _deg_seq[make_pair(v.in_degree, v.out_degree)]++;
196 197 198 199 200 201
        }

        if (verbose)
        {
            cout << "\nfixing average degrees. Total degree difference: "
                 << flush;
Tiago Peixoto's avatar
Tiago Peixoto committed
202
                str.str("");
203 204
        }

Tiago Peixoto's avatar
Tiago Peixoto committed
205
        // Sequence must be graphical. Re-sample random pairs until this holds
206
        tr1::uniform_int<size_t> vertex_sample(0, _N-1);
207
        size_t count = 0;
Tiago Peixoto's avatar
Tiago Peixoto committed
208 209 210
        while(sum_j != sum_k || (_no_parallel && !is_graphical(_deg_seq)) ||
              (_no_self_loops && !_no_parallel &&
               !is_graphical_parallel(_deg_seq)))
211
        {
212 213
            size_t i = vertex_sample(rng);
            dvertex_t& v = vertices[i];
214
            if (_no_parallel || _no_self_loops)
Tiago Peixoto's avatar
Tiago Peixoto committed
215 216 217 218 219 220 221 222
            {
                typeof(_deg_seq.begin()) iter =
                    _deg_seq.find(make_pair(v.in_degree, v.out_degree));
                iter->second--;
                if (iter->second == 0)
                    _deg_seq.erase(iter);
            }

223 224 225 226
            sum_j -= v.in_degree;
            sum_k -= v.out_degree;
            do
            {
227
                tie(v.in_degree, v.out_degree) = deg_sample(i);
228 229 230 231 232
            }
            while (_no_parallel &&
                   (v.in_degree > _max_deg || v.out_degree > _max_deg));
            sum_j += v.in_degree;
            sum_k += v.out_degree;
233
            if (_no_parallel || _no_self_loops)
Tiago Peixoto's avatar
Tiago Peixoto committed
234
                _deg_seq[make_pair(v.in_degree, v.out_degree)]++;
235
            if (verbose && (count % 100 == 0 || sum_j == sum_k))
236
                print_update(min(sum_j-sum_k, sum_k-sum_j), str);
237 238 239 240 241
            count++;
        }
        return sum_k;
    }

Tiago Peixoto's avatar
Tiago Peixoto committed
242
    struct deg_cmp
243
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
244 245 246 247 248 249 250
        bool operator()(const deg_t& d1, const deg_t& d2) const
        {
            if (d1.second == d2.second)
                return d1.first > d2.first;
            return d1.second > d2.second;
        }
    };
251 252 253 254 255 256

private:
    size_t _N;
    bool _no_parallel;
    bool _no_self_loops;
    size_t _max_deg;
Tiago Peixoto's avatar
Tiago Peixoto committed
257
    map<deg_t, size_t, deg_cmp> _deg_seq;
258 259 260 261 262 263 264 265 266
};

//
// Undirected graph generation strategy
//

class UndirectedStrat
{
public:
Tiago Peixoto's avatar
Tiago Peixoto committed
267
    typedef size_t deg_t; // degree type
268 269 270 271 272 273 274 275 276 277

    UndirectedStrat(size_t N, bool no_parallel, bool no_self_loops)
        : _N(N), _no_parallel(no_parallel), _no_self_loops(no_self_loops)
    {
        if (_no_parallel)
            _max_deg = (_no_self_loops) ? _N - 1 : N;
        else
            _max_deg = numeric_limits<size_t>::max();
    }

Tiago Peixoto's avatar
Tiago Peixoto committed
278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314
    // check whether a degree sequence is graphical
    template <class DegSequence>
    bool is_graphical(DegSequence& d)
    {
        size_t one = (_no_self_loops) ? 1 : 0;
        size_t sum_deg = 0;
        size_t j = 0;
        for(typeof(d.begin()) di = d.begin(); di != d.end(); ++di)
        {
            j += di->second;
            sum_deg += di->first * di->second;
            size_t sum_rest = 0;
            typeof(d.begin()) dj = di;
            for(++dj; dj != d.end(); ++dj)
                sum_rest += min(dj->first, j)*dj->second;
            if (sum_deg > j*(j-one) + sum_rest)
                return false;
        }
        return true;
    }

    // check whether a degree sequence is graphical, when parallel loops are
    // allowed but self-loops are not
    template <class DegSequence>
    bool is_graphical_parallel(DegSequence& d)
    {
        size_t sum_deg = 0;
        for(typeof(d.begin()) di = d.begin(); di != d.end(); ++di)
            sum_deg += di->first * di->second;
        for(typeof(d.begin()) di = d.begin(); di != d.end(); ++di)
        {
            if (di->first > sum_deg - di->first)
                return false;
        }
        return true;
    }

315
    // samples the degress of all vertices
Tiago Peixoto's avatar
Tiago Peixoto committed
316 317
    template <class DegSample>
    size_t SampleDegrees(vector<dvertex_t>& vertices, DegSample& deg_sample,
318 319 320 321
                         rng_t& rng, bool verbose)
    {
        stringstream str;
        size_t sum_k=0;
Tiago Peixoto's avatar
Tiago Peixoto committed
322
        sum_k = 0;
323 324 325 326 327 328 329
        for(size_t i = 0; i < _N; ++i)
        {
            if (verbose)
                print_progress(i, _N, str);
            dvertex_t& v = vertices[i];
            do
            {
330
                v.out_degree = deg_sample(i, true);
331 332 333
            }
            while (_no_parallel && v.out_degree > _max_deg);
            sum_k += v.out_degree;
Tiago Peixoto's avatar
Tiago Peixoto committed
334
            _deg_seq[v.out_degree]++;
335 336 337 338
        }

        if (verbose)
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
339
            cout << "\nFixing degree sequence: "
340 341 342 343
                 << flush;
            str.str("");
        }

Tiago Peixoto's avatar
Tiago Peixoto committed
344 345 346
        // sum_k must be an even number (2*num_edges), and degree sequence must
        // be graphical, if multiple edges are not allowed. Re-sample degrees
        // until this holds.
347
        tr1::uniform_int<size_t> vertex_sample(0, _N-1);
348
        size_t count = 0;
Tiago Peixoto's avatar
Tiago Peixoto committed
349 350 351
        while (sum_k % 2 != 0 || (_no_parallel && !is_graphical(_deg_seq)) ||
               (_no_self_loops && !_no_parallel &&
                !is_graphical_parallel(_deg_seq)))
352
        {
353 354
            size_t i = vertex_sample(rng);
            dvertex_t& v = vertices[i];
355
            if (_no_parallel || _no_self_loops)
Tiago Peixoto's avatar
Tiago Peixoto committed
356 357 358 359 360 361
            {
                typeof(_deg_seq.begin()) iter = _deg_seq.find(v.out_degree);
                iter->second--;
                if(iter->second == 0)
                    _deg_seq.erase(iter);
            }
362 363 364
            sum_k -= v.out_degree;
            do
            {
365
                v.out_degree = deg_sample(i, true);
366 367 368
            }
            while (_no_parallel && (v.out_degree > _max_deg));
            sum_k +=  v.out_degree;
369
            if (_no_parallel || _no_self_loops)
Tiago Peixoto's avatar
Tiago Peixoto committed
370
                _deg_seq[v.out_degree]++;
371 372 373 374
            if (verbose && (count % 100 || sum_k % 2 == 0))
                print_update(sum_k, str);
            count++;
        }
Tiago Peixoto's avatar
Tiago Peixoto committed
375
        return sum_k/2;
376 377 378 379 380 381 382
    }

private:
    size_t _N;
    bool _no_parallel;
    bool _no_self_loops;
    size_t _max_deg;
Tiago Peixoto's avatar
Tiago Peixoto committed
383
    map<size_t, size_t, greater<size_t> > _deg_seq;
384 385 386
};

//
Tiago Peixoto's avatar
Tiago Peixoto committed
387 388
// Main Algorithm
// ==============
389
//
Tiago Peixoto's avatar
Tiago Peixoto committed
390
// generates a directed or undirected graph with given degree distribution
391

Tiago Peixoto's avatar
Tiago Peixoto committed
392 393
template <class Cmp>
struct cmp_in
394
{
Tiago Peixoto's avatar
Tiago Peixoto committed
395 396
    bool operator()(const pair<size_t,size_t>& v1,
                    const pair<size_t,size_t>& v2) const
397
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
398 399 400
        if (v1.first == v2.first)
            return cmp(v1.second, v2.second);
        return cmp(v1.first, v2.first);
401
    }
Tiago Peixoto's avatar
Tiago Peixoto committed
402
    Cmp cmp;
403 404
};

Tiago Peixoto's avatar
Tiago Peixoto committed
405 406
template <class Cmp>
struct cmp_out
407
{
Tiago Peixoto's avatar
Tiago Peixoto committed
408 409
    bool operator()(const pair<size_t,size_t>& v1,
                    const pair<size_t,size_t>& v2) const
410
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
411 412 413
        if (v1.second == v2.second)
            return cmp(v1.first, v2.first);
        return cmp(v1.second, v2.second);
414
    }
Tiago Peixoto's avatar
Tiago Peixoto committed
415
    Cmp cmp;
416 417
};

Tiago Peixoto's avatar
Tiago Peixoto committed
418 419 420 421 422 423
template <class Graph>
pair<size_t, size_t> get_deg(dvertex_t& v, Graph& g)
{
    return make_pair(v.in_degree - in_degreeS()(vertex(v.index, g), g),
                     v.out_degree - out_degree(vertex(v.index, g), g));
}
424

425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452
template <class Graph>
bool is_source(const pair<size_t, size_t>& deg)
{
    return deg.second > 0;
}

template <class Graph>
bool is_target(const pair<size_t, size_t>& deg)
{
    if (is_directed::apply<Graph>::type::value)
        return deg.first > 0;
    else
        return is_source<Graph>(deg);
}


template <class Vset, class Targets, class Sources, class Graph>
bool update_deg(size_t t_i, const pair<size_t, size_t>& deg, Vset& vset,
                Targets& targets, Sources& sources, Graph& g)
{
    if (is_source<Graph>(deg))
        sources.insert(deg);
    if (is_target<Graph>(deg))
        targets.insert(deg);
    vset[deg].push_back(t_i);
    return true;
}

453
struct gen_graph
454
{
Tiago Peixoto's avatar
Tiago Peixoto committed
455 456
    template <class Graph, class DegSample>
    void operator()(Graph& g, size_t N, DegSample& deg_sample, bool no_parallel,
457
                    bool no_self_loops, size_t seed, bool verbose, bool verify)
458 459
        const
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
460
        rng_t rng(static_cast<rng_t::result_type>(seed));
461 462 463
        typename property_map<Graph,vertex_index_t>::type vertex_index =
            get(vertex_index_t(), g);

Tiago Peixoto's avatar
Tiago Peixoto committed
464
        // figure out the necessary strategy
465 466
        typedef typename mpl::if_<typename is_directed::apply<Graph>::type,
                                  DirectedStrat,
467 468 469 470 471 472 473 474 475
                                  UndirectedStrat>::type gen_strat_t;

        gen_strat_t gen_strat(N, no_parallel, no_self_loops);
        stringstream str; // used for verbose status

        if (verbose)
            cout << "adding vertices: " << flush;

        vector<dvertex_t> vertices(N);
Tiago Peixoto's avatar
Tiago Peixoto committed
476 477
        for(size_t i = 0; i < N; ++i)
            vertices[i].index = vertex_index[add_vertex(g)];
478

Tiago Peixoto's avatar
Tiago Peixoto committed
479 480
        // sample the N (j,k) pairs
        size_t E = gen_strat.SampleDegrees(vertices, deg_sample, rng, verbose);
481

482
        // source and target degree lists
Tiago Peixoto's avatar
Tiago Peixoto committed
483 484 485
        typedef pair<size_t, size_t> deg_t;
        set<deg_t, cmp_out<greater<size_t> > > sources;
        set<deg_t, cmp_in<greater<size_t> > > targets;
486 487 488

        // vertices with a given degree
        tr1::unordered_map<deg_t, vector<size_t>,
489
                           hash<deg_t> > vset;
490

491
        size_t num_e = 0;
Tiago Peixoto's avatar
Tiago Peixoto committed
492
        for (size_t i = 0; i < vertices.size();  ++i)
493
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
494
            deg_t deg = get_deg(vertices[i], g);
495 496 497 498 499 500 501

            if (is_source<Graph>(deg))
                sources.insert(deg);
            if (is_target<Graph>(deg))
                targets.insert(deg);
            if (is_target<Graph>(deg) || is_source<Graph>(deg))
                vset[deg].push_back(i);
502 503 504 505
        }

        if (verbose)
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
506
            cout << endl << "adding edges: " << flush;
507 508 509
            str.str("");
        }

510
        vector<size_t> skip;
511

Tiago Peixoto's avatar
Tiago Peixoto committed
512 513 514 515 516 517 518
        // connect edges: from sources with the largest in-degree to the ones
        // with largest out-degree
        while (!sources.empty())
        {
            // find source. The out-degree must be non-zero, and there must be a
            // vertex with the chosen degree.
            deg_t s_deg = *sources.begin();
519 520 521
            typeof(vset.begin()) sv_iter = vset.find(s_deg);
            if (s_deg.second == 0 || sv_iter == vset.end() ||
                sv_iter->second.empty())
522
            {
Tiago Peixoto's avatar
Tiago Peixoto committed
523 524
                sources.erase(sources.begin());
                continue;
525 526
            }

527 528
            vector<size_t>& s_list = sv_iter->second;
            size_t s_i = s_list.front();
Tiago Peixoto's avatar
Tiago Peixoto committed
529 530
            typename graph_traits<Graph>::vertex_descriptor s =
                vertex(vertices[s_i].index, g);
531

532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560
            deg_t ns_deg = get_deg(vertices[s_i], g);
            if (ns_deg != s_deg)
            {
                swap(s_list.back(), s_list.front());
                s_list.pop_back();
                update_deg(s_i, ns_deg, vset, targets, sources, g);
                continue;
            }

            // find the targets.
            // we will keep an iterator to the current target degree
            typeof(targets.begin()) t_iter = targets.begin();
            typeof(vset.begin()) v_iter = vset.find(*t_iter);
            while (v_iter == vset.end() || v_iter->second.empty())
            {
                targets.erase(t_iter);
                t_iter = targets.begin();
                v_iter = vset.find(*t_iter);
            }

            skip.clear();
            skip.push_back(s_i);

            if (no_self_loops)
            {
                swap(s_list.back(), s_list.front());
                s_list.pop_back();
            }

Tiago Peixoto's avatar
Tiago Peixoto committed
561
            while (s_deg.second > 0)
562
            {
563 564 565 566
                //assert(!targets.empty());
                //assert(t_iter != targets.end());

                while (v_iter == vset.end() || v_iter->second.empty())
567
                {
568 569
                    ++t_iter;
                    v_iter = vset.find(*t_iter);
570 571
                }

572
                deg_t t_deg = *t_iter;
573

574 575 576 577 578 579
                vector<size_t>& v_list = v_iter->second;

                size_t t_i = v_list.front();

                deg_t nt_deg = get_deg(vertices[t_i], g);
                if (nt_deg != t_deg)
580
                {
581 582 583 584 585 586
                    swap(v_list.back(), v_list.front());
                    v_list.pop_back();
                    update_deg(t_i, nt_deg, vset, targets, sources, g);
                    //t_iter = targets.begin();
                    //v_iter = vset.find(*t_iter);
                    continue;
587 588
                }

589 590 591 592 593 594
                // remove target from vertex list, and get new t_i
                skip.push_back(t_i);

                swap(v_list.back(), v_list.front());
                v_list.pop_back();

Tiago Peixoto's avatar
Tiago Peixoto committed
595 596
                typename graph_traits<Graph>::vertex_descriptor t =
                    vertex(vertices[t_i].index, g);
597

598 599 600
                if ((s == t) && (!is_directed::apply<Graph>::type::value &&
                                 s_deg.second < 2))
                    continue;
601

Tiago Peixoto's avatar
Tiago Peixoto committed
602
                add_edge(s, t, g);
603
                s_deg = get_deg(vertices[s_i], g);
604

605 606
                // if parallel edges are allowed, we should update the target
                // list right away
Tiago Peixoto's avatar
Tiago Peixoto committed
607 608
                if (!no_parallel)
                {
609 610 611 612 613 614 615 616 617 618 619
                    for (size_t i = 0; i < skip.size(); ++i)
                    {
                        if (no_self_loops && skip[i] == s_i)
                            continue;
                        update_deg(skip[i],
                                   get_deg(vertices[skip[i]], g), vset,
                                   targets, sources, g);
                    }
                    skip.clear();
                    if (no_self_loops)
                        skip.push_back(s_i);
Tiago Peixoto's avatar
Tiago Peixoto committed
620 621 622 623 624
                }
                if (verbose)
                    print_progress(num_e++, E, str);
            }

625
            if (!s_list.empty() && s_list.front() == s_i)
Tiago Peixoto's avatar
Tiago Peixoto committed
626
            {
627 628
                swap(s_list.back(), s_list.front());
                s_list.pop_back();
Tiago Peixoto's avatar
Tiago Peixoto committed
629
            }
630 631 632 633 634 635 636

            // update modified degrees
            for (size_t i = 0; i < skip.size(); ++i)
                update_deg(skip[i],
                           get_deg(vertices[skip[i]], g),
                           vset, targets, sources, g);
       }
637
        if (verbose)
Tiago Peixoto's avatar
Tiago Peixoto committed
638
            cout << endl;
639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662

        if (verify)
        {
            for (size_t i = 0; i < vertices.size(); ++i)
            {
                deg_t dseq = make_pair(vertices[i].in_degree,
                                       vertices[i].out_degree);
                deg_t deg = make_pair(in_degreeS()(vertex(i, g), g),
                                      out_degree(vertex(i, g), g));
                if (deg != dseq)
                    throw GraphException("Graph does not match the desired "
                                         "sequence! Vertex " +
                                         lexical_cast<string>(i) +
                                         ", wanted: " +
                                         lexical_cast<string>(dseq.first) +
                                         " " +
                                         lexical_cast<string>(dseq.second) +
                                         ", got: " +
                                         lexical_cast<string>(deg.first) +
                                         " " +
                                         lexical_cast<string>(deg.second) +
                                         " This is a bug.");
            }
        }
663 664 665 666 667 668
    }
};

} // graph_tool namespace

#endif // GRAPH_GENERATION_HH