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)
