Re: [igraph] find highest degrees

[John Lapeyre]

Thanks, that seems to be efficient.

Here is a routine that returns the ordered indices. 

It is not written in a way to include in the source, because
I know how to do neither of 1) rebuild the library
quickly after changing one source file; nor 2) compile the
routine outside of the build system, but with the correct
headers and files required to process macros, etc. Does someone
have advice on this?

I thought about adding an option to return the degrees themselves, but
I couldn't find a way to do that without putting a conditional in the
innermost loop... The name of the function is not so great.


Thanks,
John

------

/**
 * \function igraph_degrees_ordered_inds
 * \brief return vids of vs of highest degrees
 * This routine effectively orders a list of the vids according
 * to the degree of the corresponding vertex
 * with the vid of the vertex of highest degree as the first element,
 * and returns vids from the top of this list. For example,
 * *order[0] will be the vid of the vertex of highest degree.
 *
 * The return vector order must be initialized, but it will be resized.
 * The order of vids of vertices of the same degree is undefined.
 * 
 * \param order the output vector of vids
 * \param nout the number of vids to return. nout=-1 to return all of them
 * \param mode passed directly to the same param in igraph_degree
 * \param loops passed directly to the same param in igraph_degree
 */
int igraph_degrees_ordered_inds (const igraph_t *graph, igraph_vector_t *order, 
long int nout,
                                 igraph_neimode_t mode, igraph_bool_t loops ) {
  igraph_vector_t degrees;
  double *x;              // C array to hold the degrees
  int i;
  igraph_indheap_t h;
  long int n = igraph_vcount(graph);
  if ( nout < 0) nout = n;
  x = (double *) malloc(n*sizeof(double));
  if (x == 0) 
    IGRAPH_ERROR("degrees_ordered_inds failed", IGRAPH_ENOMEM);
  igraph_vector_view (&degrees,x,n); // vector_t degrees points to the C array
  igraph_degree(graph,&degrees,igraph_vss_all(),mode,loops); // fill up x with 
degrees
  igraph_indheap_init_array(&h,x,n); // initialize heap and move indices to 
satisfy heap requirements
  igraph_vector_resize(order,nout);
  for(i=0;i<nout;i++) {
    VECTOR(*order)[i] = igraph_indheap_max_index(&h)-1;// convert rank to 
0-base index
    igraph_indheap_delete_max(&h); // 'pop' the root node and rearrange tree
  }
  igraph_indheap_destroy(&h);
  free(x);
  return 0;
}