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

#ifndef GRAPH_GENERATION_HH
#define GRAPH_GENERATION_HH

Tiago Peixoto's avatar
Tiago Peixoto committed
21
22
#include <map>
#include <set>
23
24
#include <iostream>

25
#include "graph_util.hh"
26
#include "random.hh"
27
#include "hash_map_wrap.hh"
28

29
30
31
32
33
34
35
36
namespace graph_tool
{
using namespace std;
using namespace boost;

// desired vertex type, with desired j,k values and the index in the real graph
struct dvertex_t
{
37
    dvertex_t(): in_degree(0), out_degree(0) {}
38
39
40
41
42
43
44
    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;}
};

45
46
47
48
49
50
size_t hash_value(const dvertex_t& v)
{
    return v.index;
}


51
52
53
// used for verbose display
void print_progress(size_t current, size_t total, stringstream& str)
{
54
55
    size_t atom = (total > 200) ? total/100 : 1;
    if ( ( (current+1) % atom == 0) || (current + 1) == total)
56
57
58
59
    {
        for (size_t j = 0; j < str.str().length(); ++j)
            cout << "\b";
        str.str("");
60
61
        str << current+1 << " of " << total << " ("
            << (current+1)*100 / total << "%)";
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
        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;
}

79

80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
//
// 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
100
            _max_deg = _no_self_loops ? _N - 1 : N;
101
102
103
104
        else
            _max_deg = numeric_limits<size_t>::max();
    }

Tiago Peixoto's avatar
Tiago Peixoto committed
105
106
107
108
109
110
111
112
    // 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;
113
        for(auto di = d.begin(); di != d.end(); ++di)
Tiago Peixoto's avatar
Tiago Peixoto committed
114
115
116
117
118
119
120
121
        {
            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;
122
123
124
            auto dj_end = di; ++dj_end;
            for(auto dj = d.begin(); dj != dj_end; ++dj)
                sum_in_deg += min(dj->first.first, j - one) * dj->second;
Tiago Peixoto's avatar
Tiago Peixoto committed
125
126

            size_t sum_rest = 0;
127
            auto dj = di;
Tiago Peixoto's avatar
Tiago Peixoto committed
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
            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;
143
        for(auto di = d.begin(); di != d.end(); ++di)
Tiago Peixoto's avatar
Tiago Peixoto committed
144
            sum_in_deg += di->first.first * di->second;
145
        for(auto di = d.begin(); di != d.end(); ++di)
Tiago Peixoto's avatar
Tiago Peixoto committed
146
147
148
149
150
151
152
        {
            if (di->first.second > sum_in_deg - di->first.first)
                return false;
        }
        return true;
    }

153
    // sample the degrees of all the vertices
Tiago Peixoto's avatar
Tiago Peixoto committed
154
155
    template <class DegSample>
    size_t SampleDegrees(vector<dvertex_t>& vertices, DegSample& deg_sample,
156
157
158
159
160
161
162
163
164
165
166
                         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
            {
167
                tie(v.in_degree, v.out_degree) = deg_sample(i);
168
169
170
171
172
            }
            while (_no_parallel &&
                   (v.in_degree > _max_deg || v.out_degree > _max_deg));
            sum_j += v.in_degree;
            sum_k += v.out_degree;
173
            if (_no_parallel || _no_self_loops)
Tiago Peixoto's avatar
Tiago Peixoto committed
174
                _deg_seq[make_pair(v.in_degree, v.out_degree)]++;
175
176
177
178
179
180
        }

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

Tiago Peixoto's avatar
Tiago Peixoto committed
184
        // Sequence must be graphical. Re-sample random pairs until this holds
Tiago Peixoto's avatar
Tiago Peixoto committed
185
        uniform_int_distribution<size_t> vertex_sample(0, _N-1);
186
        size_t count = 0;
Tiago Peixoto's avatar
Tiago Peixoto committed
187
188
189
        while(sum_j != sum_k || (_no_parallel && !is_graphical(_deg_seq)) ||
              (_no_self_loops && !_no_parallel &&
               !is_graphical_parallel(_deg_seq)))
