[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] find highest degrees
From: |
John Lapeyre |
Subject: |
Re: [igraph] find highest degrees |
Date: |
Fri, 19 Feb 2010 19:45:28 +0100 |
User-agent: |
KMail/1.12.4 (Linux/2.6.31.9; KDE/4.3.4; x86_64; ; ) |
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 (°rees,x,n); // vector_t degrees points to the C array
igraph_degree(graph,°rees,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;
}