Re: [igraph] find highest degrees

[Tamas Nepusz]

Hi,

> I would like to remove some of the vertices of highest
> order from a graph using the igraph C library. Ie, if the
> vertex-orders were sorted, take the n highest numbers and
> remove the corresponding vertices. Is there some idiomatic
> way of doing this?
Well, I'd try the following:

1. Get the degree vector using igraph_degree()
2. Put the degrees along with the vertex indices into an indexed max-heap. I 
think this data structure is not public yet (I don't know why), but you can 
find everything you need in heap.c (see, e.g., igraph_indheap_init).
3. Pop the vertex indices one by one from the heap and remove the corresponding 
vertices from the graph. Note that if you want to remove more vertices in a 
single step, it is more efficient to delete them at once instead of one by one.

> An unrelated task is taking the union of two igraph_vectors
> of vertex ids considered as sets. That is, combine the lists,
> but don't put in duplicates. This seems like it might be a
> generally useful task. (or eg just return the number of vertices
> in the union)  These were not so difficult to write, but
> are worth mentioning.
I think we have functions for set intersection and set difference in vector.pmt 
(they operate on sorted vectors), but there's no such function for taking the 
union. If you happen to implement it, send me a patch and I'll merge it with 
the trunk.

Best,
-- 
Tamas