[Top][All Lists]

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

Re: [igraph] Traversing edges in sorted order

From: Tamás Nepusz
Subject: Re: [igraph] Traversing edges in sorted order
Date: Sun, 28 Jul 2013 20:16:46 +0200

> 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.


reply via email to

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