graph_rewiring.cc 22.4 KB
Newer Older
Tiago Peixoto's avatar
 
Tiago Peixoto committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
// graph-tool -- a general graph modification and manipulation thingy
//
// Copyright (C) 2007  Tiago de Paula Peixoto <tiago@forked.de>
//
// 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
Tiago Peixoto's avatar
Tiago Peixoto committed
16
// along with this program. If not, see <http://www.gnu.org/licenses/>.
Tiago Peixoto's avatar
 
Tiago Peixoto committed
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#include <algorithm>
#include <tr1/unordered_set>
#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp>
#include <boost/random.hpp>
#include <boost/functional/hash.hpp>

#include "graph.hh"
#include "graph_filtering.hh"
#include "shared_map.hh"

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

typedef boost::mt19937 rng_t;

36 37
// this will get the source of an edge for directed graphs and the target for
// undirected graphs, i.e. "the source of an in-edge"
38 39 40
struct source_in
{
    template <class Graph>
Tiago Peixoto's avatar
Tiago Peixoto committed
41 42
    typename graph_traits<Graph>::vertex_descriptor
    operator()(typename graph_traits<Graph>::edge_descriptor e, const Graph& g)
43
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
44 45 46
        return get_source(e, g, typename is_convertible
                          <typename graph_traits<Graph>::directed_category,
                           directed_tag>::type());
47 48 49
    }

    template <class Graph>
Tiago Peixoto's avatar
Tiago Peixoto committed
50 51 52
    typename graph_traits<Graph>::vertex_descriptor
    get_source(typename graph_traits<Graph>::edge_descriptor e, const Graph& g,
               true_type)
53 54 55 56 57
    {
        return source(e, g);
    }

    template <class Graph>
Tiago Peixoto's avatar
Tiago Peixoto committed
58 59 60
    typename graph_traits<Graph>::vertex_descriptor
    get_source(typename graph_traits<Graph>::edge_descriptor e, const Graph& g,
               false_type)
61 62 63 64 65
    {
        return target(e, g);
    }
};

66 67
// this will get the target of an edge for directed graphs and the source for
// undirected graphs, i.e. "the target of an in-edge"
68 69 70
struct target_in
{
    template <class Graph>
Tiago Peixoto's avatar
Tiago Peixoto committed
71 72
    typename graph_traits<Graph>::vertex_descriptor
    operator()(typename graph_traits<Graph>::edge_descriptor e, const Graph& g)
73
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
74 75 76
        return get_target(e, g, typename is_convertible
                          <typename graph_traits<Graph>::directed_category,
                           directed_tag>::type());
77 78 79
    }

    template <class Graph>
Tiago Peixoto's avatar
Tiago Peixoto committed
80 81 82
    typename graph_traits<Graph>::vertex_descriptor
    get_target(typename graph_traits<Graph>::edge_descriptor e, const Graph& g,
               true_type)
83 84 85 86 87
    {
        return target(e, g);
    }

    template <class Graph>
Tiago Peixoto's avatar
Tiago Peixoto committed
88 89 90
    typename graph_traits<Graph>::vertex_descriptor
    get_target(typename graph_traits<Graph>::edge_descriptor e, const Graph& g,
               false_type)
91 92 93 94 95
    {
        return source(e, g);
    }
};

96
// returns true if vertices u and v are adjacent. This is O(k(u)).
Tiago Peixoto's avatar
 
Tiago Peixoto committed
97
template <class Graph>
Tiago Peixoto's avatar
Tiago Peixoto committed
98
bool is_adjacent(typename graph_traits<Graph>::vertex_descriptor u,
99 100
                 typename graph_traits<Graph>::vertex_descriptor v,
                 const Graph& g )
Tiago Peixoto's avatar
 
Tiago Peixoto committed
101 102 103 104 105 106 107 108 109 110
{
    typename graph_traits<Graph>::out_edge_iterator e, e_end;
    for (tie(e, e_end) = out_edges(u, g); e != e_end; ++e)
    {
        if (target(*e,g) == v)
            return true;
    }
    return false;
}