190
        {
191
192
            size_t i = vertex_sample(rng);
            dvertex_t& v = vertices[i];
193
            if (_no_parallel || _no_self_loops)
Tiago Peixoto's avatar
Tiago Peixoto committed
194
            {
195
                auto iter = _deg_seq.find(make_pair(v.in_degree, v.out_degree));
Tiago Peixoto's avatar
Tiago Peixoto committed
196
197
198
199
200
                iter->second--;
                if (iter->second == 0)
                    _deg_seq.erase(iter);
            }

201
202
203
204
            sum_j -= v.in_degree;
            sum_k -= v.out_degree;
            do
            {
205
                tie(v.in_degree, v.out_degree) = deg_sample(i);
206
207
208
209
210
            }
            while (_no_parallel &&
                   (v.in_degree > _max_deg || v.out_degree > _max_deg));
            sum_j += v.in_degree;
            sum_k += v.out_degree;
211
            if (_no_parallel || _no_self_loops)
Tiago Peixoto's avatar
Tiago Peixoto committed
212
                _deg_seq[make_pair(v.in_degree, v.out_degree)]++;
213
            if (verbose && (count % 100 == 0 || sum_j == sum_k))
214
                print_update(min(sum_j-sum_k, sum_k-sum_j), str);
215
216
217
218
219
            count++;
        }
        return sum_k;
    }

Tiago Peixoto's avatar
Tiago Peixoto committed
220
    struct deg_cmp
221
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
222
223
224
225
226
227
228
        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;
        }
    };
229
230
231
232
233
234

private:
    size_t _N;
    bool _no_parallel;
    bool _no_self_loops;
    size_t _max_deg;
Tiago Peixoto's avatar
Tiago Peixoto committed
235
    map<deg_t, size_t, deg_cmp> _deg_seq;
236
237
238
239
240
241
242
243
244
};

//
// Undirected graph generation strategy
//

class UndirectedStrat
{
public:
Tiago Peixoto's avatar
Tiago Peixoto committed
245
    typedef size_t deg_t; // degree type
246
247
248
249
250
251
252
253
254
255

    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
256
257
258
259
260
261
262
    // 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;
263
        for(auto di = d.begin(); di != d.end(); ++di)
Tiago Peixoto's avatar
Tiago Peixoto committed
264
265
266
267
        {
            j += di->second;
            sum_deg += di->first * di->second;
            size_t sum_rest = 0;
268
            auto dj = di;
Tiago Peixoto's avatar
Tiago Peixoto committed
269
270
271
272
273
274
275
276
277
278
279
280
281
282
            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;
283
284
285
        for(auto& di : d)
            sum_deg += di.first * di.second;
        for(auto& di : d)
Tiago Peixoto's avatar
Tiago Peixoto committed
286
        {
287
            if (di.first > sum_deg - di.first)
Tiago Peixoto's avatar
Tiago Peixoto committed
288
289
290
291
292
                return false;
        }
        return true;
    }

293
    // samples the degress of all vertices
Tiago Peixoto's avatar
Tiago Peixoto committed
294
295
    template <class DegSample>
    size_t SampleDegrees(vector<dvertex_t>& vertices, DegSample& deg_sample,
296
297
298
299
                         rng_t& rng, bool verbose)
    {
        stringstream str;
        size_t sum_k=0;
Tiago Peixoto's avatar
Tiago Peixoto committed
300
        sum_k = 0;
301
302
303
304
305
306
307
        for(size_t i = 0; i < _N; ++i)
        {
            if (verbose)
                print_progress(i, _N, str);
            dvertex_t& v = vertices[i];
            do
            {
308
                v.out_degree = deg_sample(i, true);
309
310
311
            }
            while (_no_parallel && v.out_degree > _max_deg);
            sum_k += v.out_degree;
Tiago Peixoto's avatar
Tiago Peixoto committed
312
            _deg_seq[v.out_degree]++;
313
314
315
316
        }

        if (verbose)
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
317
            cout << "\nFixing degree sequence: "
318
319
320
321
                 << flush;
            str.str("");
        }

Tiago Peixoto's avatar
Tiago Peixoto committed
322
323
324
        // 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.
Tiago Peixoto's avatar
Tiago Peixoto committed
325
        uniform_int_distribution<size_t> vertex_sample(0, _N-1);
326
        size_t count = 0;
Tiago Peixoto's avatar
Tiago Peixoto committed
327
328
329
        while (sum_k % 2 != 0 || (_no_parallel && !is_graphical(_deg_seq)) ||
               (_no_self_loops && !_no_parallel &&
                !is_graphical_parallel(_deg_seq)))
330
        {
331
332
            size_t i = vertex_sample(rng);
            dvertex_t& v = vertices[i];
333
            if (_no_parallel || _no_self_loops)
Tiago Peixoto's avatar
Tiago Peixoto committed
334
            {
335
                auto iter = _deg_seq.find(v.out_degree);
Tiago Peixoto's avatar
Tiago Peixoto committed
336
337
338
339
                iter->second--;
                if(iter->second == 0)
                    _deg_seq.erase(iter);
            }
340
341
342
            sum_k -= v.out_degree;
            do
            {
343
                v.out_degree = deg_sample(i, true);
344
345
346
            }
            while (_no_parallel && (v.out_degree > _max_deg));
            sum_k +=  v.out_degree;
347
            if (_no_parallel || _no_self_loops)
Tiago Peixoto's avatar
Tiago Peixoto committed
348
                _deg_seq[v.out_degree]++;
349
350
351
352
            if (verbose && (count % 100 || sum_k % 2 == 0))
                print_update(sum_k, str);
            count++;
        }
Tiago Peixoto's avatar
Tiago Peixoto committed
353
        return sum_k/2;
354
355
356
357
358
359
360
    }

