Details
-
Task
-
Status: Closed (View Workflow)
-
Critical
-
Resolution: Fixed
-
10.2.7-1, 10.2.10
Description
This algorithm returns all reachable leaf nodes from a given origin, or all root nodes that can reach a given destination.
Currently, I had to perform a self-join on the graph table to get a list of all leaf nodes (all destids that themselves are not an origid). This becomes rather expensive the larger the graph is.
I created a simple, large graph of 2 million nodes in (essentially just a chain of nodes, so A->B->C->...) and finding the leaf node from the root node took about 45 seconds. With the new
"leaves" latch it completes in about 7 seconds.
Briefly discussed on oqgraph-dev (thread starting at https://lists.launchpad.net/oqgraph-dev/msg00314.html), but no review was done yet (other than mtr and works for me).