111 112 113
// this functor will swap the source of the edge e with the source of edge se
// and the target of edge e with the target of te
struct swap_edge_triad
114
{
115 116 117 118 119
    template <class Graph, class NewEdgeMap>
    static bool parallel_check(typename graph_traits<Graph>::edge_descriptor e,
                               typename graph_traits<Graph>::edge_descriptor te,
                               typename graph_traits<Graph>::edge_descriptor se,
                               NewEdgeMap edge_is_new, const Graph &g)
120
    {
121 122 123 124 125 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
        // We want to check that if we swap the source of 'e' with the source of
        // 'se', and the target of 'te' with the target of 'e', as such
        //
        //  (s)    -e--> (t)          (ns)   -e--> (nt)
        //  (ns)   -se-> (se_t)   =>  (s)    -se-> (se_t)
        //  (te_s) -te-> (nt)         (te_s) -te-> (t),
        //
        // no parallel edges are introduced. We must considered only "new
        // edges", i.e., edges which were already sampled and swapped. "Old
        // edges" will have their chance of being swapped, and then they'll be
        // checked for parallelism.

        typename graph_traits<Graph>::vertex_descriptor
            s = source(e, g),          // current source
            t = target(e, g),          // current target
            ns = source(se, g),        // new source
            nt = target(te, g),        // new target
            te_s = source_in()(te, g), // target edge source
            se_t = target(se, g);      // source edge target

        if (edge_is_new[te] && (te_s == ns) && (nt == t) )
            return true; // s is parallel to te after swap
        if (edge_is_new[te] && edge_is_new[se] && (te != se) &&
             (s == te_s) && (t == se_t))
            return true; // se is parallel to te after swap
        if (is_adjacent_in_new(ns,  nt, se, te, edge_is_new, g))
            return true; // e would clash with an existing (new) edge
        if (is_adjacent_in_new(te_s, t, se, te, edge_is_new, g))
            return true; // te would clash with an existing (new) edge
        if (is_adjacent_in_new(s, se_t, se, te, edge_is_new, g))
            return true; // se would clash with an existing (new) edge
        return false; // the coast is clear - hooray!
153 154
    }

155 156 157 158 159 160 161 162 163
    // returns true if vertices u and v are adjacent in the new graph. This is
    // O(k(u)).
    template <class Graph, class EdgeIsNew>
    static bool is_adjacent_in_new
        (typename graph_traits<Graph>::vertex_descriptor u,
         typename graph_traits<Graph>::vertex_descriptor v,
         typename graph_traits<Graph>::edge_descriptor e1,
         typename graph_traits<Graph>::edge_descriptor e2,
         EdgeIsNew edge_is_new, const Graph& g)
164
    {
165 166 167 168 169 170 171 172
        typename graph_traits<Graph>::out_edge_iterator e, e_end;
        for (tie(e, e_end) = out_edges(u, g); e != e_end; ++e)
        {
            if (target(*e,g) == v && edge_is_new[*e] &&
                (*e != e1) && (*e != e2))
                return true;
        }
        return false;
173
    }
174

175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196
    template <class Graph, class EdgeIndexMap, class EdgesType>
    void operator()(typename graph_traits<Graph>::edge_descriptor e,
                    typename graph_traits<Graph>::edge_descriptor se,
                    typename graph_traits<Graph>::edge_descriptor te,
                    EdgesType& edges, EdgeIndexMap edge_index, Graph& g)
    {
        // swap the source of the edge 'e' with the source of edge 'se' and the
        // target of edge 'e' with the target of 'te', as such:
        //
        //  (s)    -e--> (t)          (ns)   -e--> (nt)
        //  (ns)   -se-> (se_t)   =>  (s)    -se-> (se_t)
        //  (te_s) -te-> (nt)         (te_s) -te-> (t),

        // new edges which will replace the old ones
        typename graph_traits<Graph>::edge_descriptor ne, nse, nte;

        // split cases where different combinations of the three edges are
        // the same
        if(se != te)
        {
            ne = add_edge(source(se, g), target_in()(te, g), g).first;
            if(e != se)
197
            {
198 199 200 201
                nse = add_edge(source(e, g), target(se, g), g).first;
                edge_index[nse] = edge_index[se];
                remove_edge(se, g);
                edges[edge_index[nse]] = nse;
202
            }
203
            if(e != te)
204
            {
205 206 207 208
                nte = add_edge(source_in()(te, g), target(e, g), g).first;
                edge_index[nte] = edge_index[te];
                remove_edge(te, g);
                edges[edge_index[nte]] = nte;
209
            }
210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225
            edge_index[ne] = edge_index[e];
            remove_edge(e, g);
            edges[edge_index[ne]] = ne;
        }
        else
        {
            if(e != se)
            {
                // se and te are the same. swapping indexes only.
                swap(edge_index[se], edge_index[e]);
                edges[edge_index[se]] = se;
                edges[edge_index[e]] = e;
            }
        }
    }
};
226

