www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Keep Track of the Best N Nodes in a Graph Traversal Algorithm

reply "Per =?UTF-8?B?Tm9yZGzDtnci?= <per.nordlow gmail.com> writes:
I have graph traversal algorithm that needs to keep track of the 
N "best" node visit. Every time a visit a new node I get its 
goodness along with a ref to it. I then want to compare it to 
every currently best node in this list and replace it with the 
worst one if its better than the worst. How do I most easily do 
this with regards to minimizing GC-usage.

For N = 3 I mean something like this:

(A,1) => [(A,1)]
(B,2) => [(A,1), (B,2)]
(C,3) => [(A,1), (B,2), (C,3)]
(X,0) => [(X,0), (A,1), (B,2)]
(Y,1) => [(X,0), (Y,1), (A,1)]
...

(A,1) means we just visited node with goodness (distance) 1
Mar 25 2015
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Nordlöw:

 I have graph traversal algorithm that needs to keep track of 
 the N "best" node visit.
std.algorithm.topNCopy? Bye, bearophile
Mar 25 2015
next sibling parent "Per =?UTF-8?B?Tm9yZGzDtnci?= <per.nordlow gmail.com> writes:
On Wednesday, 25 March 2015 at 13:55:29 UTC, bearophile wrote:
 Nordlöw:

 I have graph traversal algorithm that needs to keep track of 
 the N "best" node visit.
std.algorithm.topNCopy? Bye, bearophile
Could you please elaborate a bit how you mean this should be used. Notice that the number of visited nodes are in the millions or perhaps even tens of millions. And N is typically 100-1000.
Mar 25 2015
prev sibling parent reply "Per =?UTF-8?B?Tm9yZGzDtnci?= <per.nordlow gmail.com> writes:
On Wednesday, 25 March 2015 at 13:55:29 UTC, bearophile wrote:
 Nordlöw:

 I have graph traversal algorithm that needs to keep track of 
 the N "best" node visit.
std.algorithm.topNCopy? Bye, bearophile
Notice that, ideally, I would like my list of top-nodes to have a fixed size during the whole algorithm (99.9 % of time) as soon it has reached the length of N.
Mar 25 2015
parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
On Wednesday, 25 March 2015 at 14:40:28 UTC, Per Nordlöw wrote:
 On Wednesday, 25 March 2015 at 13:55:29 UTC, bearophile wrote:
 Nordlöw:

 I have graph traversal algorithm that needs to keep track of 
 the N "best" node visit.
std.algorithm.topNCopy? Bye, bearophile
Notice that, ideally, I would like my list of top-nodes to have a fixed size during the whole algorithm (99.9 % of time) as soon it has reached the length of N.
What's wrong with binary heaps?
Mar 25 2015
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Wednesday, 25 March 2015 at 17:49:49 UTC, Tobias Pankrath 
wrote:
 What's wrong with binary heaps?
Ahh, a Binary Heap perfectly matches my needs. https://en.wikipedia.org/wiki/Binary_heap http://dlang.org/phobos/std_container_binaryheap.html Thx
Mar 25 2015
parent "bearophile" <bearophileHUGS lycos.com> writes:
Nordlöw:

 Ahh, a Binary Heap perfectly matches my needs.

 https://en.wikipedia.org/wiki/Binary_heap
 http://dlang.org/phobos/std_container_binaryheap.html
But isn't topNCopy using a heap? Bye, bearophile
Mar 25 2015