Details

    • Sprint:
      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).

        Attachments

          Activity

            People

            • Assignee:
              cvicentiu Vicentiu Ciorbaru
              Reporter:
              svoj Sergey Vojtovich
            • Votes:
              0 Vote for this issue
              Watchers:
              6 Start watching this issue

              Dates

              • Due:
                Created:
                Updated:
                Resolved: