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

2020-06-27 Thread GitBox


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 {
 private final DefaultDirectedGraph graph;
-private final Map, List> shortestPaths;
+private final Map, int[]> shortestDistances;
 
 /** Creates a frozen graph as a copy of another graph. */
 FrozenGraph(DefaultDirectedGraph graph,
-Map, List> shortestPaths) {
+Map, 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.

For queries about this service, please contact Infrastructure at:
us...@infra.apache.org




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

2020-06-27 Thread GitBox


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



##
File path: 
core/src/test/java/org/apache/calcite/util/graph/DirectedGraphTest.java
##
@@ -64,14 +64,21 @@
 g.addEdge("B", "D");
 assertEquals("[A, B, D]", shortestPath(g, "A", "D").toString());
 assertNull(shortestPath(g, "A", "E"), "There is no path from A to E");
-assertEquals("[]", shortestPath(g, "D", "D").toString());
+assertEquals("[D, C, D]", shortestPath(g, "D", "D").toString());

Review comment:
   Sounds reasonable. I have revised the code to include the empty path to 
itself.
   
   BTW, the empty path from node D to itself should be denoted "[D]"? as it 
helps to maintain the relation:
   
   pathLength == path.size() - 1





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.

For queries about this service, please contact Infrastructure at:
us...@infra.apache.org




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

2020-06-18 Thread GitBox


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



##
File path: 
core/src/test/java/org/apache/calcite/util/graph/DirectedGraphTest.java
##
@@ -66,7 +66,7 @@
 assertNull(shortestPath(g, "A", "E"), "There is no path from A to E");
 assertEquals("[]", shortestPath(g, "D", "D").toString());
 assertNull(shortestPath(g, "X", "A"), "Node X is not in the graph");
-assertEquals("[[A, B, C, D], [A, B, D]]", paths(g, "A", "D").toString());
+assertEquals("[[A, B, D], [A, B, C, D]]", paths(g, "A", "D").toString());

Review comment:
   We have DirectedGraphTest#testDistance





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.

For queries about this service, please contact Infrastructure at:
us...@infra.apache.org




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

2020-06-18 Thread GitBox


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



##
File path: core/src/main/java/org/apache/calcite/util/graph/Graphs.java
##
@@ -134,7 +135,44 @@ public int size() {
   if (from.equals(to)) {

Review comment:
   Removed. Maybe we can add it back some time in the future, if we find a 
requirement for it. 





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.

For queries about this service, please contact Infrastructure at:
us...@infra.apache.org




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

2020-06-18 Thread GitBox


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



##
File path: core/src/main/java/org/apache/calcite/plan/ConventionTraitDef.java
##
@@ -234,10 +234,10 @@ private ConversionData getConversionData(RelOptPlanner 
planner) {
   return pathMap;
 }
 
-public List getShortestPath(
+public int getShortestDistance(

Review comment:
   @xndai I have revised the getPaths() method accordingly. Thank you.
   
   @rubenada Thanks a lot for your suggestion. I tend to agree with @xndai. If 
getting shortest paths is not a frequently used operation, there is no need to 
store all pairs of shortest paths. Here, we preserve the getShortestPath API, 
mainly for the sake of backward compatibility. 





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.

For queries about this service, please contact Infrastructure at:
us...@infra.apache.org




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

2020-06-17 Thread GitBox


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



##
File path: core/src/main/java/org/apache/calcite/util/graph/Graphs.java
##
@@ -56,42 +54,40 @@ public int size() {
   public static  FrozenGraph makeImmutable(
   DirectedGraph graph) {
 DefaultDirectedGraph graph1 = (DefaultDirectedGraph) graph;
-Map, List> shortestPaths = new HashMap<>();
+Map, int[]> shortestDistances = new HashMap<>();
 for (DefaultDirectedGraph.VertexInfo arc
 : graph1.vertexMap.values()) {
   for (E edge : arc.outEdges) {
 final V source = graph1.source(edge);
 final V target = graph1.target(edge);
-shortestPaths.put(Pair.of(source, target),
-ImmutableList.of(source, target));
+shortestDistances.put(Pair.of(source, target), new int[] {1});
   }
 }
 while (true) {
   // Take a copy of the map's keys to avoid
   // ConcurrentModificationExceptions.
   final List> previous =
-  ImmutableList.copyOf(shortestPaths.keySet());
-  int changeCount = 0;
+  ImmutableList.copyOf(shortestDistances.keySet());
+  boolean changeCount = false;

Review comment:
   Revised. Thanks for your kind reminder. 





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.

For queries about this service, please contact Infrastructure at:
us...@infra.apache.org




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

2020-06-17 Thread GitBox


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



##
File path: core/src/main/java/org/apache/calcite/plan/ConventionTraitDef.java
##
@@ -234,10 +234,10 @@ private ConversionData getConversionData(RelOptPlanner 
planner) {
   return pathMap;
 }
 
-public List getShortestPath(
+public int getShortestDistance(

Review comment:
   IMO, it would be an overkill to call getPaths() only to get the shortest 
path. 
   To support this scenario, I have restored the getShortestPath API, and 
implement it with BFS. It should be more efficient than the Dijkstra and Floyd 
algorihtms. 





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.

For queries about this service, please contact Infrastructure at:
us...@infra.apache.org