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 9d5b898 [SYSTEMDS-2591] Builtin hospitalResidencyMatch for Stable
matching Closes #1312.
9d5b898 is described below
commit 9d5b898b4e4b94a685f239d513c55c23eaa0a4ef
Author: Atefeh Asayesh <[email protected]>
AuthorDate: Sat Jun 19 23:17:52 2021 +0200
[SYSTEMDS-2591] Builtin hospitalResidencyMatch for Stable matching
Closes #1312.
---
scripts/builtin/hospitalResidencyMatch.dml | 181 +++++++++++++++++++++
.../java/org/apache/sysds/common/Builtins.java | 1 +
.../builtin/BuiltinHospitalResidencyMatchTest.java | 133 +++++++++++++++
.../scripts/functions/builtin/residencymatch.dml | 28 ++++
4 files changed, 343 insertions(+)
diff --git a/scripts/builtin/hospitalResidencyMatch.dml
b/scripts/builtin/hospitalResidencyMatch.dml
new file mode 100644
index 0000000..94eb931
--- /dev/null
+++ b/scripts/builtin/hospitalResidencyMatch.dml
@@ -0,0 +1,181 @@
+#-------------------------------------------------------------
+## 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 HOSPITAL RESIDENCY MATCH PROBLEM
+#
+# INPUT PARAMETERS:
+#
--------------------------------------------------------------------------------------------
+# NAME TYPE DEFAULT MEANING
+#
--------------------------------------------------------------------------------------------
+# R Matrix --- Residents matrix R.
+# It must be an ORDERED matrix.
+#
+# H Matrix --- Hospitals matrix H.
+# It must be an UNORDRED matrix.
+#
+# capacity Matrix --- capacity of Hospitals matrix C.
+# It must be a [n*1] matrix with
non zero values.
+# 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
+#
--------------------------------------------------------------------------------------------
+# residencyMatch Matrix --- Result Matrix
+# If cell [i,j] is non-zero, it
means that Resident i has matched with Hospital j.
+# Further, if cell [i,j] is
non-zero, it holds the preference value that led to the match.
+#
+#
+# hospitalMatch Matrix --- Result Matrix
+# If cell [i,j] is non-zero, it
means that Resident i has matched with Hospital j.
+# Further, if cell [i,j] is
non-zero, it holds the preference value that led to the match.
+#
+#
+# Residents.mtx:
+# 2.0,1.0,3.0
+# 1.0,2.0,3.0
+# 1.0,2.0,0.0
+#
+# Since it is an ORDERED matrix, this means that Resident 1 (row 1) likes
hospital 2 the most, followed by hospital 1 and hospital 3.
+# If it was UNORDERED, this would mean that resident 1 (row 1) likes hospital
3 the most (since the value at [1,3] is the row max),
+# followed by hospital 1 (2.0 preference value) and hospital 2 (1.0 preference
value).
+#
+# Hospitals.mtx:
+# 2.0,1.0,0.0
+# 0.0,1.0,2.0
+# 1.0,2.0,0.0
+#
+# Since it is an UNORDERED matrix this means that Hospital 1 (row 1) likes
Resident 1 the most (since the value at [1,1] is the row max).
+#
+# capacity.mtx
+# 1.0
+# 1.0
+# 1.0
+#
+# residencyMatch.mtx
+# 2.0,0.0,0.0
+# 1.0,0.0,0.0
+# 0.0,2.0,0.0
+#
+
+
+# hospitalMatch.mtx
+# 0.0,1.0,0.0
+# 0.0,0.0,2.0
+# 1.0,0.0,0.0
+#
+# Resident 1 has matched with Hospital 3 (since [1,3] is non-zero) at a
preference level of 2.0.
+# Resident 2 has matched with Hospital 1 (since [2,1] is non-zero) at a
preference level of 1.0.
+# Resident 3 has matched with Hospital 2 (since [3,2] is non-zero) at a
preference level of 2.0.
+#
--------------------------------------------------------------------------------------------
+
+m_hospitalResidencyMatch = function(Matrix[Double] R, Matrix[Double] H,
Matrix[Double] capacity, Boolean verbose = FALSE)
+ return (Matrix[Double] residencyMatch, Matrix[Double] hospitalMatch)
+{
+
+ # in this step we consider that Residents Matrix is ORDERED.
+ # in this step we consider that Hospital Matrix is UNORDERED.
+ # in the next implementation can consider number of choices for every
resident.
+
+ #TODO set a finite number of maximum iterations so that the execution
terminates after maximum iterations.
+
+ print("STARTING RESIDENCY MATCH ALGORITHM");
+ print("READING R as residents AND H as Hospitals and capacity...");
+
+ m = nrow(R)
+ n = ncol(R)
+
+ residencyMatch = matrix(0.0, rows=m, cols=n)
+ hospitalMatch = matrix(0.0, rows=n, cols=m)
+ resultmMatrix = matrix(0.0, rows=nrow(R), cols=ncol(R))
+
+ if(nrow(capacity) != nrow(H))
+ print("ERROR: Missing capacity info for some hospitals")
+
+
+ startM = matrix(1.0, rows=m, cols=1) ### for checking while
+
+ hIndex =matrix(1.0, rows=m, cols=1)
+ proposer_pointers = matrix(1.0, rows=m, cols=1)
+ prev_Residents_vector = matrix(1.0, rows=n, cols=1)
+ prevIndex_Residents_vector = matrix(1.0, rows=n, cols=1)
+
+ prev_Residents_vector = rowMins(hospitalMatch)
+ prevIndex_Residents_vector = rowIndexMin(hospitalMatch)
+ # TODO remove the nested looping by vectorizing
+ while(sum(startM) > 0) {
+ for(i in 1:m) {
+ if(as.scalar(startM[i]) == 1) {
+ secondIndex = as.scalar (proposer_pointers[i])
+ hIndex[i] = as.scalar (R[i,secondIndex])
+ #the minimum value means most preference.
+ prev_Residents_vector = rowMaxs(hospitalMatch)
+ prevIndex_Residents_vector = rowIndexMax(hospitalMatch)
+ if (as.scalar(hIndex[i]) != 0) {
+ hosValue = as.scalar (H[as.scalar(hIndex[i]),i])
+ if (hosValue > 0) {
+ # if this hospital likes this resident and has the capacity ...
+ if(as.scalar(capacity[as.scalar (hIndex[i]),1]) >= 1) {
+ capacity[as.scalar(hIndex[i]),1] = as.scalar(capacity[as.scalar
(hIndex[i]),1]) - 1
+ residencyMatch [i,as.scalar(hIndex[i])] =
as.scalar(proposer_pointers[i])
+ hospitalMatch [as.scalar(hIndex[i]), i] = hosValue
+ #Disable freshly Matched resident to search for a new Hospital
in the next round
+ startM[i] = 0
+ proposer_pointers[i] = as.scalar(proposer_pointers[i]) + 1
+ if (as.scalar(proposer_pointers[i]) > n)
+ proposer_pointers[i] = n
+ }
+ else if(as.scalar(prev_Residents_vector[as.scalar(hIndex[i])]) >=
secondIndex) {
+ #in this step we check that if the hospital capacity is 0
+ # but the preference value of prev residents is lower than
+ #the preference value of current resident.
+ # we should replace the prev resident with current resident.
+ resPrev= as.scalar(prevIndex_Residents_vector[as.scalar
(hIndex[i]),1])
+ hospitalMatch [as.scalar(hIndex[i]) ,resPrev] = 0
+ residencyMatch[resPrev,as.scalar(hIndex[i])] = 0
+ hospitalMatch [as.scalar(hIndex[i]),i ] =
as.scalar(proposer_pointers[i])
+ residencyMatch [i,as.scalar(hIndex[i])] =
as.scalar(proposer_pointers[i])
+ startM[i] = 0
+ prevResIndex
=as.scalar(prevIndex_Residents_vector[as.scalar(hIndex[i]),1])
+ if(prevResIndex > 0){
+ startM[prevResIndex ] =1
+ proposer_pointers[i] = as.scalar(proposer_pointers[i]) + 1
+ if (as.scalar(proposer_pointers[i]) > n)
+ proposer_pointers[i] = n
+ }
+ }
+ }
+ if ( as.scalar (startM[i]) == 1 ) {
+ proposer_pointers[i] = as.scalar(proposer_pointers[i]) + 1
+ if (as.scalar(proposer_pointers[i]) > n)
+ proposer_pointers[i] = n
+ }
+ }
+ }
+ }
+ }
+ if(verbose) {
+ print("residencyMatch")
+ print(toString(residencyMatch))
+ print("hospitalMatch")
+ print(toString(hospitalMatch))
+ }
+}
+
+
diff --git a/src/main/java/org/apache/sysds/common/Builtins.java
b/src/main/java/org/apache/sysds/common/Builtins.java
index be3647b..99acfaf 100644
--- a/src/main/java/org/apache/sysds/common/Builtins.java
+++ b/src/main/java/org/apache/sysds/common/Builtins.java
@@ -129,6 +129,7 @@ public enum Builtins {
GMM_PREDICT("gmmPredict", true),
GNMF("gnmf", true),
GRID_SEARCH("gridSearch", true),
+ HOSPITAL_RESIDENCY_MATCH("hospitalResidencyMatch", true),
HYPERBAND("hyperband", true),
IFELSE("ifelse", false),
IMG_MIRROR("img_mirror", true),
diff --git
a/src/test/java/org/apache/sysds/test/functions/builtin/BuiltinHospitalResidencyMatchTest.java
b/src/test/java/org/apache/sysds/test/functions/builtin/BuiltinHospitalResidencyMatchTest.java
new file mode 100644
index 0000000..91cc38f
--- /dev/null
+++
b/src/test/java/org/apache/sysds/test/functions/builtin/BuiltinHospitalResidencyMatchTest.java
@@ -0,0 +1,133 @@
+/*
+ * 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.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 BuiltinHospitalResidencyMatchTest extends AutomatedTestBase {
+
+
+ private final static String TEST_NAME = "residencymatch";
+ private final static String TEST_DIR = "functions/builtin/";
+ private static final String TEST_CLASS_DIR = TEST_DIR +
BuiltinHospitalResidencyMatchTest.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[]{"RM"}));
+ }
+
+ @Test
+ public void testResidencyMatch1() {
+ double[][] R = {
+ {2,3,1},{1,3,2},{3,1,3}};
+ double[][] H = {
+ {1,2,0},{3,1,2},{0,1,2}};
+ double[][] C = {
+ {2},{3},{2}};
+ double[][]EM = { // this is an expected matrix
+ {0,1,0},{1,0,0},{0,0,1}};
+ runtestResidencyMatchTest(R, H, C, EM, Types.ExecType.CP);
+ }
+
+ @Test
+ public void testResidencyMatch2() {
+ double[][] R = {
+ {2,1,3},{1,2,3},{1,3,2}};
+ double[][] H = {
+ {3,1,2},{2,1,3},{3,2,1}};
+ double[][] C = {
+ {1},{1},{1}};
+ double[][]EM = { // this is an expected matrix
+ {0,0,3},{0,2,0},{1,0,0}};
+ runtestResidencyMatchTest(R, H, C, EM, Types.ExecType.CP);
+ }
+
+ @Test
+ public void testResidencyMatch3() {
+ double[][] R = {
+ {1,2},{2,1},{1,2},{1,2}};
+ double[][] H = {
+ {3,2,1,4},{2,1,3,0}};
+ double[][] C = {
+ {4},{3}};
+ double[][]EM = { // this is an expected matrix
+ {1,0},{0,1},{1,0},{1,0}};
+ runtestResidencyMatchTest(R, H, C, EM, Types.ExecType.CP);
+ }
+ @Test
+ public void testResidencyMatch4() {
+ double[][] R = {
+ {1,2},{2,1},{1,2},{1,2}};
+ double[][] H = {
+ {3,2,1,4},{2,1,3,0}};
+ double[][] C = {
+ {4},{3}};
+ double[][]EM = { // this is an expected matrix
+ {1,0},{0,1},{1,0},{1,0}};
+ runtestResidencyMatchTest(R, H, C, EM, Types.ExecType.SPARK);
+ }
+
+ private void runtestResidencyMatchTest(double[][] R, double[][] H,
double[][] C, double[][] EM,
+ Types.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("R"));
+ proArgs.add(input("H"));
+ proArgs.add(input("C"));
+ proArgs.add(output("RM"));
+
+ programArgs = proArgs.toArray(new
String[proArgs.size()]);
+ // defining Residents Matrix
+
+ writeInputMatrixWithMTD("R", R, true);
+ writeInputMatrixWithMTD("H", H, true);
+ writeInputMatrixWithMTD("C", C, true);
+
+
+ runTest(true, EXCEPTION_NOT_EXPECTED, null, -1);
+
+ //compare expected results
+ HashMap<MatrixValue.CellIndex, Double> matrixU =
readDMLMatrixFromOutputDir("RM");
+ double[][] OUT =
TestUtils.convertHashMapToDoubleArray(matrixU);
+ TestUtils.compareMatrices(EM, OUT, eps);
+ }
+ finally {
+ rtplatform = platformOld;
+ }
+ }
+}
+
diff --git a/src/test/scripts/functions/builtin/residencymatch.dml
b/src/test/scripts/functions/builtin/residencymatch.dml
new file mode 100644
index 0000000..d5a2090
--- /dev/null
+++ b/src/test/scripts/functions/builtin/residencymatch.dml
@@ -0,0 +1,28 @@
+#-------------------------------------------------------------
+#
+# 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.
+#
+#-------------------------------------------------------------
+
+R = read($1)
+H = read($2)
+C = read($3)
+[R, H] = hospitalResidencyMatch(R=R,H=H,capacity=C, verbose = TRUE)
+write(R, $4)
+
+
