// graph-tool -- a general graph modification and manipulation thingy // // Copyright (C) 2006-2013 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_EIGENVECTOR_HH #define GRAPH_EIGENVECTOR_HH #include "graph.hh" #include "graph_filtering.hh" #include "graph_util.hh" #include using __gnu_cxx::power; namespace graph_tool { using namespace std; using namespace boost; struct get_eigenvector { template void operator()(Graph& g, VertexIndex vertex_index, WeightMap w, CentralityMap c, double epsilon, size_t max_iter, long double& eig) const { typedef typename property_traits::value_type c_type; typedef typename property_traits::value_type t_type; CentralityMap c_temp(vertex_index, num_vertices(g)); t_type norm = 0; t_type delta = epsilon + 1; size_t iter = 0; int i, N = num_vertices(g); while (delta >= epsilon) { norm = 0; #pragma omp parallel for default(shared) private(i) \ schedule(static, 100) reduction(+:norm) for (i = 0; i < N; ++i) { typename graph_traits::vertex_descriptor v = vertex(i, g); if (v == graph_traits::null_vertex()) continue; c_temp[v] = 0; typename in_or_out_edge_iteratorS::type e, e_end; for (tie(e, e_end) = in_or_out_edge_iteratorS::get_edges(v, g); e != e_end; ++e) { typename graph_traits::vertex_descriptor s; if (is_directed::apply::type::value) s = source(*e,g); else s = target(*e,g); c_temp[v] += get(w, *e) * c[s]; } norm += power(c_temp[v], 2); } norm = sqrt(norm); delta = 0; #pragma omp parallel for default(shared) private(i) \ schedule(static, 100) reduction(+:delta) for (i = 0; i < N; ++i) { typename graph_traits::vertex_descriptor v = vertex(i, g); if (v == graph_traits::null_vertex()) continue; c_temp[v] /= norm; delta += abs(c_temp[v] - c[v]); } swap(c_temp, c); ++iter; if (max_iter > 0 && iter== max_iter) break; } if (iter % 2 != 0) { #pragma omp parallel for default(shared) private(i) \ schedule(static, 100) for (i = 0; i < N; ++i) { typename graph_traits::vertex_descriptor v = vertex(i, g); if (v == graph_traits::null_vertex()) continue; c[v] = c_temp[v]; } } eig = 1. / norm; } }; } #endif