// 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_LAPLACIAN_HH #define GRAPH_LAPLACIAN_HH #include "graph.hh" #include "graph_filtering.hh" #include "graph_util.hh" namespace graph_tool { enum deg_t { IN_DEG, OUT_DEG, TOTAL_DEG }; template typename property_traits::value_type sum_degree(Graph& g, typename graph_traits::vertex_descriptor v, Weight w, EdgeSelector) { typename property_traits::value_type sum = 0; typename EdgeSelector::type e, e_end; for(tie(e, e_end) = EdgeSelector::get_edges(v, g); e != e_end; ++e) sum += get(w, *e); return sum; } template double sum_degree(Graph& g, typename graph_traits::vertex_descriptor v, ConstantPropertyMap w, all_edges_iteratorS) { return total_degreeS()(v, g); } template double sum_degree(Graph& g, typename graph_traits::vertex_descriptor v, ConstantPropertyMap w, in_edge_iteratorS) { return in_degreeS()(v, g); } template double sum_degree(Graph& g, typename graph_traits::vertex_descriptor v, ConstantPropertyMap w, out_edge_iteratorS) { return out_degreeS()(v, g); } struct get_laplacian { template void operator()(const Graph& g, Index index, Weight weight, deg_t deg, multi_array_ref& data, multi_array_ref& i, multi_array_ref& j) const { int pos = 0; typename graph_traits::edge_iterator e, e_end; for(tie(e, e_end) = edges(g); e != e_end; ++e) { if (source(*e, g) == target(*e, g)) continue; data[pos] = -get(weight, *e); i[pos] = get(index, target(*e, g)); j[pos] = get(index, source(*e, g)); ++pos; if (!is_directed::apply::type::value) { data[pos] = -get(weight, *e); i[pos] = get(index, source(*e, g)); j[pos] = get(index, target(*e, g)); ++pos; } } typename graph_traits::vertex_iterator v, v_end; for(tie(v, v_end) = vertices(g); v != v_end; ++v) { double k = 0; switch (deg) { case OUT_DEG: k = sum_degree(g, *v, weight, out_edge_iteratorS()); break; case IN_DEG: k = sum_degree(g, *v, weight, in_edge_iteratorS()); break; case TOTAL_DEG: k = sum_degree(g, *v, weight, all_edges_iteratorS()); } data[pos] = k; i[pos] = j[pos] = get(index, *v); ++pos; } } }; struct get_norm_laplacian { template void operator()(const Graph& g, Index index, Weight weight, deg_t deg, multi_array_ref& data, multi_array_ref& i, multi_array_ref& j) const { int pos = 0; typename graph_traits::vertex_iterator v, v_end; for(tie(v, v_end) = vertices(g); v != v_end; ++v) { double ks = 0; switch (deg) { case OUT_DEG: ks = sum_degree(g, *v, weight, out_edge_iteratorS()); break; case IN_DEG: ks = sum_degree(g, *v, weight, in_edge_iteratorS()); break; case TOTAL_DEG: ks = sum_degree(g, *v, weight, all_edges_iteratorS()); } typename graph_traits::out_edge_iterator e, e_end; for(tie(e, e_end) = out_edges(*v, g); e != e_end; ++e) { if (source(*e, g) == target(*e, g)) continue; double kt = 0; switch (deg) { case OUT_DEG: kt = sum_degree(g, target(*e, g), weight, out_edge_iteratorS()); break; case IN_DEG: kt = sum_degree(g, target(*e, g), weight, in_edge_iteratorS()); break; case TOTAL_DEG: kt = sum_degree(g, target(*e, g), weight, all_edges_iteratorS()); } if (ks * kt > 0) data[pos] = -get(weight, *e) / sqrt(ks * kt); i[pos] = get(index, target(*e, g)); j[pos] = get(index, source(*e, g)); ++pos; } if (ks > 0) data[pos] = 1; i[pos] = j[pos] = get(index, *v); ++pos; } } }; } // namespace graph_tool #endif // GRAPH_LAPLACIAN_HH