[GitHub] [calcite] liyafan82 commented on a change in pull request #2027: [CALCITE-4049] Improve the implementation of the shortest-path algorithm

liyafan82 commented on a change in pull request #2027:
URL: https://github.com/apache/calcite/pull/2027#discussion_r446590701

##########
File path: core/src/main/java/org/apache/calcite/util/graph/Graphs.java
##########
@@ -102,41 +99,28 @@ public int size() {
*/
public static class FrozenGraph<V, E extends DefaultEdge> {
private final DefaultDirectedGraph<V, E> graph;
-    private final Map<Pair<V, V>, List<V>> shortestPaths;
+    private final Map<Pair<V, V>, int[]> shortestDistances;

/** Creates a frozen graph as a copy of another graph. */
FrozenGraph(DefaultDirectedGraph<V, E> graph,
-        Map<Pair<V, V>, List<V>> shortestPaths) {
+        Map<Pair<V, V>, int[]> shortestDistances) {
this.graph = graph;
-      this.shortestPaths = shortestPaths;
+      this.shortestDistances = shortestDistances;
}

/**
-     * Returns an iterator of all paths between two nodes, shortest first.
+     * Returns an iterator of all paths between two nodes,
+     * in non-decreasing order of path lengths.

Review comment:
Thanks a lot for your careful review.

It seems there is a minor difference between increasing and non-decreasing
order. A sequence is said to be in increasing order, if

```
a0 < a1 < ... < an
```

It is said to be in non-decreasing order, if

```
a0 <= a1 <= ... <= an
```

For paths between two nodes in a graph, it is possible that there are
multiple paths with the same length. So the sequence of path lengths should be
in non-decreasing order. What do you think

----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.