[jira] [Created] (CALCITE-4049) Reduce the time complexity of getting shortest distances

["Liya Fan (Jira)" <ji...@apache.org>]

Liya Fan created CALCITE-4049:
---------------------------------

             Summary: Reduce the time complexity of getting shortest distances
                 Key: CALCITE-4049
                 URL: https://issues.apache.org/jira/browse/CALCITE-4049
             Project: Calcite
          Issue Type: Improvement
          Components: core
            Reporter: Liya Fan
            Assignee: Liya Fan


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(n) (n 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. 



--
This message was sent by Atlassian Jira
(v8.3.4#803005)