227
// main rewire loop
228
template <template <class Graph, class EdgeIndexMap> class RewireStrategy>
Tiago Peixoto's avatar
 
Tiago Peixoto committed
229 230 231
struct graph_rewire
{
    template <class Graph, class EdgeIndexMap>
Tiago Peixoto's avatar
Tiago Peixoto committed
232 233
    void operator()(Graph& g, EdgeIndexMap edge_index, size_t seed,
                    bool self_loops, bool parallel_edges) const
Tiago Peixoto's avatar
 
Tiago Peixoto committed
234
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
235 236
        typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
        typedef typename graph_traits<Graph>::edge_descriptor edge_t;
237

Tiago Peixoto's avatar
 
Tiago Peixoto committed
238 239 240 241 242 243 244
        rng_t rng(static_cast<rng_t::result_type>(seed));

        if (!self_loops)
        {
            // check the existence of self-loops
            bool has_self_loops = false;
            int i, N = num_vertices(g);
Tiago Peixoto's avatar
Tiago Peixoto committed
245 246
            #pragma omp parallel for default(shared) private(i) \
                schedule(dynamic)
Tiago Peixoto's avatar
 
Tiago Peixoto committed
247 248
            for (i = 0; i < N; ++i)
            {
Tiago Peixoto's avatar
Tiago Peixoto committed
249
                vertex_t v = vertex(i, g);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
250 251 252
                if (v == graph_traits<Graph>::null_vertex())
                    continue;
                if (is_adjacent(v, v, g))
253
                    has_self_loops = true;
Tiago Peixoto's avatar
 
Tiago Peixoto committed
254 255
            }
            if (has_self_loops)
Tiago Peixoto's avatar
Tiago Peixoto committed
256 257 258
                throw GraphException("Self-loop detected. Can't rewire graph "
                                     "without self-loops if it already contains"
                                     " self-loops!");
Tiago Peixoto's avatar
 
Tiago Peixoto committed
259 260 261 262
        }

        if (!parallel_edges)
        {
263
            // check the existence of parallel edges
Tiago Peixoto's avatar
 
Tiago Peixoto committed
264 265
            bool has_parallel_edges = false;
            int i, N = num_vertices(g);
Tiago Peixoto's avatar
Tiago Peixoto committed
266 267
            #pragma omp parallel for default(shared) private(i) \
                schedule(dynamic)
Tiago Peixoto's avatar
 
Tiago Peixoto committed
268 269
            for (i = 0; i < N; ++i)
            {
Tiago Peixoto's avatar
Tiago Peixoto committed
270
                vertex_t v = vertex(i, g);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
271 272 273
                if (v == graph_traits<Graph>::null_vertex())
                    continue;

Tiago Peixoto's avatar
Tiago Peixoto committed
274
                tr1::unordered_set<vertex_t> targets;
Tiago Peixoto's avatar
 
Tiago Peixoto committed
275 276 277 278 279 280 281 282 283 284 285
                typename graph_traits<Graph>::out_edge_iterator e, e_end;
                for (tie(e, e_end) = out_edges(v, g); e != e_end; ++e)
                {
                    if (targets.find(target(*e, g)) != targets.end())
                        has_parallel_edges = true;
                    else
                        targets.insert(target(*e, g));
                }
            }

            if (has_parallel_edges)
Tiago Peixoto's avatar
Tiago Peixoto committed
286 287 288
                throw GraphException("Parallel edge detected. Can't rewire "
                                     "graph without parallel edges if it "
                                     "already contains parallel edges!");
Tiago Peixoto's avatar
 
Tiago Peixoto committed
289 290
        }

291
        RewireStrategy<Graph, EdgeIndexMap> rewire(g, edge_index, rng);
292

Tiago Peixoto's avatar
Tiago Peixoto committed
293
        vector<edge_t> edges(num_edges(g));
Tiago Peixoto's avatar
 
Tiago Peixoto committed
294 295 296 297
        int i, N = num_vertices(g);
        #pragma omp parallel for default(shared) private(i) schedule(dynamic)
        for (i = 0; i < N; ++i)
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
298
            vertex_t v = vertex(i, g);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
299 300 301 302 303 304 305
            if (v == graph_traits<Graph>::null_vertex())
                continue;
            typename graph_traits<Graph>::out_edge_iterator e, e_end;
            for (tie(e, e_end) = out_edges(v, g); e != e_end; ++e)
                edges[edge_index[*e]] = *e;
        }

