graph_rewiring.cc 21.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 36 37 38

#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;

struct get_in_degree
{
    template <class Graph>
Tiago Peixoto's avatar
Tiago Peixoto committed
39 40
    size_t operator()(typename graph_traits<Graph>::vertex_descriptor v,
                      const Graph& g)
Tiago Peixoto's avatar
 
Tiago Peixoto committed
41
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
42 43 44
        return get_degree(v, g, typename is_convertible
                          <typename graph_traits<Graph>::directed_category,
                           directed_tag>::type());
Tiago Peixoto's avatar
 
Tiago Peixoto committed
45 46 47
    }

    template <class Graph>
Tiago Peixoto's avatar
Tiago Peixoto committed
48 49
    size_t get_degree(typename graph_traits<Graph>::vertex_descriptor v,
                      const Graph& g, true_type)
Tiago Peixoto's avatar
 
Tiago Peixoto committed
50 51 52 53 54
    {
        return in_degree(v,g);
    }

    template <class Graph>
Tiago Peixoto's avatar
Tiago Peixoto committed
55 56
    size_t get_degree(typename graph_traits<Graph>::vertex_descriptor v,
                      const Graph& g, false_type)
Tiago Peixoto's avatar
 
Tiago Peixoto committed
57 58 59 60 61
    {
        return out_degree(v,g);
    }
};

62 63 64
struct source_in
{
    template <class Graph>
Tiago Peixoto's avatar
Tiago Peixoto committed
65 66
    typename graph_traits<Graph>::vertex_descriptor
    operator()(typename graph_traits<Graph>::edge_descriptor e, const Graph& g)
67
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
68 69 70
        return get_source(e, g, typename is_convertible
                          <typename graph_traits<Graph>::directed_category,
                           directed_tag>::type());
71 72 73
    }

    template <class Graph>
Tiago Peixoto's avatar
Tiago Peixoto committed
74 75 76
    typename graph_traits<Graph>::vertex_descriptor
    get_source(typename graph_traits<Graph>::edge_descriptor e, const Graph& g,
               true_type)
77 78 79 80 81
    {
        return source(e, g);
    }

    template <class Graph>
Tiago Peixoto's avatar
Tiago Peixoto committed
82 83 84
    typename graph_traits<Graph>::vertex_descriptor
    get_source(typename graph_traits<Graph>::edge_descriptor e, const Graph& g,
               false_type)
85 86 87 88 89 90 91 92
    {
        return target(e, g);
    }
};

struct target_in
{
    template <class Graph>
Tiago Peixoto's avatar
Tiago Peixoto committed
93 94
    typename graph_traits<Graph>::vertex_descriptor
    operator()(typename graph_traits<Graph>::edge_descriptor e, const Graph& g)
95
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
96 97 98
        return get_target(e, g, typename is_convertible
                          <typename graph_traits<Graph>::directed_category,
                           directed_tag>::type());
99 100 101
    }

    template <class Graph>
Tiago Peixoto's avatar
Tiago Peixoto committed
102 103 104
    typename graph_traits<Graph>::vertex_descriptor
    get_target(typename graph_traits<Graph>::edge_descriptor e, const Graph& g,
               true_type)
105 106 107 108 109
    {
        return target(e, g);
    }

    template <class Graph>
Tiago Peixoto's avatar
Tiago Peixoto committed
110 111 112
    typename graph_traits<Graph>::vertex_descriptor
    get_target(typename graph_traits<Graph>::edge_descriptor e, const Graph& g,
               false_type)
113 114 115 116 117
    {
        return source(e, g);
    }
};

Tiago Peixoto's avatar
 
Tiago Peixoto committed
118
template <class Graph>
Tiago Peixoto's avatar
Tiago Peixoto committed
119 120
bool is_adjacent(typename graph_traits<Graph>::vertex_descriptor u,
                 typename graph_traits<Graph>::vertex_descriptor v, Graph& g )
Tiago Peixoto's avatar
 
Tiago Peixoto committed
121 122 123 124 125 126 127 128 129 130
{
    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;
}

