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-2017 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

Tiago Peixoto's avatar
Tiago Peixoto committed
21
#include <tuple>
Tiago Peixoto's avatar
Tiago Peixoto committed
22
23
24
#include <boost/functional/hash.hpp>
#include <map>
#include <set>
25
26
#include <iostream>

27
#include "graph_util.hh"
28
#include "random.hh"
29
#include "hash_map_wrap.hh"
30

31
32
33
34
35
36
37
38
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
{
39
    dvertex_t(): in_degree(0), out_degree(0) {}
40
41
42
43
44
45
46
    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;}
};

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


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

81

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

Tiago Peixoto's avatar
Tiago Peixoto committed
107
108
109
110
111
112
113
114
    // 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;
115
        for(auto di = d.begin(); di != d.end(); ++di)
Tiago Peixoto's avatar
Tiago Peixoto committed
116
117
118
119
120
121
122
123
        {
            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;
124
125
126
            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
127
128

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

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

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

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

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

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

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

//
// Undirected graph generation strategy
//

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

            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);
482
483
484
485
        }

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

490
        vector<size_t> skip;
491

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

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

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

551
                deg_t t_deg = *t_iter;
552

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

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

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

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

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

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

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

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

} // graph_tool namespace

#endif // GRAPH_GENERATION_HH