private:
    size_t _N;
    bool _no_parallel;
    bool _no_self_loops;
    size_t _max_deg;
Tiago Peixoto's avatar
Tiago Peixoto committed
361
    map<size_t, size_t, greater<size_t> > _deg_seq;
362
363
364
};

//
Tiago Peixoto's avatar
Tiago Peixoto committed
365
366
// Main Algorithm
// ==============
367
//
Tiago Peixoto's avatar
Tiago Peixoto committed
368
// generates a directed or undirected graph with given degree distribution
369

Tiago Peixoto's avatar
Tiago Peixoto committed
370
371
template <class Cmp>
struct cmp_in
372
{
Tiago Peixoto's avatar
Tiago Peixoto committed
373
374
    bool operator()(const pair<size_t,size_t>& v1,
                    const pair<size_t,size_t>& v2) const
375
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
376
377
378
        if (v1.first == v2.first)
            return cmp(v1.second, v2.second);
        return cmp(v1.first, v2.first);
379
    }
Tiago Peixoto's avatar
Tiago Peixoto committed
380
    Cmp cmp;
381
382
};

Tiago Peixoto's avatar
Tiago Peixoto committed
383
384
template <class Cmp>
struct cmp_out
385
{
Tiago Peixoto's avatar
Tiago Peixoto committed
386
387
    bool operator()(const pair<size_t,size_t>& v1,
                    const pair<size_t,size_t>& v2) const
388
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
389
390
391
        if (v1.second == v2.second)
            return cmp(v1.first, v2.first);
        return cmp(v1.second, v2.second);
392
    }
Tiago Peixoto's avatar
Tiago Peixoto committed
393
    Cmp cmp;
394
395
};

Tiago Peixoto's avatar
Tiago Peixoto committed
396
397
398
399
400
401
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));
}
402

403
404
405
406
407
408
409
410
411
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)
{
412
    if (is_directed_::apply<Graph>::type::value)
413
414
415
416
417
418
419
420
        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,
421
                Targets& targets, Sources& sources, Graph&)
422
423
424
425
426
427
428
429
430
{
    if (is_source<Graph>(deg))
        sources.insert(deg);
    if (is_target<Graph>(deg))
        targets.insert(deg);
    vset[deg].push_back(t_i);
    return true;
}

