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

2020-06-25 Thread GitBox


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



##
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:
   +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] xndai commented on a change in pull request #2027: [CALCITE-4049] Improve the implementation of the shortest-path algorithm

2020-06-18 Thread GitBox


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



##
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:
   where are the tests for getShortestDistance()?

##
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:
   I think we can just remove this method. Nobody is using it anymore.





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] xndai commented on a change in pull request #2027: [CALCITE-4049] Improve the implementation of the shortest-path algorithm

2020-06-17 Thread GitBox


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



##
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:
   @liyafan82 I am not saying getPaths() to return shortest paths. What I 
mean is you should put shortest path at the front of list, so during convert() 
we always choose the shortest converted path if possible. This only requires a 
sort after generating all possible path.
   
   @rubenada I don't think we need to cache shortest path. This is only one 
time used and there's no benefit to cache 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] xndai commented on a change in pull request #2027: [CALCITE-4049] Improve the implementation of the shortest-path algorithm

2020-06-16 Thread GitBox


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



##
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:
   Can you also fix the getPaths() to return shortest paths first? This is 
to make sure we choose the shortest path during convert.





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