131
template <class Graph, class EdgeIsNew>
Tiago Peixoto's avatar
Tiago Peixoto committed
132 133 134 135 136
bool is_adjacent_in_new(typename graph_traits<Graph>::vertex_descriptor u,
                        typename graph_traits<Graph>::vertex_descriptor v,
                        Graph& g , EdgeIsNew& edge_is_new,
                        const typename graph_traits<Graph>::edge_descriptor& e1,
                        const typename graph_traits<Graph>::edge_descriptor& e2)
137 138 139 140
{
    typename graph_traits<Graph>::out_edge_iterator ei, ei_end;
    for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei)
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
141 142
        if ( (target(*ei, g) == v) && edge_is_new[*ei] &&
             (*ei != e1) && (*ei != e2) )
143 144 145 146 147
            return true;
    }
    return false;
}

148 149
template <class RandomAccessIterator, class RandomNumberGenerator>
class iterative_random_shuffle
150
{
151
public:
Tiago Peixoto's avatar
Tiago Peixoto committed
152 153 154 155
    iterative_random_shuffle( RandomAccessIterator first,
                              RandomAccessIterator last,
                              RandomNumberGenerator& rand )
        : _i(first), _last(last), _rand(rand)
156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178
    {
        std::iter_swap(_i, _i + _rand(_last - _i) );
    }
    typename RandomAccessIterator::value_type operator*()
    {
        return *_i;
    }
    iterative_random_shuffle operator++()
    {
        ++_i;
        if(_i != _last)
            std::iter_swap(_i, _i + _rand(_last - _i) );
        return *this;
    }
    bool operator==(const RandomAccessIterator& i)
    {
        return _i == i;
    }
    bool operator!=(const RandomAccessIterator& i)
    {
        return _i != i;
    }
private:
Tiago Peixoto's avatar
Tiago Peixoto committed
179 180
    RandomAccessIterator _i, _last;
    RandomNumberGenerator& _rand;
181
};
182

183
template <class Graph, class EdgeIndexMap, class EdgesType>
Tiago Peixoto's avatar
Tiago Peixoto committed
184 185 186 187
void swap_edge_triad( 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 )
188
{
189
            typename graph_traits<Graph>::edge_descriptor ne, nse, nte;
Tiago Peixoto's avatar
Tiago Peixoto committed
190 191
            // split cases where different combinations of the three edges are
            // the same
192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217
            if( se != te )
            {
                ne = add_edge(source(se, g), target_in()(te, g), g).first;
                if(e != se)
                {
                    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;
                }
                if(e != te)
                {
                    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;
                }
                edge_index[ne] = edge_index[e];
                remove_edge(e, g);
                edges[edge_index[ne]] = ne;
            }
            else
            {
                if(e != se)
                {
                    ne = se; nse = e;
Tiago Peixoto's avatar
Tiago Peixoto committed
218 219
                    tie(edge_index[ne], edge_index[nse]) =
                        make_pair(edge_index[e], edge_index[se]);
220 221 222
                    edges[edge_index[ne]] = ne; edges[edge_index[nse]] = nse;
                }
            }
223 224
}

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

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

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

Tiago Peixoto's avatar
Tiago Peixoto committed
271
                tr1::unordered_set<vertex_t> targets;
Tiago Peixoto's avatar
 
Tiago Peixoto committed
272 273 274 275 276 277 278 279 280 281 282
                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
283 284 285
                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
286 287
        }

288
        RewireStrategy<Graph, EdgeIndexMap> rewire(g, rng);
289

Tiago Peixoto's avatar
Tiago Peixoto committed
290
        vector<edge_t> edges(num_edges(g));
Tiago Peixoto's avatar
 
Tiago Peixoto committed
291 292 293 294
        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
295
            vertex_t v = vertex(i, g);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
296 297 298 299 300 301 302
            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;
        }

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

314
template <class Graph, class EdgeIndexMap>
Tiago Peixoto's avatar
 
