[systemds] branch master updated: [SYSTEMDS-3052] New shortestPath builtin function

[mb...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

mboehm7 pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/systemds.git


The following commit(s) were added to refs/heads/master by this push:
     new 1dc278a  [SYSTEMDS-3052] New shortestPath builtin function
1dc278a is described below

commit 1dc278ad761cec4c6c4976c829f87a5a17e81889
Author: Oleksandr Serhiienko <al...@gmail.com>
AuthorDate: Sun Jul 4 18:58:20 2021 +0200

    [SYSTEMDS-3052] New shortestPath builtin function
    
    AMLS project SS2021.
    Closes #1254.
---
 scripts/builtin/shortestPath.dml                   | 94 ++++++++++++++++++++++
 .../java/org/apache/sysds/common/Builtins.java     |  1 +
 .../functions/builtin/BuiltinShortestPathTest.java | 80 ++++++++++++++++++
 .../scripts/functions/builtin/shortestPathTest.dml | 26 ++++++
 4 files changed, 201 insertions(+)

diff --git a/scripts/builtin/shortestPath.dml b/scripts/builtin/shortestPath.dml
new file mode 100644
index 0000000..7f04799
--- /dev/null
+++ b/scripts/builtin/shortestPath.dml
@@ -0,0 +1,94 @@
+#-------------------------------------------------------------
+#
+# Licensed to the Apache Software Foundation (ASF) under one
+# or more contributor license agreements.  See the NOTICE file
+# distributed with this work for additional information
+# regarding copyright ownership.  The ASF licenses this file
+# to you under the Apache License, Version 2.0 (the
+# "License"); you may not use this file except in compliance
+# with the License.  You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing,
+# software distributed under the License is distributed on an
+# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+# KIND, either express or implied.  See the License for the
+# specific language governing permissions and limitations
+# under the License.
+#
+#-------------------------------------------------------------
+#
+# Computes the minimum distances (shortest-path) between a single 
+# source vertex and every other vertex in the graph.
+# 
+# Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bilk, 
+# James C. Dehnert, Ikkan Horn, Naty Leiser and Grzegorz Czajkowski:
+# Pregel: A System for Large-Scale Graph Processing
+#
+#------------------------------------------------------------------------------
+# NAME       TYPE      MEANING
+# G          MATRIX    adjacency matrix of the labeled graph: Such graph can be directed 
+#                      (G is symmetric) or undirected (G is not symmetric).
+#                      The values of G can be 0/1 (just specifying whether the nodes
+#                      are connected or not) or integer values (representing the weight
+#                      of the edges or the distances between nodes, 0 if not connected).
+#
+# maxi       Integer   Integer max number of iterations accepted (0 for FALSE, i.e. 
+#                      max number of iterations not defined)
+#
+# sourceNode Integer   node index to calculate the shortest paths to all other nodes.
+#
+# verbose    Boolean   flag for verbose debug output
+#------------------------------------------------------------------------------
+# C          Matrix    Output matrix (double) of minimum distances (shortest-path) between 
+#                      vertices: The value of the ith row and the jth column of the output
+#                      matrix is the minimum distance shortest-path from vertex i to vertex j.
+#                      When the value of the minimum distance is infinity, the two nodes are 
+#                      not connected.
+#------------------------------------------------------------------------------
+
+m_shortestPath = function(Matrix[Double] G, Integer maxi = 0, Integer sourceNode, Boolean verbose = FALSE) 
+  return (Matrix[Double] C) 
+{
+  if(verbose) {
+    print("SHORTEST PATH CALCULATION");
+  }
+
+  if(min(G) < 0){
+    stop("All values in G must be positive")
+  }
+
+  if(ncol(G) != nrow(G)){
+    stop("Not correct matrix dimensions")
+  }
+
+  matrixSize = nrow(G)
+
+  G = replace(target=G, pattern=0, replacement=Inf)
+
+  # initialize the matrix of minimum distances with "infinity" values:
+  minDistVector = matrix(Inf,rows=matrixSize,cols=1)
+
+  # update minimum distance from the sourceNode to itself to 0:
+  minDistVector[sourceNode,1] = 0
+
+  iter = 1
+  diff = Inf;
+  while( diff > 0 & (maxi==0 | iter<=maxi) ) {
+    w = t(colMins(G + minDistVector))
+    u = min(w, minDistVector);
+    diff = sum(u != minDistVector)
+    minDistVector = u; # update assignment
+    if( verbose ){
+      print("Shortest Path: iter = "+iter+", #diff = "+diff);
+    }
+    iter = iter + 1;
+  }
+
+  C=minDistVector
+  if(verbose) {
+    print("SHORTEST PATH CALCULATION FINISHED, CHECK OUTPUT MATRIX OF MINIMUM DISTANCES:");
+    print(toString(C))
+  }
+}
diff --git a/src/main/java/org/apache/sysds/common/Builtins.java b/src/main/java/org/apache/sysds/common/Builtins.java
index 3288a25..f6cd50f 100644
--- a/src/main/java/org/apache/sysds/common/Builtins.java
+++ b/src/main/java/org/apache/sysds/common/Builtins.java
@@ -227,6 +227,7 @@ public enum Builtins {
 	SEQ("seq", false),
 	SHERLOCK("sherlock", true),
 	SHERLOCKPREDICT("sherlockPredict", true),
+	SHORTESTPATH("shortestPath", true),
 	SIGMOID("sigmoid", true),   // 1 / (1 + exp(-X))
 	SIGN("sign", false),
 	SIN("sin", false),
diff --git a/src/test/java/org/apache/sysds/test/functions/builtin/BuiltinShortestPathTest.java b/src/test/java/org/apache/sysds/test/functions/builtin/BuiltinShortestPathTest.java
new file mode 100644
index 0000000..5d9ed2d
--- /dev/null
+++ b/src/test/java/org/apache/sysds/test/functions/builtin/BuiltinShortestPathTest.java
@@ -0,0 +1,80 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.test.functions.builtin;
+
+import java.util.HashMap;
+
+import org.junit.Test;
+
+import org.apache.sysds.runtime.matrix.data.MatrixValue;
+import org.apache.sysds.test.AutomatedTestBase;
+import org.apache.sysds.test.TestConfiguration;
+import org.apache.sysds.test.TestUtils;
+
+public class BuiltinShortestPathTest extends AutomatedTestBase {
+	private final static String TEST_NAME = "shortestPathTest";
+	private final static String TEST_DIR = "functions/builtin/";
+	private static final String TEST_CLASS_DIR = TEST_DIR + BuiltinShortestPathTest.class.getSimpleName() + "/";
+	private final static double eps = 1e-10;
+	
+	@Override
+	public void setUp() {
+		TestUtils.clearAssertionInformation();
+		addTestConfiguration(TEST_NAME,new TestConfiguration(TEST_CLASS_DIR, TEST_NAME,new String[]{"r"}));
+	}
+
+	@Test
+	public void testShortestPathNode1CP() {
+		runShortestPathNodeTest(1, new double[][] {{0}, {2}, {5}, {5}});
+	}
+	
+	@Test
+	public void testShortestPathNode2CP() {
+		runShortestPathNodeTest(2, new double[][] {{1}, {0}, {4}, {5}});
+	}
+	
+	@Test
+	public void testShortestPathNode3CP() {
+		runShortestPathNodeTest(3, new double[][] {{4}, {3}, {0}, {1}});
+	}
+	
+	
+
+	private void runShortestPathNodeTest(int node, double [][] Res) {
+		loadTestConfiguration(getTestConfiguration(TEST_NAME));
+	
+		String HOME = SCRIPT_DIR + TEST_DIR;
+		fullDMLScriptName = HOME + TEST_NAME + ".dml";
+		programArgs = new String[]{ "-args",
+			input("X"), String.valueOf(node), output("R")};
+	
+		double[][] X = {{0, 2, 5, 5 }, 
+						{1, 0, 4, 10}, 
+						{0, 3, 0, 1 },
+						{3, 2, 0, 0 }};
+		writeInputMatrixWithMTD("X", X, true);
+	
+		runTest(true, false, null, -1);
+	
+		HashMap<MatrixValue.CellIndex, Double> dmlfile = readDMLMatrixFromOutputDir("R");
+		double[][] Y = TestUtils.convertHashMapToDoubleArray(dmlfile);
+		TestUtils.compareMatrices(Res, Y, eps);
+	}
+}
diff --git a/src/test/scripts/functions/builtin/shortestPathTest.dml b/src/test/scripts/functions/builtin/shortestPathTest.dml
new file mode 100644
index 0000000..3e5454b
--- /dev/null
+++ b/src/test/scripts/functions/builtin/shortestPathTest.dml
@@ -0,0 +1,26 @@
+
+#-------------------------------------------------------------
+#
+# Licensed to the Apache Software Foundation (ASF) under one
+# or more contributor license agreements.  See the NOTICE file
+# distributed with this work for additional information
+# regarding copyright ownership.  The ASF licenses this file
+# to you under the Apache License, Version 2.0 (the
+# "License"); you may not use this file except in compliance
+# with the License.  You may obtain a copy of the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing,
+# software distributed under the License is distributed on an
+# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+# KIND, either express or implied.  See the License for the
+# specific language governing permissions and limitations
+# under the License.
+#
+#-------------------------------------------------------------
+
+X = read($1)
+C = shortestPath(G=X,sourceNode = $2)
+
+write(C, $3)