431
struct gen_graph
432
{
Tiago Peixoto's avatar
Tiago Peixoto committed
433
    template <class Graph, class DegSample>
434
    void operator()(Graph& g, size_t N, DegSample const& deg_sample, bool no_parallel,
435
                    bool no_self_loops, rng_t& rng, bool verbose, bool verify)
436
437
438
439
440
        const
    {
        typename property_map<Graph,vertex_index_t>::type vertex_index =
            get(vertex_index_t(), g);

Tiago Peixoto's avatar
Tiago Peixoto committed
441
        // figure out the necessary strategy
442
        typedef typename mpl::if_<typename is_directed_::apply<Graph>::type,
443
                                  DirectedStrat,
444
445
446
447
448
449
450
451
452
                                  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
453
454
        for(size_t i = 0; i < N; ++i)
            vertices[i].index = vertex_index[add_vertex(g)];
455

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

459
        // source and target degree lists
Tiago Peixoto's avatar
Tiago Peixoto committed
460
461
462
        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;
463
464

        // vertices with a given degree
465
466
467
        unordered_map<deg_t, vector<size_t>> vset; // can't use gt_hash_map, as
                                                   // internal pointers are
                                                   // invalidated after insert
468

469
        size_t num_e = 0;
Tiago Peixoto's avatar
Tiago Peixoto committed
470
        for (size_t i = 0; i < vertices.size();  ++i)
471
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
472
            deg_t deg = get_deg(vertices[i], g);
473
474
475
476
477
478
479

            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);
480
481
482
483
        }

        if (verbose)
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
484
            cout << endl << "adding edges: " << flush;
485
486
487
            str.str("");
        }

488
        vector<size_t> skip;
489

Tiago Peixoto's avatar
Tiago Peixoto committed
490
491
492
493
494
495
496
        // 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();
497
            auto sv_iter = vset.find(s_deg);
498
499
            if (s_deg.second == 0 || sv_iter == vset.end() ||
                sv_iter->second.empty())
500
            {
Tiago Peixoto's avatar
Tiago Peixoto committed
501
502
                sources.erase(sources.begin());
                continue;
503
504
            }

505
506
            vector<size_t>& s_list = sv_iter->second;
            size_t s_i = s_list.front();
Tiago Peixoto's avatar
Tiago Peixoto committed
507
508
            typename graph_traits<Graph>::vertex_descriptor s =
                vertex(vertices[s_i].index, g);
509

510
511
512
513
514
515
516
517
518
519
520
            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
521
522
            auto t_iter = targets.begin();
            auto v_iter = vset.find(*t_iter);
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
            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
539
            while (s_deg.second > 0)
540
            {
541
542
                // assert(!targets.empty());
                // assert(t_iter != targets.end());
543
                while (v_iter == vset.end() || v_iter->second.empty())
544
                {
545
546
                    ++t_iter;
                    v_iter = vset.find(*t_iter);
547
548
                }

549
                deg_t t_deg = *t_iter;
550

551
552
553
554
555
556
                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)
557
                {
558
559
560
                    swap(v_list.back(), v_list.front());
                    v_list.pop_back();
                    update_deg(t_i, nt_deg, vset, targets, sources, g);
561
562
                    t_iter = targets.begin();
                    v_iter = vset.find(*t_iter);
563
                    continue;
564
565
                }

566
567
568
569
570
571
                // 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
572
573
                typename graph_traits<Graph>::vertex_descriptor t =
                    vertex(vertices[t_i].index, g);
574

575
                if ((s == t) && (!graph_tool::is_directed(g) &&
576
577
                                 s_deg.second < 2))
                    continue;
578

Tiago Peixoto's avatar
Tiago Peixoto committed
579
                add_edge(s, t, g);
580
                s_deg = get_deg(vertices[s_i], g);
581

582
583
                // if parallel edges are allowed, we should update the target
                // list right away
Tiago Peixoto's avatar
Tiago Peixoto committed
584
585
                if (!no_parallel)
                {
586
587
588
589
590
591
592
                    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);
593
594
                        t_iter = targets.begin();
                        v_iter = vset.find(*t_iter);
595
596
597
598
                    }
                    skip.clear();
                    if (no_self_loops)
                        skip.push_back(s_i);
Tiago Peixoto's avatar
Tiago Peixoto committed
599
600
601
602
603
                }
                if (verbose)
                    print_progress(num_e++, E, str);
            }

604
            if (!s_list.empty() && s_list.front() == s_i)
Tiago Peixoto's avatar
Tiago Peixoto committed
605
            {
606
607
                swap(s_list.back(), s_list.front());
                s_list.pop_back();
Tiago Peixoto's avatar
Tiago Peixoto committed
608
            }
609
610
611
612
613
614

            // 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);
615
        }
616
        if (verbose)
Tiago Peixoto's avatar
Tiago Peixoto committed
617
            cout << endl;
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641

        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.");
            }
        }
642
643
644
645
646
647
    }
};

} // graph_tool namespace

#endif // GRAPH_GENERATION_HH