Tiago Peixoto committed
315 316 317 318 319 320
class RandomRewireStrategy
{
public:
    RandomRewireStrategy (const Graph& g, rng_t& rng): _g(g), _rng(rng)
    {
    }
Tiago Peixoto's avatar
Tiago Peixoto committed
321 322 323
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
    typedef typename graph_traits<Graph>::edge_descriptor edge_t;

324
    template<class EdgesType>
Tiago Peixoto's avatar
Tiago Peixoto committed
325 326
    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
327
    {
328 329 330 331
        _edges_source = edges;
        _edges_target = edges;
        random_number_generator<rng_t, size_t> generator(_rng);
        bool pass=false;
Tiago Peixoto's avatar
Tiago Peixoto committed
332
        edge_t se, te;
333

Tiago Peixoto's avatar
Tiago Peixoto committed
334 335 336 337 338
        //try randomly drawn pairs of edges until one satisfies all the
        //consistency checks
        iterative_random_shuffle<typename edges_t::iterator,
                                 random_number_generator<rng_t, size_t> >
            esi(_edges_source.begin(), _edges_source.end(), generator);
339
        for(; esi != _edges_source.end() ; ++esi)
Tiago Peixoto's avatar
 
Tiago Peixoto committed
340
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
341 342 343
            iterative_random_shuffle<typename edges_t::iterator,
                                     random_number_generator<rng_t, size_t> >
                eti(_edges_target.begin(), _edges_target.end(), generator);
344 345
            for(; eti != _edges_target.end() ; ++eti)
            {
Tiago Peixoto's avatar
Tiago Peixoto committed
346
                if(!self_loops)
347
                {
Tiago Peixoto's avatar
Tiago Peixoto committed
348
                    if((source(e, _g) == target(*esi, _g)))
349
                        break;
Tiago Peixoto's avatar
Tiago Peixoto committed
350 351
                    if((source(*esi, _g) == target_in()(*eti, _g)) ||
                       (source_in()(*eti, _g) == target(e, _g)))
352 353
                        continue;
                }
Tiago Peixoto's avatar
Tiago Peixoto committed
354
                if(!parallel_edges)
355
                {
Tiago Peixoto's avatar
Tiago Peixoto committed
356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374
                    //TODO: make this readable - count0
                    if(is_adjacent_in_new(source(*esi, _g),
                                          target_in()(*eti, _g),
                                          _g, _edge_is_new, *esi, *eti) ||
                        is_adjacent_in_new(source_in()(*eti, _g),
                                           target(e, _g), _g,
                                           _edge_is_new, *esi, *eti) ||
                        is_adjacent_in_new(source(e, _g), target(*esi, _g),
                                           _g, _edge_is_new, *esi, *eti) ||
                       (_edge_is_new[*eti] &&
                        (source_in()(*eti, _g) == source(*esi, _g)) &&
                        (target( e  , _g) == target_in()(*eti, _g)) ) ||
                       (_edge_is_new[*esi] && (source( e  , _g) ==
                                               source(*esi, _g))
                        && (target(*esi, _g) == target_in()(*eti, _g)) ) ||
                       ( _edge_is_new[*eti] && _edge_is_new[*esi]  &&
                         (*eti != *esi) &&
                         (source(e, _g) == source_in()(*eti, _g)) &&
                         (target(e, _g) == target(*esi, _g)) ) )
375 376 377 378 379 380 381 382
                        continue;
                }
                se = *esi;
                te = *eti;
                pass = true;
                break;
            }
            if(pass) break;
Tiago Peixoto's avatar
 
Tiago Peixoto committed
383
        }
384
        if(pass==false)
Tiago Peixoto's avatar
Tiago Peixoto committed
385 386 387 388
            throw GraphException("Bad things happen when you're not one with"
                                 "your inner self."); // also when you don't
                                                      // comment your code
                                                      // properly :-) - count0
389 390
        _edge_is_new[e]=true;
        return make_pair(se, te);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
391 392 393 394 395
    }

private:
    const Graph& _g;
    rng_t& _rng;
Tiago Peixoto's avatar
Tiago Peixoto committed
396
    typedef vector<edge_t> edges_t;
397 398
    edges_t _edges_target, _edges_source;
    vector_property_map<bool, EdgeIndexMap> _edge_is_new;
Tiago Peixoto's avatar
 
Tiago Peixoto committed
399 400
};

401
template <class Graph, class EdgeIndexMap>
Tiago Peixoto's avatar
 
