You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@systemds.apache.org by ss...@apache.org on 2021/05/19 13:06:10 UTC
[systemds] branch master updated: [SYSTEMDS-2976] Builtin for
Stable Marriage Algorithm Closes #1279.
This is an automated email from the ASF dual-hosted git repository.
ssiddiqi 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 2ae0f81 [SYSTEMDS-2976] Builtin for Stable Marriage Algorithm Closes #1279.
2ae0f81 is described below
commit 2ae0f818d9fc5092408df6ff3fe75539a5117e40
Author: Atefeh Asayesh <at...@tugraz.at>
AuthorDate: Wed May 19 11:06:26 2021 +0200
[SYSTEMDS-2976] Builtin for Stable Marriage Algorithm
Closes #1279.
---
scripts/builtin/stableMarriage.dml | 154 +++++++++++++++++++++
.../java/org/apache/sysds/common/Builtins.java | 5 +-
.../builtin/BuiltinStableMarriageTest.java | 119 ++++++++++++++++
.../scripts/functions/builtin/stablemarriage.dml | 27 ++++
4 files changed, 303 insertions(+), 2 deletions(-)
diff --git a/scripts/builtin/stableMarriage.dml b/scripts/builtin/stableMarriage.dml
new file mode 100644
index 0000000..e6293cd
--- /dev/null
+++ b/scripts/builtin/stableMarriage.dml
@@ -0,0 +1,154 @@
+#-------------------------------------------------------------
+## 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.
+#
+#-------------------------------------------------------------
+# THIS SCRIPT COMPUTES A SOLUTION FOR THE STABLE MARRIAGE PROBLEM
+#
+# INPUT PARAMETERS:
+# --------------------------------------------------------------------------------------------
+# NAME TYPE DEFAULT MEANING
+# --------------------------------------------------------------------------------------------
+# P Matrix --- proposer matrix P.
+# It must be a square matrix with no zeros.
+#
+# A Matrix --- acceptor matrix A.
+# It must be a square matrix with no zeros.
+#
+# ordered Boolean TRUE If true, P and A are assumed to be ordered,
+# i.e. the leftmost value in a row is the most preferred partner's index.
+# i.e. the leftmost value in a row in P is the preference value for the acceptor with
+# index 1 and vice-versa (higher is better).
+# OUTPUT PARAMETERS:
+# --------------------------------------------------------------------------------------------
+# NAME TYPE DEFAULT MEANING
+# --------------------------------------------------------------------------------------------
+#result_matrix Matrix --- Result Matrix
+# If cell [i,j] is non-zero, it means that acceptor i has matched with proposer j.
+# Further, if cell [i,j] is non-zero, it holds the preference value that led to the match.
+#
+#
+# Proposers.mtx:
+# 2.0,1.0,3.0
+# 1.0,2.0,3.0
+# 1.0,3.0,2.0
+#
+# Since ordered=TRUE, this means that proposer 1 (row 1) likes acceptor 2 the most, followed by acceptor 1 and acceptor 3.
+# If ordered=FALSE, this would mean that proposer 1 (row 1) likes acceptor 3 the most (since the value at [1,3] is the row max),
+# followed by acceptor 1 (2.0 preference value) and acceptor 2 (1.0 preference value).
+#
+# Acceptors.mtx:
+# 3.0,1.0,2.0
+# 2.0,1.0,3.0
+# 3.0,2.0,1.0
+#
+# Since ordered=TRUE, this means that acceptor 1 (row 1) likes proposer 3 the most, followed by proposer 1 and proposer 2.
+# If ordered=FALSE, this would mean that acceptor 1 (row 1) likes proposer 1 the most (since the value at [1,1] is the row max),
+# followed by proposer 3 (2.0 preference value) and proposer 2 (1.0 preference value).
+#
+# Output.mtx (assuming ordered=TRUE):
+# 0.0,0.0,3.0
+# 0.0,3.0,0.0
+# 1.0,0.0,0.0
+#
+# Acceptor 1 has matched with proposer 3 (since [1,3] is non-zero) at a preference level of 3.0.
+# Acceptor 2 has matched with proposer 2 (since [2,2] is non-zero) at a preference level of 3.0.
+# Acceptor 3 has matched with proposer 1 (since [3,1] is non-zero) at a preference level of 1.0.
+# --------------------------------------------------------------------------------------------
+
+m_stableMarriage = function(Matrix[Double] P, Matrix[Double] A, Boolean ordered = TRUE, Boolean verbose = FALSE)
+ return (Matrix[Double] result_matrix)
+{
+ # variable names follow publication
+
+ print("STARTING STABLE MARRIAGE");
+ assert(nrow(A) == nrow(P));
+ assert(ncol(A) == ncol(P));
+
+ if(nrow(P) != ncol(P) | nrow(A) != ncol(A))
+ stop("StableMarriage error: Wrong Input! Both P and A must be square.")
+
+ n = nrow(P)
+ # Let S be the identity matrix
+ S = diag(matrix(1.0, rows=n, cols=1))
+ result_matrix = matrix(0.0, rows=n, cols=n)
+ # Pre-processing
+ if(!ordered) {
+ # If unordered, we need to order P
+ ordered_P = matrix(0.0, rows=n, cols=n)
+ transposed_P = t(P)
+
+ parfor(i in 1:n)
+ ordered_P[,i] = order(target=transposed_P, by=i, decreasing=TRUE, index.return=TRUE)
+ P = t(ordered_P)
+ }
+ else {
+ # If ordered, we need to unorder A
+ unordered_A = matrix(0.0, rows=n, cols=n)
+ # Since cells can be converted to unordered indices independently, we can nest parfor loops.
+ parfor(i in 1:n) {
+ parfor(j in 1:n, check=0)
+ unordered_A[i, as.scalar(A[i, j])] = n - j + 1
+ }
+ A = unordered_A
+ }
+
+ proposer_pointers = matrix(1.0, rows=n, cols=1)
+
+ while(sum(S) > 0) {
+ stripped_preferences = S %*% P
+ mask_matrix = matrix(0.0, rows=n, cols=n)
+ for(i in 1:n) {
+ max_proposal = as.scalar(stripped_preferences[i, as.scalar(proposer_pointers[i])])
+ if(max_proposal != 0) {
+ proposer_pointers[i] = as.scalar(proposer_pointers[i]) + 1
+ mask_matrix[max_proposal, i] = 1
+ }
+ }
+ # make Hadamard Product
+ Propose_round_results = mask_matrix * A
+ best_proposers_vector = rowIndexMax(Propose_round_results)
+ prev_best_proposers = rowIndexMax(result_matrix)
+
+ for(i in 1:n, check=0) {
+ new_best_proposer_index = as.scalar(best_proposers_vector[i])
+ new_best = as.scalar(Propose_round_results[i, new_best_proposer_index])
+
+ if(new_best > 0) {
+ prev_best_proposer_index = as.scalar(prev_best_proposers[i])
+ prev_best = as.scalar(result_matrix[i, prev_best_proposer_index])
+
+ if (new_best > prev_best)
+ {
+ # Proposal is better than current fiance
+ result_matrix[i, prev_best_proposer_index] = 0
+ result_matrix[i, new_best_proposer_index] = new_best
+
+ #Disable freshly married man to search for a new woman in the next round
+ S[new_best_proposer_index, new_best_proposer_index] = 0
+
+ # If a fiance existed, dump him/her
+ if(prev_best > 0)
+ S[prev_best_proposer_index, prev_best_proposer_index] = 1
+ }
+ }
+ }
+ }
+
+ if(verbose)
+ print("Result: \n"+toString(result_matrix))
+}
\ No newline at end of file
diff --git a/src/main/java/org/apache/sysds/common/Builtins.java b/src/main/java/org/apache/sysds/common/Builtins.java
index 27a0d73..00bd95d 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 {
SOLVE("solve", false),
SPLIT("split", true),
SPLIT_BALANCED("splitBalanced", true),
+ STABLE_MARRIAGE("stableMarriage", true),
STATSNA("statsNA", true),
SQRT("sqrt", false),
SUM("sum", false),
@@ -377,6 +378,6 @@ public enum Builtins {
public static String getInternalFName(String name, DataType dt) {
return !contains(name, true, false) ? name : // private builtin
- (dt.isMatrix() ? "m_" : "s_") + name; // public builtin
+ (dt.isMatrix() ? "m_" : "s_") + name; // public builtin
}
-}
+}
\ No newline at end of file
diff --git a/src/test/java/org/apache/sysds/test/functions/builtin/BuiltinStableMarriageTest.java b/src/test/java/org/apache/sysds/test/functions/builtin/BuiltinStableMarriageTest.java
new file mode 100644
index 0000000..f8ed8a4
--- /dev/null
+++ b/src/test/java/org/apache/sysds/test/functions/builtin/BuiltinStableMarriageTest.java
@@ -0,0 +1,119 @@
+/*
+ * 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 org.apache.sysds.common.Types;
+import org.apache.sysds.lops.LopProperties.ExecType;
+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;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+
+public class BuiltinStableMarriageTest extends AutomatedTestBase {
+
+
+ private final static String TEST_NAME = "stablemarriage";
+ private final static String TEST_DIR = "functions/builtin/";
+ private static final String TEST_CLASS_DIR = TEST_DIR + BuiltinStableMarriageTest.class.getSimpleName() + "/";
+
+ private final static double eps = 0.0001;
+
+
+
+ @Override
+ public void setUp() {
+ addTestConfiguration(TEST_NAME,new TestConfiguration(TEST_CLASS_DIR, TEST_NAME,new String[]{"SM"}));
+ }
+
+ @Test
+ public void testStableMarriage1() {
+ double[][] P = {{2, 1, 3}, {1, 2, 3}, {1, 3, 2}};
+ double[][] A = {{3, 1, 2}, {2, 1, 3}, {3, 2, 1}};
+ // this is an expected matrix
+ double[][] EM = { {0, 0, 3}, {0, 3, 0}, {1, 0, 0}};
+ runtestStableMarriage(P, A, EM, "TRUE", ExecType.CP);
+ }
+
+ @Test
+ public void testStableMarriage2() {
+ double[][] P = {{4, 3, 2, 1}, {2, 4, 3, 1}, {1, 4, 3, 2}, {4, 1, 2, 3}};
+ double[][] A = {{2, 3, 4, 1}, {2, 3, 4, 1}, {4, 3, 1, 2}, {2, 1, 4, 3}};
+ // this is an expected matrix
+ double[][] EM = {{0, 0, 3, 0}, {0, 4, 0, 0}, {0, 0, 0, 4}, {3, 0, 0, 0}};
+ runtestStableMarriage(P, A, EM, "TRUE", ExecType.CP);
+ }
+
+ @Test
+ public void testStableMarriage3() {
+ double[][] P = {{4, 3, 2, 1}, {2, 4, 3, 1}, {1, 4, 3, 2}, {4, 1, 2, 3}};
+ double[][] A = {{2, 3, 4, 1}, {2, 3, 4, 1}, {4, 3, 1, 2}, {2, 1, 4, 3}};
+ // this is an expected matrix
+ double[][] EM = {{2, 0, 0, 0}, {0, 0, 4, 0}, {0, 3, 0, 0}, {0, 0, 0, 3}};
+ runtestStableMarriage(P, A, EM, "FALSE", ExecType.CP);
+ }
+
+
+ @Test
+ public void testStableMarriageSP() {
+ double[][] P = {{4, 3, 2, 1}, {2, 4, 3, 1}, {1, 4, 3, 2}, {4, 1, 2, 3}};
+ double[][] A = {{2, 3, 4, 1}, {2, 3, 4, 1}, {4, 3, 1, 2}, {2, 1, 4, 3}};
+ // this is an expected matrix
+ double[][] EM = {{0, 0, 3, 0}, {0, 4, 0, 0}, {0, 0, 0, 4}, {3, 0, 0, 0}};
+ runtestStableMarriage(P, A, EM, "TRUE", ExecType.SPARK);
+ }
+
+
+ private void runtestStableMarriage(double[][] P, double[][] A, double[][] EM, String ordered, ExecType instType) {
+ Types.ExecMode platformOld = setExecMode(instType);
+
+ try
+ {
+ loadTestConfiguration(getTestConfiguration(TEST_NAME));
+ String HOME = SCRIPT_DIR + TEST_DIR;
+ fullDMLScriptName = HOME + TEST_NAME + ".dml";
+ List<String> proArgs = new ArrayList<>();
+ proArgs.add("-args");
+ proArgs.add(input("P"));
+ proArgs.add(input("A"));
+ proArgs.add(ordered);
+ proArgs.add(output("SM"));
+
+ programArgs = proArgs.toArray(new String[0]);
+
+ writeInputMatrixWithMTD("P", P, true);
+ writeInputMatrixWithMTD("A", A, true);
+
+ runTest(true, EXCEPTION_NOT_EXPECTED, null, -1);
+
+ //compare expected results
+ HashMap<MatrixValue.CellIndex, Double> matrixU = readDMLMatrixFromOutputDir("SM");
+ double[][] OUT = TestUtils.convertHashMapToDoubleArray(matrixU);
+ TestUtils.compareMatrices(EM, OUT, eps);
+ }
+ finally {
+ rtplatform = platformOld;
+ }
+ }
+}
diff --git a/src/test/scripts/functions/builtin/stablemarriage.dml b/src/test/scripts/functions/builtin/stablemarriage.dml
new file mode 100644
index 0000000..c8d50b2
--- /dev/null
+++ b/src/test/scripts/functions/builtin/stablemarriage.dml
@@ -0,0 +1,27 @@
+#-------------------------------------------------------------
+#
+# 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.
+#
+#-------------------------------------------------------------
+
+# this dml file will call the stableMarriage built-in functions inside scripts/builtin
+P = read($1)
+A = read($2)
+ordered = as.logical($3)
+output = stableMarriage(P = P, A = A, ordered = ordered, verbose = TRUE)
+write(output, $4)
\ No newline at end of file