[
https://issues.apache.org/jira/browse/CALCITE-4049?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17136338#comment-17136338
]
Liya Fan commented on CALCITE-4049:
-----------------------------------
[~xndai] Thanks for your clarification. In general, I agree with your point, as
the concrete paths are not that important. Even if we need the shortest paths,
we may not need all pairs of shortest paths. However, I am not sure if we need
to keep the {{getShortestPath}} API, for the sake of backward compatibility.
[~julianhyde] I agree with you that the shortest path lengths tend to be much
smaller than the number of nodes in the graph. For cases when we need to get
the shortest path lengths many times (e.g. calculating the graph diameter), the
O(p) time complexity can be a bottleneck. Graphs#makeImmutable is another good
example where the shortest path lengths are used repeatedly, as you indicated.
> 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
> Priority: Major
> Fix For: 1.24.0
>
> Time Spent: 1h 20m
> Remaining Estimate: 0h
>
> 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.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
