/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2011-12 Gabor Csardi 334 Harvard st, Cambridge, MA, 02138 USA 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 2 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, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ /* * SCGlib : A C library for the spectral coarse graining of matrices * as described in the paper: Shrinking Matrices while preserving their * eigenpairs with Application to the Spectral Coarse Graining of Graphs. * Preprint available at * * Copyright (C) 2008 David Morton de Lachapelle * * 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 2 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, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA * 02110-1301 USA * * DESCRIPTION * ----------- * The intervals_method and intervals_plus_kmeans implements the * methods of sec. 5.3.2 and sec. 5.3.3 of the above reference. * They take an eigenvector 'v' as parameter and a vector 'breaks' * of length 'nb', which provide the intervals used to cut 'v'. * Then all components of 'v' that fall into the same interval are * assigned the same group label in 'gr'. The group labels are * positive consecutive integers starting from 0. * The intervals_method function is adapted from bincode of the R * base package. * The intervals_plus_kmeans is initialized with regularly-spaced * breaks, which rougly corresponds to the intervals_method. Then * kmeans minimizes iteratively the objective function until it gets * stuck in a (usually) local minimum, or until 'itermax' is reached. * So far, the breaks_computation function allows computation of * constant bins, as used in intervals_method, and of equidistant * centers as used in intervals_plus_kmeans. */ #include "igraph_error.h" #include "igraph_types.h" #include "scg_headers.h" #include "igraph_memory.h" #include "igraph_vector.h" int igraph_i_intervals_plus_kmeans(const igraph_vector_t *v, int *gr, int n, int n_interv, int maxiter) { int i; igraph_vector_t centers; IGRAPH_VECTOR_INIT_FINALLY(¢ers, n_interv); igraph_i_breaks_computation(v, ¢ers, n_interv, 2); IGRAPH_CHECK(igraph_i_kmeans_Lloyd(v, n, 1, ¢ers, n_interv, gr, maxiter)); /*renumber the groups*/ for (i = 0; i < n; i++) { gr[i] = gr[i] - 1; } igraph_vector_destroy(¢ers); IGRAPH_FINALLY_CLEAN(1); return 0; } int igraph_i_intervals_method(const igraph_vector_t *v, int *gr, int n, int n_interv) { int i, lo, hi, new; const int lft = 1; const int include_border = 1; igraph_vector_t breaks; IGRAPH_VECTOR_INIT_FINALLY(&breaks, n_interv + 1); IGRAPH_CHECK(igraph_i_breaks_computation(v, &breaks, n_interv + 1, 1)); for (i = 0; i < n; i++) { lo = 0; hi = n_interv; if (VECTOR(*v)[i] < VECTOR(breaks)[lo] || VECTOR(breaks)[hi] < VECTOR(*v)[i] || (VECTOR(*v)[i] == VECTOR(breaks)[lft ? hi : lo] && !include_border)) { /* Do nothing */ } else { while (hi - lo >= 2) { new = (hi + lo) / 2; if (VECTOR(*v)[i] > VECTOR(breaks)[new] || (lft && VECTOR(*v)[i] == VECTOR(breaks)[new])) { lo = new; } else { hi = new; } } gr[i] = lo; } } igraph_vector_destroy(&breaks); IGRAPH_FINALLY_CLEAN(1); return 0; } int igraph_i_breaks_computation(const igraph_vector_t *v, igraph_vector_t *breaks, int nb, int method) { int i; igraph_real_t eps, vmin, vmax; igraph_vector_minmax(v, &vmin, &vmax); if (vmax == vmin) { IGRAPH_ERROR("There is only one (repeated) value in argument 'v' " "of bin_size_computation()", IGRAPH_EINVAL); } if (nb < 2) { IGRAPH_ERROR("'nb' in bin_size_computation() must be >= 2", IGRAPH_EINVAL); } switch (method) { case 1: /* constant bins for fixed-size intervals method */ eps = (vmax - vmin) / (igraph_real_t)(nb - 1); VECTOR(*breaks)[0] = vmin; for (i = 1; i < nb - 1; i++) { VECTOR(*breaks)[i] = VECTOR(*breaks)[i - 1] + eps; } VECTOR(*breaks)[nb - 1] = vmax; break; case 2: /* equidistant centers for kmeans */ eps = (vmax - vmin) / (igraph_real_t)nb; VECTOR(*breaks)[0] = vmin + eps / 2.; for (i = 1; i < nb; i++) { VECTOR(*breaks)[i] = VECTOR(*breaks)[i - 1] + eps; } break; /* TODO: implement logarithmic binning for power-law-like distributions */ default: IGRAPH_ERROR("Internal SCG error, this should ot happen", IGRAPH_FAILURE); } return 0; }