Tiago Peixoto committed
402 403 404
class CorrelatedRewireStrategy
{
public:
Tiago Peixoto's avatar
Tiago Peixoto committed
405 406 407
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
    typedef typename graph_traits<Graph>::edge_descriptor edge_t;

408
    CorrelatedRewireStrategy (const Graph& g, rng_t& rng): _g(g), _rng(rng)
Tiago Peixoto's avatar
 
Tiago Peixoto committed
409 410 411
    {
        int i, N = num_vertices(_g);
        for (i = 0; i < N; ++i)
412
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
413
            vertex_t v = vertex(i, _g);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
414 415 416 417 418 419
            if (v == graph_traits<Graph>::null_vertex())
                continue;

            size_t j = get_in_degree()(v, _g);
            size_t k = out_degree(v, _g);

420
            if (j > 0)
421
                _deg_target_vertices[make_pair(j,k)].push_back(v);
Tiago Peixoto's avatar
Tiago Peixoto committed
422

423
            if (k > 0)
424
                _deg_source_vertices[make_pair(j,k)].push_back(v);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
425 426 427
        }
    }

428
    template<class EdgesType>
Tiago Peixoto's avatar
Tiago Peixoto committed
429 430
    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
431
    {
Tiago Peixoto's avatar
Tiago Peixoto committed
432 433 434 435 436 437
        vector<vertex_t>& source_vertices =
            _deg_source_vertices[make_pair(get_in_degree()(source(e, _g), _g),
                                           out_degree(source(e, _g), _g))];
        vector<vertex_t>& target_vertices =
            _deg_target_vertices[make_pair(get_in_degree()(target(e, _g), _g),
                                           out_degree(target(e, _g), _g))];
438 439

        random_number_generator<rng_t, size_t> generator(_rng);
Tiago Peixoto's avatar
Tiago Peixoto committed
440
        edge_t se, te;
441
        bool pass=false;
442 443

        //try new combinations until one satisfies all the consistency checks
Tiago Peixoto's avatar
Tiago Peixoto committed
444 445 446 447 448
        typedef iterative_random_shuffle
            <typename vector<vertex_t>::iterator,
             random_number_generator<rng_t, size_t> > viter_random_shuffle_t;
        viter_random_shuffle_t vs(source_vertices.begin(), 
                                  source_vertices.end(), generator);
449
        for(; vs != source_vertices.end(); ++vs)
Tiago Peixoto's avatar
 
Tiago Peixoto committed
450
        {
Tiago Peixoto's avatar
Tiago Peixoto committed
451 452
            viter_random_shuffle_t vt(target_vertices.begin(),
                                     target_vertices.end(), generator);
453
            for(; vt != target_vertices.end(); ++vt)
Tiago Peixoto's avatar
 
Tiago Peixoto committed
454
            {
455
                // set up the edges to draw from
Tiago Peixoto's avatar
Tiago Peixoto committed
456 457
                vector<edge_t> in_edges_vt, out_edges_vs;
                typename in_edge_iteratorS<Graph>::type ie, ie_end;
458
                typename graph_traits<Graph>::out_edge_iterator oe, oe_end;
Tiago Peixoto's avatar
Tiago Peixoto committed
459 460 461
                for(tie(ie, ie_end) = 
                        in_edge_iteratorS<Graph>::in_edges(*vt, _g);
                     ie != ie_end ; ++ie)
462
                    in_edges_vt.push_back(*ie);
Tiago Peixoto's avatar
Tiago Peixoto committed
463
                for(tie(oe, oe_end) = out_edges(*vs, _g); oe != oe_end ; ++oe)
464 465 466
                    out_edges_vs.push_back(*oe);

                // for combinations of in_vt and out_vs...
Tiago Peixoto's avatar
Tiago Peixoto committed
467 468 469 470 471 472
                typedef iterative_random_shuffle
                    <typename vector<edge_t>::iterator,
                     random_number_generator<rng_t, size_t> >
                    eiter_random_shuffle_t;
                eiter_random_shuffle_t out_vs_i(out_edges_vs.begin(),
                                                out_edges_vs.end(), generator);
473
                for(; out_vs_i != out_edges_vs.end(); ++out_vs_i)
474
                {
Tiago Peixoto's avatar
Tiago Peixoto committed
475 476 477
                    eiter_random_shuffle_t in_vt_i(in_edges_vt.begin(),
                                                   in_edges_vt.end(),
                                                   generator);
478
                    for(; in_vt_i != in_edges_vt.end(); ++in_vt_i)
479
                    {
Tiago Peixoto's avatar
Tiago Peixoto committed
480 481
                        if(!parallel_edges)  // check all break conditions
                                             // before continue conditions
482
                        {
Tiago Peixoto's avatar
Tiago Peixoto committed
483 484 485
                            if(_edge_is_new[*out_vs_i] &&
                               (source(e, _g)==*vs) &&
                               (target(*out_vs_i, _g)==*vt))
486
                                break;
487
                        }
Tiago Peixoto's avatar
Tiago Peixoto committed
488
                        if(!self_loops)
489
                        {
Tiago Peixoto's avatar
Tiago Peixoto committed
490 491
                            if((*vs == *vt) ||
                                (source(e, _g) == target(*out_vs_i, _g)))
492
                                break;
Tiago Peixoto's avatar
Tiago Peixoto committed
493
                            if((source_in()(*in_vt_i, _g) == target(e, _g)))
494
                                continue;
495
                        }
Tiago Peixoto's avatar
Tiago Peixoto committed
496
                        if(!parallel_edges)
497
                        {
Tiago Peixoto's avatar
Tiago Peixoto committed
498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516
                            if(is_adjacent_in_new(*vs, *vt, _g, _edge_is_new,
                                                  *out_vs_i, *in_vt_i) ||
                               is_adjacent_in_new(source_in()(*in_vt_i, _g),
                                                  target( e, _g), _g,
                                                  _edge_is_new, *out_vs_i,
                                                  *in_vt_i) ||
                               is_adjacent_in_new(source(e, _g),
                                                  target(*out_vs_i, _g), _g,
                                                  _edge_is_new, *out_vs_i,
                                                  *in_vt_i) ||
                               (_edge_is_new[*in_vt_i]
                                && (source_in()(*in_vt_i, _g) == *vs) &&
                                (target(e, _g)==*vt) ) ||
                               ( _edge_is_new[*in_vt_i] &&
                                 _edge_is_new[*out_vs_i] &&
                                 (*in_vt_i != *out_vs_i) &&
                                 (source(e, _g) ==
                                  source_in()(*in_vt_i, _g)) &&
                                 (target(e, _g) == target(*out_vs_i, _g))))
517 518 519 520
                                continue;
                        }
                        se = *out_vs_i;
                        te = *in_vt_i;
521 522 523 524 525 526
                        pass = true;
                        break;
                    }
                    if(pass) break;
                }
                if(pass) break;
Tiago Peixoto's avatar
 
Tiago Peixoto committed
527
            }
528
            if(pass) break;
Tiago Peixoto's avatar
 
Tiago Peixoto committed
529
        }
530
        if(pass==false)
Tiago Peixoto's avatar
Tiago Peixoto committed
531 532
            throw GraphException("Bad things happen when you're not one with"
                                 " your inner self.");
533
        _edge_is_new[e]=true;
534
        return make_pair(se, te);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
535 536 537 538 539
    }

