[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] Traversing edges in sorted order

From: lesshaste
Subject: Re: [igraph] Traversing edges in sorted order
Date: Sun, 28 Jul 2013 19:27:27 +0100 (BST)

> To do this I need to consider the out edges from each node in sorted order by 
> weight. The problem is that making a list of the edges and sorting them each 
> time I visit a node is slow on my large graph.
> I could explicitly store the sorted list of edges at each node but this would 
> use too much extra space on my large graph.
How large is your graph? Pre-sorting the edge indices for every node takes only 
a few seconds even on a graph with one million edges on my machine:

inclist = g.get_inclist()
weights = g.es["weight"]
for row in inclist:
    row.sort(key=weights.__getitem__, reverse=True)

If you cannot afford storing the whole pre-sorted list at once but you visit 
some nodes more frequently than others, you could probably try caching the 
pre-sorted lists in a memory-limited least-recently-used cache. This way you 
could keep your memory usage under control while not having to recalculate the 
list every time you visit a node if the list is still in the cache.

Thank you for the reply.

I can afford the time to presort the edge indices for every node once as you 
suggest. I just wanted to avoid using the space to store all the edges twice. 
Once in the normal igraph graph and once in a sorted list labeling each vertex. 
 It seems that you are effectively representing the same graph twice if you do 
that. Maybe there is no way round this however.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]