306 307
        // for each edge simultaneously rewire its source and target
        for (i = 0; i < int(edges.size()); ++i)
Tiago Peixoto's avatar
 
Tiago Peixoto committed
308
        {
309
            typename graph_traits<Graph>::edge_descriptor e = edges[i];
310
            typename graph_traits<Graph>::edge_descriptor se, te;
311
            tie(se, te) = rewire(e, edges, self_loops, parallel_edges);
312
            swap_edge_triad()(e, se, te, edges, edge_index, g);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
313 314 315 316
        }
    }
};

317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364
// This will iterate over a random permutation of a random access sequence, by
// swapping the values of the sequence as it iterates
template <class RandomAccessIterator, class RNG>
class random_permutation_iterator
{
public:
    random_permutation_iterator(RandomAccessIterator first,
                                RandomAccessIterator last, RNG& rng )
        : _i(first), _last(last), _rng(rng)
    {
        std::iter_swap(_i, _i + _rng(_last - _i));
    }
    typename RandomAccessIterator::value_type operator*()
    {
        return *_i;
    }
    random_permutation_iterator& operator++()
    {
        ++_i;
        if(_i != _last)
            std::iter_swap(_i, _i + _rng(_last - _i));
        return *this;
    }
    bool operator==(const RandomAccessIterator& i)
    {
        return _i == i;
    }
    bool operator!=(const RandomAccessIterator& i)
    {
        return _i != i;
    }
private:
    RandomAccessIterator _i, _last;
    RNG& _rng;
};

// utility function for random_permutation_iterator
template <class RandomAccessIterator, class RNG>
inline random_permutation_iterator<RandomAccessIterator,RNG>
make_random_permutation_iterator(RandomAccessIterator first,
                                 RandomAccessIterator last, RNG& rng)
{
    return random_permutation_iterator<RandomAccessIterator,RNG>(first, last,
                                                                 rng);
}

// this will rewire the edges so that the combined (in, out) degree distribution
// will be the same, but all the rest is random
365
template <class Graph, class EdgeIndexMap>
Tiago Peixoto's avatar
 
Tiago Peixoto committed
366 367 368
class RandomRewireStrategy
{
public:
369 370
    RandomRewireStrategy (const Graph& g, EdgeIndexMap edge_index, rng_t& rng)
        : _g(g), _rng(rng), _edge_is_new(edge_index)
Tiago Peixoto's avatar
 
Tiago Peixoto committed
371 372
    {
    }
Tiago Peixoto's avatar
Tiago Peixoto committed
373 374 375
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
    typedef typename graph_traits<Graph>::edge_descriptor edge_t;

376
    template<class EdgesType>
Tiago Peixoto's avatar
Tiago Peixoto committed
377 378
    pair<edge_t,edge_t> operator()(const edge_t& e, const EdgesType& edges,
                                   bool self_loops, bool parallel_edges)
Tiago Peixoto's avatar
 
Tiago Peixoto committed
379
    {
380 381
        _edges_source = edges;
        _edges_target = edges;
382 383 384 385
        typedef random_number_generator<rng_t,size_t> random_t;
        random_t random(_rng);
        typedef random_permutation_iterator<typename edges_t::iterator,random_t>
            random_edge_iter;
386

Tiago Peixoto's avatar
Tiago Peixoto committed
387 388
        //try randomly drawn pairs of edges until one satisfies all the
        //consistency checks
389 390 391 392 393 394
        bool found = false;
        edge_t se, te;

        random_edge_iter esi(_edges_source.begin(), _edges_source.end(),
                             random);
        for (; esi != _edges_source.end() && !found; ++esi)
Tiago Peixoto's avatar
 
Tiago Peixoto committed
395
        {
396
            if(!self_loops) // reject self-loops if not allowed
397
            {
398 399 400 401 402 403 404 405 406 407
                if((source(e, _g) == target(*esi, _g)))
                    continue;
            }

            random_edge_iter eti(_edges_target.begin(), _edges_target.end(),
                                 random);

            for (; eti != _edges_target.end() && !found; ++eti)
            {
                if (!self_loops) // reject self-loops if not allowed
408
                {
409 410
                    if ((source(*esi, _g) == target_in()(*eti, _g)) ||
                        (source_in()(*eti, _g) == target(e, _g)))
411 412
                        continue;
                }
413
                if (!parallel_edges) // reject parallel edges if not allowed
414
                {
415 416
                    if (swap_edge_triad::parallel_check(e, *esi, *eti,
                                                        _edge_is_new, _g))
417 418 419 420
                        continue;
                }
                se = *esi;
                te = *eti;
421
                found = true;
422
            }
Tiago Peixoto's avatar
 
Tiago Peixoto committed
423
        }
424 425 426
        if (!found)
            throw GraphException("Couldn't find random pair of edges to swap"
                                 "... This is a bug.");
427 428
        _edge_is_new[e]=true;
        return make_pair(se, te);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
429 430 431 432 433
    }

private:
    const Graph& _g;
    rng_t& _rng;
Tiago Peixoto's avatar
Tiago Peixoto committed
434
    typedef vector<edge_t> edges_t;
435 436
    edges_t _edges_target, _edges_source;
    vector_property_map<bool, EdgeIndexMap> _edge_is_new;
Tiago Peixoto's avatar
 
Tiago Peixoto committed
437 438
};

