/**
 * \function igraph_membership_reindex
 * \brief Reindexes membership vector with sparse community id's to be
 * dense and to start from zero
 * 
 * This function reindexes membership vector with sparse community id's
 * to be dense and to start from zero.
 * 
 * </para><para>
  * \param membership Numeric vector which gives the type of each
 *     vertex, ie. the component to which it belongs.
 * \param new2old Pointer to an vector, which will contain old id for
 *    each new one, if not NULL. The vector will be resized as needed.
 * 
 * Time complexity: should be O(nlogn) for n elements.
 */

int igraph_membership_reindex(igraph_vector_t *membership,
				   igraph_vector_t *new2old) {
  
  long int size=igraph_vector_size(membership);
  long int ids;
  long int i, p;
  igraph_vector_t old_sorted, new_sorted;
  
  // create sorted membership vector
  IGRAPH_CHECK(igraph_vector_copy(&old_sorted, membership));
  IGRAPH_FINALLY(igraph_vector_destroy, &old_sorted);
  igraph_vector_sort(&old_sorted);
  
  // reindex from 0 to new membership vector
  IGRAPH_VECTOR_INIT_FINALLY(&new_sorted, size);
  long int last_id = 0;
  long int new_id = -1;
  long int old_id;
  for (i = 0; i < size; i++) {
    old_id = (long int)VECTOR(old_sorted)[i];

	  if ((old_id != last_id) || (new_id == -1)) {
	    last_id = old_id;
		  new_id++;	    
    }

    VECTOR(new_sorted)[i] = new_id;
  }
  ids = new_id + 1;
  
  if (new2old) {
    IGRAPH_CHECK(igraph_vector_resize(new2old, ids));
	  igraph_vector_null(new2old);
  }
  
  // finally reindex membership vector
  for (i = 0; i < size; i++) {
    igraph_vector_binsearch(&old_sorted, VECTOR(*membership)[i], &p);
    new_id = VECTOR(new_sorted)[p];

    VECTOR(*membership)[i] = new_id;
	
	  if (new2old) {
	    VECTOR(*new2old)[new_id] = VECTOR(old_sorted)[p];
	  }
  }

  igraph_vector_destroy(&old_sorted);
  igraph_vector_destroy(&new_sorted);
  IGRAPH_FINALLY_CLEAN(2);
  
  return 0;
}

/**
 * \function igraph_shrink
 * \brief Shrink the graph according to vertex membership
 * 
 * This function shrinks the graph according to vertex membership. The
 * vertices with the same id will be collapsed into one vertex in the resulting
 * graph. The number of edges will remain unchanged, while rewiring them
 * between new vertices with the same id.
 * 
 * </para><para>
 * \param graph The graph which will be shrinked.
 * \param membership Numeric vector which gives the id of each
 *     vertex, ie. the component to which it belongs. It will
 *    be modified to describe shrinked graph vertex id's.
 * 
 * Time complexity: O(|V|log|V|+|E|), the O(nlogn) for reindexing membership vector
 *  plus the number of edges.
 */

int igraph_shrink(igraph_t *graph, igraph_vector_t *membership) {
  
  igraph_vector_t new2old, edges;
  long int no_of_edges=igraph_ecount(graph);
  long int i, e;
  igraph_integer_t from, to;
  
  if (igraph_vector_size(membership) < igraph_vcount(graph)) {
    IGRAPH_ERROR("cannot shrink graph, membership vector too short",
      IGRAPH_EINVAL);
  }
  
  IGRAPH_VECTOR_INIT_FINALLY(&new2old, 0);
  IGRAPH_CHECK(igraph_membership_reindex(membership, &new2old));

  IGRAPH_VECTOR_INIT_FINALLY(&edges, no_of_edges * 2);
  
  // create shrinked graph edge list
  for (e = 0; e < no_of_edges; e++) {
    igraph_edge(graph, e, &from, &to);
	  VECTOR(edges)[e * 2] = VECTOR(*membership)[(long int) from];
	  VECTOR(edges)[e * 2 + 1] = VECTOR(*membership)[(long int) to];
  }
  
  long int n = igraph_vector_size(&new2old);
  igraph_bool_t directed = igraph_is_directed(graph);
  igraph_destroy(graph);
  igraph_create(graph, &edges, n, directed);
  
  IGRAPH_CHECK(igraph_vector_resize(membership, n));
  for (i = 0; i < n; i++) {
    VECTOR(*membership)[i] = VECTOR(new2old)[i];
  }
  
  igraph_vector_destroy(&new2old);
  igraph_vector_destroy(&edges);
  IGRAPH_FINALLY_CLEAN(2);
  
  return 0;
}