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

**[igraph] Traversing edges in sorted order**, *lesshaste*, `2013/07/28`
**Re: [igraph] Traversing edges in sorted order**, *Tamás Nepusz*, `2013/07/28`
**Re: [igraph] Traversing edges in sorted order**,
*lesshaste* **<=**
**Re: [igraph] Traversing edges in sorted order**, *Tamás Nepusz*, `2013/07/28`
**Re: [igraph] Traversing edges in sorted order**, *lesshaste*, `2013/07/29`
**Re: [igraph] Traversing edges in sorted order**, *Tamás Nepusz*, `2013/07/29`
**Re: [igraph] Traversing edges in sorted order**, *lesshaste*, `2013/07/30`
**Re: [igraph] Traversing edges in sorted order**, *Tamás Nepusz*, `2013/07/30`