/* -*- mode: C -*-  */
/*
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard street, Cambridge, MA 02139 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

*/

#include "igraph_community.h"
#include "igraph_memory.h"
#include "igraph_interface.h"
#include "igraph_iterators.h"
#include "config.h"

/**
 * \function igraph_coreness
 * \brief Finding the coreness of the vertices in a network.
 *
 * The k-core of a graph is a maximal subgraph in which each vertex
 * has at least degree k. (Degree here means the degree in the
 * subgraph of course.). The coreness of a vertex is the highest order
 * of a k-core containing the vertex.
 *
 * </para><para>
 * This function implements the algorithm presented in Vladimir
 * Batagelj, Matjaz Zaversnik: An O(m) Algorithm for Cores
 * Decomposition of Networks.
 * \param graph The input graph.
 * \param cores Pointer to an initialized vector, the result of the
 *        computation will be stored here. It will be resized as
 *        needed. For each vertex it contains the highest order of a
 *        core containing the vertex.
 * \param mode For directed graph it specifies whether to calculate
 *        in-cores, out-cores or the undirected version. It is ignored
 *        for undirected graphs. Possible values: \c IGRAPH_ALL
 *        undirected version, \c IGRAPH_IN in-cores, \c IGRAPH_OUT
 *        out-cores.
 * \return Error code.
 *
 * Time complexity: O(|E|), the number of edges.
 */

int igraph_coreness(const igraph_t *graph, igraph_vector_t *cores,
                    igraph_neimode_t mode) {

    long int no_of_nodes = igraph_vcount(graph);
    long int *bin, *vert, *pos;
    long int maxdeg;
    long int i, j = 0;
    igraph_vector_t neis;
    igraph_neimode_t omode;

    if (mode != IGRAPH_ALL && mode != IGRAPH_OUT && mode != IGRAPH_IN) {
        IGRAPH_ERROR("Invalid mode in k-cores", IGRAPH_EINVAL);
    }
    if (!igraph_is_directed(graph) || mode == IGRAPH_ALL) {
        mode = omode = IGRAPH_ALL;
    } else if (mode == IGRAPH_IN) {
        omode = IGRAPH_OUT;
    } else {
        omode = IGRAPH_IN;
    }

    vert = igraph_Calloc(no_of_nodes, long int);
    if (vert == 0) {
        IGRAPH_ERROR("Cannot calculate k-cores", IGRAPH_ENOMEM);
    }
    IGRAPH_FINALLY(igraph_free, vert);
    pos = igraph_Calloc(no_of_nodes, long int);
    if (pos == 0) {
        IGRAPH_ERROR("Cannot calculate k-cores", IGRAPH_ENOMEM);
    }
    IGRAPH_FINALLY(igraph_free, pos);

    /* maximum degree + degree of vertices */
    IGRAPH_CHECK(igraph_degree(graph, cores, igraph_vss_all(), mode,
                               IGRAPH_LOOPS));
    maxdeg = (long int) igraph_vector_max(cores);

    bin = igraph_Calloc(maxdeg + 1, long int);
    if (bin == 0) {
        IGRAPH_ERROR("Cannot calculate k-cores", IGRAPH_ENOMEM);
    }
    IGRAPH_FINALLY(igraph_free, bin);

    /* degree histogram */
    for (i = 0; i < no_of_nodes; i++) {
        bin[ (long int)VECTOR(*cores)[i] ] += 1;
    }

    /* start pointers */
    j = 0;
    for (i = 0; i <= maxdeg; i++) {
        long int k = bin[i];
        bin[i] = j;
        j += k;
    }

    /* sort in vert (and corrupt bin) */
    for (i = 0; i < no_of_nodes; i++) {
        pos[i] = bin[(long int)VECTOR(*cores)[i]];
        vert[pos[i]] = i;
        bin[(long int)VECTOR(*cores)[i]] += 1;
    }

    /* correct bin */
    for (i = maxdeg; i > 0; i--) {
        bin[i] = bin[i - 1];
    }
    bin[0] = 0;

    /* this is the main algorithm */
    IGRAPH_VECTOR_INIT_FINALLY(&neis, maxdeg);
    for (i = 0; i < no_of_nodes; i++) {
        long int v = vert[i];
        IGRAPH_CHECK(igraph_neighbors(graph, &neis, (igraph_integer_t) v, omode));
        for (j = 0; j < igraph_vector_size(&neis); j++) {
            long int u = (long int) VECTOR(neis)[j];
            if (VECTOR(*cores)[u] > VECTOR(*cores)[v]) {
                long int du = (long int) VECTOR(*cores)[u];
                long int pu = pos[u];
                long int pw = bin[du];
                long int w = vert[pw];
                if (u != w) {
                    pos[u] = pw;
                    pos[w] = pu;
                    vert[pu] = w;
                    vert[pw] = u;
                }
                bin[du] += 1;
                VECTOR(*cores)[u] -= 1;
            }
        }
    }

    igraph_vector_destroy(&neis);
    IGRAPH_FINALLY_CLEAN(1);

    igraph_free(bin);
    igraph_free(pos);
    igraph_free(vert);
    IGRAPH_FINALLY_CLEAN(3);
    return 0;
}