439 440
// this will rewire the edges so that the (in,out) degree distributions and the
// (in,out)->(in,out) correlations will be the same, but all the rest is random
441
template <class Graph, class EdgeIndexMap>
Tiago Peixoto's avatar
 
Tiago Peixoto committed
442 443 444
class CorrelatedRewireStrategy
{
public:
Tiago Peixoto's avatar
Tiago Peixoto committed
445 446 447
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
    typedef typename graph_traits<Graph>::edge_descriptor edge_t;

448 449
    CorrelatedRewireStrategy (const Graph& g, EdgeIndexMap edge_index, rng_t& rng)
        : _g(g), _rng(rng), _edge_is_new(edge_index)
Tiago Peixoto's avatar
 
Tiago Peixoto committed
450 451 452
    {
        int i, N = num_vertices(_g);
        for (i = 0; i < N; ++i)
453
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
454
            vertex_t v = vertex(i, _g);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
455 456 457
            if (v == graph_traits<Graph>::null_vertex())
                continue;

458
            size_t j = in_degreeS()(v, _g);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
459 460
            size_t k = out_degree(v, _g);

461 462 463 464 465
            typedef typename is_convertible
                <typename graph_traits<Graph>::directed_category,
                 directed_tag>::type is_directed;

            if (j > 0 || !is_directed::value)
466
                _deg_target_vertices[make_pair(j,k)].push_back(v);
Tiago Peixoto's avatar
Tiago Peixoto committed
467

468
            if (k > 0)
469
                _deg_source_vertices[make_pair(j,k)].push_back(v);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
470 471 472
        }
    }

473
    template<class EdgesType>
Tiago Peixoto's avatar
Tiago Peixoto committed
474 475
    pair<edge_t, edge_t> operator()(const edge_t& e, const EdgesType& edges,
                                    bool self_loops, bool parallel_edges)
Tiago Peixoto's avatar
 
Tiago Peixoto committed
476
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
477
        vector<vertex_t>& source_vertices =
478
            _deg_source_vertices[make_pair(in_degreeS()(source(e, _g), _g),
Tiago Peixoto's avatar
Tiago Peixoto committed
479 480
                                           out_degree(source(e, _g), _g))];
        vector<vertex_t>& target_vertices =
481
            _deg_target_vertices[make_pair(in_degreeS()(target(e, _g), _g),
Tiago Peixoto's avatar
Tiago Peixoto committed
482
                                           out_degree(target(e, _g), _g))];
483

484 485 486 487 488 489 490 491
        typedef random_number_generator<rng_t, size_t> random_t;
        random_t random(_rng);
        typedef random_permutation_iterator<typename vector<vertex_t>::iterator,
                                            random_t>
            random_vertex_iter;
        typedef random_permutation_iterator<typename vector<edge_t>::iterator,
                                            random_t>
            random_edge_iter;
492

493
        edge_t se, te;
494
        //try new combinations until one satisfies all the consistency checks
495 496 497 498
        bool found = false;
        random_vertex_iter vs(source_vertices.begin(),
                              source_vertices.end(), random);
        for (; vs != source_vertices.end() && !found; ++vs)
Tiago Peixoto's avatar
 
