graph_rewiring.cc 22.2 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
            te_s = source_in()(te, g), // target edge source
            se_t = target(se, g);      // source edge target

141 142 143

        if (edge_is_new[se] && (ns == s) && (nt == se_t))
            return true; // e is parallel to se after swap
144
        if (edge_is_new[te] && (te_s == ns) && (nt == t) )
145
            return true; // e is parallel to te after swap
146 147 148 149 150 151 152 153 154 155
        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!
156 157
    }

158 159 160 161 162 163 164 165 166
    // 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)
167
    {
168 169 170 171 172 173 174 175
        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;
176
    }
177

178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199
    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)
200
            {
201 202 203 204
                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;
205
            }
206
            if(e != te)
207
            {
208 209 210 211
                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;
212
            }
213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228
            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;
            }
        }
    }
};
229

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

Tiago Peixoto's avatar
 
Tiago Peixoto committed
241 242 243 244 245 246 247
        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
248 249
            #pragma omp parallel for default(shared) private(i) \
                schedule(dynamic)
Tiago Peixoto's avatar
 
Tiago Peixoto committed
250 251
            for (i = 0; i < N; ++i)
            {
Tiago Peixoto's avatar
Tiago Peixoto committed
252
                vertex_t v = vertex(i, g);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
253 254 255
                if (v == graph_traits<Graph>::null_vertex())
                    continue;
                if (is_adjacent(v, v, g))
256
                    has_self_loops = true;
Tiago Peixoto's avatar
 
Tiago Peixoto committed
257 258
            }
            if (has_self_loops)
Tiago Peixoto's avatar
Tiago Peixoto committed
259 260 261
                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
262 263 264 265
        }

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

Tiago Peixoto's avatar
Tiago Peixoto committed
277
                tr1::unordered_set<vertex_t> targets;
Tiago Peixoto's avatar
 
Tiago Peixoto committed
278 279 280 281 282 283 284 285 286 287 288
                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
289 290 291
                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
292 293
        }

294
        RewireStrategy<Graph, EdgeIndexMap> rewire(g, edge_index, rng);
295

Tiago Peixoto's avatar
Tiago Peixoto committed
296
        vector<edge_t> edges(num_edges(g));
Tiago Peixoto's avatar
 
Tiago Peixoto committed
297 298 299 300
        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
301
            vertex_t v = vertex(i, g);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
302 303 304 305 306 307 308
            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;
        }

309 310
        // for each edge simultaneously rewire its source and target
        for (i = 0; i < int(edges.size()); ++i)
Tiago Peixoto's avatar
 
Tiago Peixoto committed
311
        {
312
            typename graph_traits<Graph>::edge_descriptor e = edges[i];
313
            typename graph_traits<Graph>::edge_descriptor se, te;
314
            tie(se, te) = rewire(e, edges, self_loops, parallel_edges);
315
            swap_edge_triad()(e, se, te, edges, edge_index, g);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
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 365 366 367
// 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
368
template <class Graph, class EdgeIndexMap>
Tiago Peixoto's avatar
 
Tiago Peixoto committed
369 370 371
class RandomRewireStrategy
{
public:
372 373
    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
374 375
    {
    }
Tiago Peixoto's avatar
Tiago Peixoto committed
376 377 378
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
    typedef typename graph_traits<Graph>::edge_descriptor edge_t;

379
    template<class EdgesType>
Tiago Peixoto's avatar
Tiago Peixoto committed
380 381
    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
382
    {
383 384
        _edges_source = edges;
        _edges_target = edges;
385 386 387 388
        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;
389

Tiago Peixoto's avatar
Tiago Peixoto committed
390 391
        //try randomly drawn pairs of edges until one satisfies all the
        //consistency checks
392 393 394 395 396 397
        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
398
        {
399
            if(!self_loops) // reject self-loops if not allowed
400
            {
401 402 403 404 405 406 407 408 409 410
                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
411
                {
412 413
                    if ((source(*esi, _g) == target_in()(*eti, _g)) ||
                        (source_in()(*eti, _g) == target(e, _g)))
414 415
                        continue;
                }
416
                if (!parallel_edges) // reject parallel edges if not allowed
417
                {
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)
453
        : _g(g), _rng(rng), _edge_is_new(edge_index)
Tiago Peixoto's avatar
 
Tiago Peixoto committed
454 455 456
    {
        int i, N = num_vertices(_g);
        for (i = 0; i < N; ++i)
457
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
458
            vertex_t v = vertex(i, _g);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
459 460 461
            if (v == graph_traits<Graph>::null_vertex())
                continue;

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

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

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

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

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

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

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

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

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

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

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

Tiago Peixoto's avatar
Tiago Peixoto committed
578 579 580 581
    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
582
                     never_reversed(), directed_check());
Tiago Peixoto's avatar
Tiago Peixoto committed
583 584 585 586
    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
587
                     never_reversed(), directed_check());
Tiago Peixoto's avatar
Tiago Peixoto committed
588 589
    else
        throw GraphException("invalid random rewire stategy: " + strat);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
590 591
    SetReversed(reversed);
}