// graph-tool -- a general graph modification and manipulation thingy // // Copyright (C) 2006-2019 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_VERTEX_SIMILARITY_HH #define GRAPH_VERTEX_SIMILARITY_HH #include "graph_util.hh" namespace graph_tool { using namespace std; using namespace boost; template double dice(Vertex u, Vertex v, Mark& mark, Weight& weight, Graph& g) { typename property_traits::value_type count = 0, ku = 0, kv = 0; for (auto e : out_edges_range(u, g)) { auto w = weight[e]; mark[target(e, g)] += w; ku += w; } for (auto e : out_edges_range(v, g)) { auto w = weight[e]; auto dw = std::min(w, mark[target(e, g)]); mark[target(e, g)] -= dw; count += dw; kv += w; } for (auto w : adjacent_vertices_range(u, g)) mark[w] = 0; return 2 * count / double(ku + kv); } template double jaccard(Vertex u, Vertex v, Mark& mark, Weight& weight, Graph& g) { typename property_traits::value_type count = 0, total = 0; for (auto e : out_edges_range(u, g)) { auto w = weight[e]; mark[target(e, g)] += w; total += w; } for (auto e : out_edges_range(v, g)) { auto w = weight[e]; auto dw = std::min(w, mark[target(e, g)]); count += dw; mark[target(e, g)] -= dw; total += w - dw; } for (auto w : adjacent_vertices_range(u, g)) mark[w] = 0; return count / double(total); } template double inv_log_weighted(Vertex u, Vertex v, Mark& mark, Weight& weight, Graph& g) { double count = 0; for (auto e : out_edges_range(u, g)) mark[target(e, g)] += weight[e]; for (auto w : adjacent_vertices_range(v, g)) { if (mark[w] > 0) { if (graph_tool::is_directed(g)) count += mark[w] / log(in_degreeS()(w, g, weight)); else count += mark[w] / log(out_degreeS()(w, g, weight)); } } for (auto w : adjacent_vertices_range(u, g)) mark[w] = 0; return count; } template void all_pairs_similarity(Graph& g, VMap s, Sim&& f, Weight& weight) { vector::value_type> mask(num_vertices(g)); #pragma omp parallel if (num_vertices(g) > OPENMP_MIN_THRESH) \ firstprivate(mask) parallel_vertex_loop_no_spawn (g, [&](auto v) { s[v].resize(num_vertices(g)); for (auto w : vertices_range(g)) s[v][w] = f(v, w, mask, weight); }); } template void some_pairs_similarity(Graph& g, Vlist& vlist, Slist& slist, Sim&& f, Weight& weight) { vector::value_type> mark(num_vertices(g)); #pragma omp parallel if (num_vertices(g) > OPENMP_MIN_THRESH) \ firstprivate(mark) parallel_loop_no_spawn (vlist, [&](size_t i, const auto& val) { size_t u = val[0]; size_t v = val[1]; slist[i] = f(u, v, mark, weight); }); } } // graph_tool namespace #endif // GRAPH_VERTEX_SIMILARITY_HH