private:
    const Graph& _g;
    rng_t& _rng;
Tiago Peixoto's avatar
Tiago Peixoto committed
540 541
    typedef tr1::unordered_map<pair<size_t, size_t>, vector<vertex_t>,
                               hash<pair<size_t, size_t> > > deg_vertices_t;
542 543
    deg_vertices_t _deg_source_vertices;
    deg_vertices_t _deg_target_vertices;
544
    vector_property_map<bool, EdgeIndexMap> _edge_is_new;
Tiago Peixoto's avatar
 
Tiago Peixoto committed
545 546
};

Tiago Peixoto's avatar
Tiago Peixoto committed
547 548
void GraphInterface::RandomRewire(string strat, bool self_loops,
                                  bool parallel_edges, size_t seed)
Tiago Peixoto's avatar
 
Tiago Peixoto committed
549 550 551 552
{
    bool reversed = GetReversed();
    SetReversed(false);

Tiago Peixoto's avatar
Tiago Peixoto committed
553 554 555 556
    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
557
                     never_reversed(), directed_check());
Tiago Peixoto's avatar
Tiago Peixoto committed
558 559 560 561
    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
562
                     never_reversed(), directed_check());
Tiago Peixoto's avatar
Tiago Peixoto committed
563 564
    else
        throw GraphException("invalid random rewire stategy: " + strat);
Tiago Peixoto's avatar
 
Tiago Peixoto committed
565 566
    SetReversed(reversed);
}