// graph-tool -- a general graph modification and manipulation thingy // // Copyright (C) 2007-2012 Tiago de Paula Peixoto // // This program is free software; you can redistribute it and/or // modify it under the terms of the GNU General Public License // as published by the Free Software Foundation; either version 3 // of the License, or (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program. If not, see . #ifndef GRAPH_REWIRING_HH #define GRAPH_REWIRING_HH #if (GCC_VERSION >= 40400) # include # include #else # include # include #endif #include #include #include "graph.hh" #include "graph_filtering.hh" #include "graph_util.hh" #include "sampler.hh" namespace graph_tool { using namespace std; using namespace boost; // returns true if vertices u and v are adjacent. This is O(k(u)). template bool is_adjacent(typename graph_traits::vertex_descriptor u, typename graph_traits::vertex_descriptor v, const Graph& g ) { typename graph_traits::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; } template typename graph_traits::vertex_descriptor source(const pair& e, const vector::edge_descriptor>& edges, const Graph& g) { if (e.second) return target(edges[e.first], g); else return source(edges[e.first], g); } template typename graph_traits::vertex_descriptor target(const pair& e, const vector::edge_descriptor>& edges, const Graph& g) { if (e.second) return source(edges[e.first], g); else return target(edges[e.first], g); } // 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 { template static bool parallel_check_target (size_t e, const pair& te, vector::edge_descriptor>& edges, const Graph &g) { // We want to check that if we swap the target of 'e' with the target of // 'te', as such // // (s) -e--> (t) (s) -e--> (nt) // (te_s) -te-> (nt) => (te_s) -te-> (t) // // no parallel edges are introduced. typename graph_traits::vertex_descriptor s = source(edges[e], g), // current source t = target(edges[e], g), // current target nt = target(te, edges, g), // new target te_s = source(te, edges, g); // target edge source if (is_adjacent(s, nt, g)) return true; // e would clash with an existing edge if (is_adjacent(te_s, t, g)) return true; // te would clash with an existing edge return false; // the coast is clear - hooray! } template static void swap_target (size_t e, const pair& te, vector::edge_descriptor>& edges, EdgeIndexMap edge_index, Graph& g) { // swap the source of the edge 'e' with the source of edge 'se', as // such: // // (s) -e--> (t) (s) -e--> (nt) // (te_s) -te-> (nt) => (te_s) -te-> (t) if (e == te.first) return; // new edges which will replace the old ones typename graph_traits::edge_descriptor ne, nte; ne = add_edge(source(edges[e], g), target(te, edges, g), g).first; if (!te.second) nte = add_edge(source(te, edges, g), target(edges[e], g), g).first; else // keep invertedness (only for undirected graphs) nte = add_edge(target(edges[e], g), source(te, edges, g), g).first; edge_index[nte] = edge_index[edges[te.first]]; remove_edge(edges[te.first], g); edges[te.first] = nte; edge_index[ne] = edge_index[edges[e]]; remove_edge(edges[e], g); edges[e] = ne; } }; // used for verbose display void print_progress(size_t i, size_t n_iter, size_t current, size_t total, stringstream& str) { size_t atom = (total > 200) ? total / 100 : 1; if ( ( (current+1) % atom == 0) || (current + 1) == total) { size_t size = str.str().length(); for (size_t j = 0; j < str.str().length(); ++j) cout << "\b"; str.str(""); str << "(" << i + 1 << " / " << n_iter << ") " << current + 1 << " of " << total << " (" << (current + 1) * 100 / total << "%)"; for (int j = 0; j < int(size - str.str().length()); ++j) str << " "; cout << str.str() << flush; } } class DegreeBlock; // main rewire loop template