" > 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. Marshall _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
