// 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 . // based on code written by Alexandre Hannud Abdo #ifndef GRAPH_EXTENDED_CLUSTERING_HH #define GRAPH_EXTENDED_CLUSTERING_HH #if (GCC_VERSION >= 40400) # include #else # include #endif #include namespace graph_tool { using namespace std; using namespace boost; // graph filter to remove a single vertex template struct single_vertex_filter { single_vertex_filter() {} single_vertex_filter(Vertex v):_v(v) {} bool operator()(Vertex v) const { return v != _v; } Vertex _v; }; class bfs_stop_exception {}; // this will abort the BFS search when no longer useful template struct bfs_max_depth_watcher { typedef on_tree_edge event_filter; bfs_max_depth_watcher(TargetSet& targets, size_t max_depth, DistanceMap distance) : _targets(targets), _max_depth(max_depth), _distance(distance) {} template void operator()(typename graph_traits::edge_descriptor e, const Graph& g) { typename graph_traits::vertex_descriptor v = target(e,g); if (get(_distance, v) > _max_depth) throw bfs_stop_exception(); if (_targets.find(v) != _targets.end()) _targets.erase(v); if (_targets.empty()) throw bfs_stop_exception(); } TargetSet& _targets; size_t _max_depth; DistanceMap _distance; }; // abstract target collecting so algorithm works for bidirectional and // undirected graphs template void collect_targets(Vertex v, Graph& g, Targets& t, DirectedCategory) { typename graph_traits::in_edge_iterator ei, ei_end; typename graph_traits::vertex_descriptor u; for(tie(ei, ei_end) = in_edges(v, g); ei != ei_end; ++ei) { u = source(*ei, g); if (u == v) // no self-loops continue; if (t.find(u) != t.end()) // avoid parallel edges continue; t.insert(u); } } template void collect_targets(Vertex v, Graph& g, Targets& t, undirected_tag) { typename graph_traits::out_edge_iterator ei, ei_end; typename graph_traits::vertex_descriptor u; for(tie(ei, ei_end) = out_edges(v, g); ei != ei_end; ++ei) { u = target(*ei, g); if (u == v) // no self-loops continue; if (t.find(u) != t.end()) // avoid parallel edges continue; t.insert(u); } } // get_extended_clustering struct get_extended_clustering { template void operator()(const Graph& g, IndexMap vertex_index, vector cmaps) const { typedef typename graph_traits::vertex_descriptor vertex_t; int i, N = num_vertices(g); #pragma omp parallel for default(shared) private(i) schedule(dynamic) for (i = 0; i < N; ++i) { vertex_t v = vertex(i, g); if (v == graph_traits::null_vertex()) continue; // We must disconsider paths through the original vertex typedef single_vertex_filter filter_t; typedef filtered_graph fg_t; fg_t fg(g, keep_all(), filter_t(v)); typedef DescriptorHash hasher_t; typedef tr1::unordered_set neighbour_set_t; neighbour_set_t neighbours(0, hasher_t(vertex_index)); neighbour_set_t targets(0, hasher_t(vertex_index)); typename neighbour_set_t::iterator ni, ti; // collect targets, neighbours and calculate normalization factor collect_targets(v, g, targets, typename graph_traits::directed_category()); size_t k_in = targets.size(), k_out, k_inter=0, z; typename graph_traits::adjacency_iterator a, a_end; for (tie(a, a_end) = adjacent_vertices(v, g); a != a_end; ++a) { if (*a == v) // no self-loops continue; if (neighbours.find(*a) != neighbours.end()) // avoid parallel continue; // edges neighbours.insert(*a); if (targets.find(*a) != targets.end()) ++k_inter; } k_out = neighbours.size(); z = (k_in*k_out) - k_inter; // And now we setup and start the BFS bonanza for (ni = neighbours.begin(); ni != neighbours.end(); ++ni) { typedef tr1::unordered_map > dmap_t; dmap_t dmap(0, DescriptorHash(vertex_index)); InitializedPropertyMap distance_map(dmap, numeric_limits::max()); typedef tr1::unordered_map > cmap_t; cmap_t cmap(0, DescriptorHash(vertex_index)); InitializedPropertyMap color_map(cmap, color_traits::white()); try { distance_map[*ni] = 0; neighbour_set_t specific_targets = targets; specific_targets.erase(*ni); bfs_max_depth_watcher > watcher(specific_targets, cmaps.size(), distance_map); breadth_first_visit(fg, *ni, visitor (make_bfs_visitor (make_pair(record_distances (distance_map, boost::on_tree_edge()), watcher))). color_map(color_map)); } catch (bfs_stop_exception) {} for (ti = targets.begin(); ti != targets.end(); ++ti) { if (*ti == *ni) // no self-loops continue; if (distance_map[*ti] <= cmaps.size()) cmaps[distance_map[*ti]-1][v] += 1.0/z; } } } } }; } // graph_tool namespace #endif // GRAPH_EXTENDED_CLUSTERING_HH