Tiago Peixoto committed
499
        {
500 501 502
            random_vertex_iter vt(target_vertices.begin(),
                                  target_vertices.end(), random);
            for (; vt != target_vertices.end() && !found; ++vt)
Tiago Peixoto's avatar
 
Tiago Peixoto committed
503
            {
504
                // set up the edges to draw from
Tiago Peixoto's avatar
Tiago Peixoto committed
505
                vector<edge_t> in_edges_vt, out_edges_vs;
506
                typename in_or_out_edge_iteratorS<Graph>::type ie, ie_end;
507
                typename graph_traits<Graph>::out_edge_iterator oe, oe_end;
508 509 510
                tie(ie, ie_end) =
                    in_or_out_edge_iteratorS<Graph>::get_edges(*vt, _g);
                for (; ie != ie_end; ++ie)
511
                    in_edges_vt.push_back(*ie);
512
                for (tie(oe, oe_end) = out_edges(*vs, _g); oe != oe_end ; ++oe)
513 514 515
                    out_edges_vs.push_back(*oe);

                // for combinations of in_vt and out_vs...
516 517 518
                random_edge_iter out_vs_i(out_edges_vs.begin(),
                                          out_edges_vs.end(), random);
                for (; out_vs_i != out_edges_vs.end() && !found; ++out_vs_i)
519
                {
520 521

                    if(!self_loops) // reject self-loops if not allowed
522
                    {
523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539
                        if((*vs == *vt) ||
                           (source(e, _g) == target(*out_vs_i, _g)))
                            continue;
                    }

                    if(!parallel_edges) // reject parallel edges if not allowed
                    {
                        if(_edge_is_new[*out_vs_i] && (source(e, _g)==*vs) &&
                           (target(*out_vs_i, _g)==*vt))
                            continue;
                    }

                    random_edge_iter in_vt_i(in_edges_vt.begin(),
                                             in_edges_vt.end(), random);
                    for (; in_vt_i != in_edges_vt.end() && !found; ++in_vt_i)
                    {
                        if(!self_loops) // reject self-loops if not allowed
540
                        {
Tiago Peixoto's avatar
Tiago Peixoto committed
541
                            if((source_in()(*in_vt_i, _g) == target(e, _g)))
542
                                continue;
543
                        }
544 545
                        if(!parallel_edges) // reject parallel edges if not
                                            // allowed
546
                        {
547 548
                            if (swap_edge_triad::parallel_check
                                (e, *out_vs_i, *in_vt_i, _edge_is_new, _g))
549 550 551 552
                                continue;
                        }
                        se = *out_vs_i;
                        te = *in_vt_i;
553
                        found = true;
554 555
                    }
                }
Tiago Peixoto's avatar
 
Tiago Peixoto committed
556 557
            }
        }
558 559 560
        if (!found)
            throw GraphException("Couldn't find random pair of edges to swap"
                                 "... This is a bug.");
561
        _edge_is_new[e]=true;
562
        return make_pair(se, te);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
563 564 565 566 567
    }

private:
    const Graph& _g;
    rng_t& _rng;
Tiago Peixoto's avatar
Tiago Peixoto committed
568 569
    typedef tr1::unordered_map<pair<size_t, size_t>, vector<vertex_t>,
                               hash<pair<size_t, size_t> > > deg_vertices_t;
570 571
    deg_vertices_t _deg_source_vertices;
    deg_vertices_t _deg_target_vertices;
572
    vector_property_map<bool, EdgeIndexMap> _edge_is_new;
Tiago Peixoto's avatar
 
Tiago Peixoto committed
573 574
};

Tiago Peixoto's avatar
Tiago Peixoto committed
575 576
void GraphInterface::RandomRewire(string strat, bool self_loops,
                                  bool parallel_edges, size_t seed)
Tiago Peixoto's avatar
 
Tiago Peixoto committed
577 578 579 580
{
    bool reversed = GetReversed();
    SetReversed(false);

Tiago Peixoto's avatar
Tiago Peixoto committed
581 582 583 584
    if (strat == "uncorrelated")
        check_filter(*this, bind<void>(graph_rewire<RandomRewireStrategy>(),
                                       _1, _edge_index, seed, self_loops,
                                       parallel_edges),
Tiago Peixoto's avatar
 
Tiago Peixoto committed
585
                     never_reversed(), directed_check());
Tiago Peixoto's avatar
Tiago Peixoto committed
586 587 588 589
    else if (strat == "correlated")
        check_filter(*this, bind<void>(graph_rewire<CorrelatedRewireStrategy>(),
                                       _1, _edge_index, seed, self_loops,
                                       parallel_edges),
Tiago Peixoto's avatar
 
Tiago Peixoto committed
590
                     never_reversed(), directed_check());
Tiago Peixoto's avatar
Tiago Peixoto committed
591 592
    else
        throw GraphException("invalid random rewire stategy: " + strat);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
593 594
    SetReversed(reversed);
}