Uploaded image for project: 'Calcite'
  1. Calcite
  2. CALCITE-4049

Reduce the time complexity of getting shortest distances

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 1.24.0
    • Component/s: core
    • Labels:
      None

      Description

      Currently, we have Graphs#makeImmutable to compute the shortest paths between all pairs of nodes. For many scenarios, however, we do not need the exact paths between nodes. Instead, we are only interested in the lengths of the shortest paths.

      To get the path length, we need to get the shortest path first, which is returned as a List, then we call the List#size() method. According to the current implementation, the returned list is of type ConsList. The time complexity of ConsList#size is O(p) (p is the number of vertices on the path), which is inefficient.

      In this issue, we revise the implementation of ConsList#size so that it takes O(1) time. In addition, we also give a utiltiy to get the shortest distances between nodes.

        Attachments

          Activity

            People

            • Assignee:
              fan_li_ya Liya Fan
              Reporter:
              fan_li_ya Liya Fan
            • Votes:
              0 Vote for this issue
              Watchers:
              5 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Time Tracking

                Estimated:
                Original Estimate - Not Specified
                Not Specified
                Remaining:
                Remaining Estimate - 0h
                0h
                Logged:
                Time Spent - 5h 10m
                5h 10m