Hi, I'm looking to traverse a DAG using BFS where vertices are discovered after the last incident edge has been examined. That is, I want to discover vertices lazily rather than the current BFS behavior of discovering vertices eagerly (following the first incident edge). I know I can modify the BFS algorithm to effect this behavior but I'm wondering if anyone has figured out the visitor changes necessary to support this? Thanks. -- Noel
On Mon, 26 Jul 2010, Belcourt, Kenneth wrote:
Hi,
I'm looking to traverse a DAG using BFS where vertices are discovered after the last incident edge has been examined. That is, I want to discover vertices lazily rather than the current BFS behavior of discovering vertices eagerly (following the first incident edge). I know I can modify the BFS algorithm to effect this behavior but I'm wondering if anyone has figured out the visitor changes necessary to support this?
Would just reversing the order of the edge lists work, or is there something more sophisticated you need? -- Jeremiah Willcock
On Jul 26, 2010, at 10:23 PM, Jeremiah Willcock wrote:
On Mon, 26 Jul 2010, Belcourt, Kenneth wrote:
I'm looking to traverse a DAG using BFS where vertices are discovered after the last incident edge has been examined. That is, I want to discover vertices lazily rather than the current BFS behavior of discovering vertices eagerly (following the first incident edge). I know I can modify the BFS algorithm to effect this behavior but I'm wondering if anyone has figured out the visitor changes necessary to support this?
Would just reversing the order of the edge lists work, or is there something more sophisticated you need?
I'm not sure, let me read up on reversing edge lists and I'll let you know. Thanks! -- Noel
participants (2)
-
Belcourt, Kenneth -
Jeremiah Willcock