graph_rewiring.cc 22.5 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
    template <class Graph, class NewEdgeMap>
    static bool parallel_check(typename graph_traits<Graph>::edge_descriptor e,
                               typename graph_traits<Graph>::edge_descriptor se,
118
                               typename graph_traits<Graph>::edge_descriptor te,
119
                               NewEdgeMap edge_is_new, const Graph &g)
120
    {
121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136
        // 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
137
            nt = target_in()(te, g),        // new target
138 139 140 141 142 143 144 145 146 147 148 149 150 151 152
            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 417
                    if(_edge_is_new[*esi] && (source(e, _g)==source(*esi, _g)) &&
                       (target(*esi, _g)==target_in()(*eti, _g)))
                        continue;
418 419
                    if (swap_edge_triad::parallel_check(e, *esi, *eti,
                                                        _edge_is_new, _g))
420 421 422 423
                        continue;
                }
                se = *esi;
                te = *eti;
424
                found = true;
425
            }
Tiago Peixoto's avatar
 
Tiago Peixoto committed
426
        }
427 428 429
        if (!found)
            throw GraphException("Couldn't find random pair of edges to swap"
                                 "... This is a bug.");
430 431
        _edge_is_new[e]=true;
        return make_pair(se, te);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
432 433 434 435 436
    }

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

442 443
// 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
444
template <class Graph, class EdgeIndexMap>
Tiago Peixoto's avatar
 
Tiago Peixoto committed
445 446 447
class CorrelatedRewireStrategy
{
public:
Tiago Peixoto's avatar
Tiago Peixoto committed
448 449 450
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
    typedef typename graph_traits<Graph>::edge_descriptor edge_t;

451 452
    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
453 454 455
    {
        int i, N = num_vertices(_g);
        for (i = 0; i < N; ++i)
456
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
457
            vertex_t v = vertex(i, _g);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
458 459 460
            if (v == graph_traits<Graph>::null_vertex())
                continue;

461
            size_t j = in_degreeS()(v, _g);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
462 463
            size_t k = out_degree(v, _g);

464 465 466 467 468
            typedef typename is_convertible
                <typename graph_traits<Graph>::directed_category,
                 directed_tag>::type is_directed;

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

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

476
    template<class EdgesType>
Tiago Peixoto's avatar
Tiago Peixoto committed
477 478
    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
479
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
480
        vector<vertex_t>& source_vertices =
481
            _deg_source_vertices[make_pair(in_degreeS()(source(e, _g), _g),
Tiago Peixoto's avatar
Tiago Peixoto committed
482 483
                                           out_degree(source(e, _g), _g))];
        vector<vertex_t>& target_vertices =
484
            _deg_target_vertices[make_pair(in_degreeS()(target(e, _g), _g),
Tiago Peixoto's avatar
Tiago Peixoto committed
485
                                           out_degree(target(e, _g), _g))];
486

487 488 489 490 491 492 493 494
        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;
495

496
        edge_t se, te;
497
        //try new combinations until one satisfies all the consistency checks
498 499 500 501
        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
502
        {
503 504 505
            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
506
            {
507
                // set up the edges to draw from
Tiago Peixoto's avatar
Tiago Peixoto committed
508
                vector<edge_t> in_edges_vt, out_edges_vs;
509
                typename in_or_out_edge_iteratorS<Graph>::type ie, ie_end;
510
                typename graph_traits<Graph>::out_edge_iterator oe, oe_end;
511 512 513
                tie(ie, ie_end) =
                    in_or_out_edge_iteratorS<Graph>::get_edges(*vt, _g);
                for (; ie != ie_end; ++ie)
514
                    in_edges_vt.push_back(*ie);
515
                for (tie(oe, oe_end) = out_edges(*vs, _g); oe != oe_end ; ++oe)
516 517 518
                    out_edges_vs.push_back(*oe);

                // for combinations of in_vt and out_vs...
519 520 521
                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)
522
                {
523 524

                    if(!self_loops) // reject self-loops if not allowed
525
                    {
526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542
                        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
543
                        {
Tiago Peixoto's avatar
Tiago Peixoto committed
544
                            if((source_in()(*in_vt_i, _g) == target(e, _g)))
545
                                continue;
546
                        }
547 548
                        if(!parallel_edges) // reject parallel edges if not
                                            // allowed
549
                        {
550 551
                            if (swap_edge_triad::parallel_check
                                (e, *out_vs_i, *in_vt_i, _edge_is_new, _g))
552 553 554 555
                                continue;
                        }
                        se = *out_vs_i;
                        te = *in_vt_i;
556
                        found = true;
557 558
                    }
                }
Tiago Peixoto's avatar
 
Tiago Peixoto committed
559 560
            }
        }
561 562 563
        if (!found)
            throw GraphException("Couldn't find random pair of edges to swap"
                                 "... This is a bug.");
564
        _edge_is_new[e]=true;
565
        return make_pair(se, te);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
566 567 568 569 570
    }

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

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

Tiago Peixoto's avatar
Tiago Peixoto committed
584 585 586 587
    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
588
                     never_reversed(), directed_check());
Tiago Peixoto's avatar
Tiago Peixoto committed
589 590 591 592
    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
593
                     never_reversed(), directed_check());
Tiago Peixoto's avatar
Tiago Peixoto committed
594 595
    else
        throw GraphException("invalid random rewire stategy: " + strat);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
596 597
    SetReversed(reversed);
}