Main Page | Namespace List | Class List | File List | Namespace Members | Class Members | Related Pages | Examples

marriage.py

This example solves the stable marriages problem.

marriage.py men marriage.py women

This example solves the stable marriages problem. A classic distributed computing problem involves a group of men and a group of women. Each person has an ordered list ranking each member of the opposite sex in the order they want to marry them. A stable marriage is one where there are no pairs of the form {wi, mj} {wk, mt} where wi prefers mt to mj and mt prefers wi to wk.

This example is based on the example in A Principled Semantics for inp by Jacob & Wood 2000. The main code is in the Men and Women functions. The rest of the code is just to fork a seperate process for each person in the simulation.

The code itself is very simple, and relies mostly on the fact that when deadlock is reached the algorithm has finished. The inp calls detect the deadlock and cause the processes to exit.

#!/usr/bin/python # Copyright 2004 Andrew Wilkinson <aw@cs.york.ac.uk>. # # This file is part of PyLinda (http://www-users.cs.york.ac.uk/~aw/pylinda) # # PyLinda is free software; you can redistribute it and/or modify # it under the terms of the GNU Lesser General Public License as published by # the Free Software Foundation; either version 2.1 of the License, or # (at your option) any later version. # # PyLinda is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU Lesser General Public License for more details. # # You should have received a copy of the GNU Lesser General Public License # along with PyLinda; if not, write to the Free Software # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA import linda import sys import random import os # # Process command line options # from optparse import OptionParser parser = OptionParser(version="%prog 1.0") parser.add_option("-p", "--connect-port", type="int", dest="connectport", default=2102, help="The port to connect to.") (options, args) = parser.parse_args() linda.connect(options.connectport) # # # # Lists of men's and women's names men = ["AIDAN", "JADEN", "CADEN", "ETHAN", "CALEB", "DYLAN", "JACOB", "JORDAN", "LOGAN", "HAYDEN", "CONNOR", "RYAN", "MORGAN", "CAMERON", "ANDREW", "JOSHUA", "NOAH", "MATTHEW", "ADDISON", "ASHTON"] women = ["MADISON", "EMMA", "ABIGAIL", "RILEY", "CHLOE", "HANNAH", "ALEXIS", "ISABELLA", "MACKENZIE", "TAYLOR", "OLIVIA", "HAILEY", "PAIGE", "EMILY", "GRACE", "AVA", "AALIYAH", "ALYSSA", "FAITH", "BRIANNA"] ts = None # Function that represents a Man def Man(name): # Get the tuplespace we're working in ts = linda.universe._in(("ts", linda.TupleSpace))[1] # Randomize the order we want to propose to people in order = women[:] random.shuffle(order) # propose to each woman in order for w in order: print name + " proposing to " + w ts._out(("propose", name, w)) # wait to see if we get rejected. If a deadlock is reached we've finished and should exit r = ts._inp(("reject", name, w)) if r is None: break print "%s ended with %s (%i)" % (name, w, order.index(w) + 1) # Function that represents a Woman def Woman(name): # Returns the person we'd rather marry def BestOf(fiance, suitor): if fiance is None: return suitor elif order.index(fiance) < order.index(suitor): return fiance else: return suitor # Returns the person we'd rather not marry def WorstOf(fiance, suitor): if BestOf(fiance, suitor) == fiance: return suitor else: return fiance # Get the tuplespace we're working in ts = linda.universe._in(("ts", linda.TupleSpace))[1] # Randomize the order we want to marry people in order = men[:] random.shuffle(order) fiance = None while 1: # wait to be proposed to. If this returns None then a deadlock was reached p = ts._inp(("propose", str, name)) if p is None: break else: suitor = p[1] # Choose who to reject and who to keep reject = WorstOf(fiance, suitor) fiance = BestOf(fiance, suitor) if reject is not None: print "%s rejecting %s for %s" % (name, reject, fiance) ts._out(("reject", reject, name)) else: print "%s accepting %s" % (name, fiance) print "%s ended with %s (%i)" % (name, fiance, order.index(fiance) + 1) import sys # Create a tuplespace for us to work in if args[0] == "man" and args[1] == "0": ts = linda.TupleSpace() for i in range(len(men) + len(women)): linda.universe._out(("ts", ts)) del ts if args[0] == "man": Man(men[int(sys.argv[2])]) elif args[0] == "men": for i in range(0,len(men)): print "spawn", i os.spawnl(os.P_NOWAIT, "marriage.py", "marriage.py", "man", str(i)) #if os.fork() == 0: # os.execlp("./marriage.py", "marriage.py", "man", str(i)) elif args[0] == "woman": Woman(women[int(sys.argv[2])]) elif args[0] == "women": for i in range(0,len(women)): print "spawn", i os.spawnl(os.P_NOWAIT, "marriage.py", "marriage.py", "woman", str(i)) #if os.fork() == 0: # os.execlp("./marriage.py", "marriage.py","woman", str(i))
00001 #!/usr/bin/python 00002 00003 # Copyright 2004 Andrew Wilkinson <aw@cs.york.ac.uk>. 00004 # 00005 # This file is part of PyLinda (http://www-users.cs.york.ac.uk/~aw/pylinda) 00006 # 00007 # PyLinda is free software; you can redistribute it and/or modify 00008 # it under the terms of the GNU Lesser General Public License as published by 00009 # the Free Software Foundation; either version 2.1 of the License, or 00010 # (at your option) any later version. 00011 # 00012 # PyLinda is distributed in the hope that it will be useful, 00013 # but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 # GNU Lesser General Public License for more details. 00016 # 00017 # You should have received a copy of the GNU Lesser General Public License 00018 # along with PyLinda; if not, write to the Free Software 00019 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 00020 00021 import linda 00022 import sys 00023 import random 00024 import os 00025 00026 # 00027 # Process command line options 00028 # 00029 from optparse import OptionParser 00030 00031 parser = OptionParser(version="%prog 1.0") 00032 parser.add_option("-p", "--connect-port", type="int", dest="connectport", default=2102, 00033 help="The port to connect to.") 00034 00035 (options, args) = parser.parse_args() 00036 00037 linda.connect(options.connectport) 00038 # 00039 # 00040 # 00041 00042 # Lists of men's and women's names 00043 men = ["AIDAN", "JADEN", "CADEN", "ETHAN", "CALEB", "DYLAN", "JACOB", "JORDAN", "LOGAN", "HAYDEN", "CONNOR", "RYAN", "MORGAN", "CAMERON", "ANDREW", "JOSHUA", "NOAH", "MATTHEW", "ADDISON", "ASHTON"] 00044 women = ["MADISON", "EMMA", "ABIGAIL", "RILEY", "CHLOE", "HANNAH", "ALEXIS", "ISABELLA", "MACKENZIE", "TAYLOR", "OLIVIA", "HAILEY", "PAIGE", "EMILY", "GRACE", "AVA", "AALIYAH", "ALYSSA", "FAITH", "BRIANNA"] 00045 00046 ts = None 00047 00048 # Function that represents a Man 00049 def Man(name): 00050 # Get the tuplespace we're working in 00051 ts = linda.universe._in(("ts", linda.TupleSpace))[1] 00052 00053 # Randomize the order we want to propose to people in 00054 order = women[:] 00055 random.shuffle(order) 00056 00057 # propose to each woman in order 00058 for w in order: 00059 print name + " proposing to " + w 00060 ts._out(("propose", name, w)) 00061 00062 # wait to see if we get rejected. If a deadlock is reached we've finished and should exit 00063 r = ts._inp(("reject", name, w)) 00064 if r is None: 00065 break 00066 00067 print "%s ended with %s (%i)" % (name, w, order.index(w) + 1) 00068 00069 # Function that represents a Woman 00070 def Woman(name): 00071 # Returns the person we'd rather marry 00072 def BestOf(fiance, suitor): 00073 if fiance is None: 00074 return suitor 00075 elif order.index(fiance) < order.index(suitor): 00076 return fiance 00077 else: 00078 return suitor 00079 # Returns the person we'd rather not marry 00080 def WorstOf(fiance, suitor): 00081 if BestOf(fiance, suitor) == fiance: 00082 return suitor 00083 else: 00084 return fiance 00085 00086 # Get the tuplespace we're working in 00087 ts = linda.universe._in(("ts", linda.TupleSpace))[1] 00088 00089 # Randomize the order we want to marry people in 00090 order = men[:] 00091 random.shuffle(order) 00092 00093 fiance = None 00094 while 1: 00095 # wait to be proposed to. If this returns None then a deadlock was reached 00096 p = ts._inp(("propose", str, name)) 00097 if p is None: 00098 break 00099 else: 00100 suitor = p[1] 00101 00102 # Choose who to reject and who to keep 00103 reject = WorstOf(fiance, suitor) 00104 fiance = BestOf(fiance, suitor) 00105 00106 if reject is not None: 00107 print "%s rejecting %s for %s" % (name, reject, fiance) 00108 ts._out(("reject", reject, name)) 00109 else: 00110 print "%s accepting %s" % (name, fiance) 00111 00112 print "%s ended with %s (%i)" % (name, fiance, order.index(fiance) + 1) 00113 00114 import sys 00115 00116 # Create a tuplespace for us to work in 00117 if args[0] == "man" and args[1] == "0": 00118 ts = linda.TupleSpace() 00119 for i in range(len(men) + len(women)): 00120 linda.universe._out(("ts", ts)) 00121 del ts 00122 00123 if args[0] == "man": 00124 Man(men[int(sys.argv[2])]) 00125 00126 elif args[0] == "men": 00127 for i in range(0,len(men)): 00128 print "spawn", i 00129 os.spawnl(os.P_NOWAIT, "marriage.py", "marriage.py", "man", str(i)) 00130 #if os.fork() == 0: 00131 # os.execlp("./marriage.py", "marriage.py", "man", str(i)) 00132 00133 elif args[0] == "woman": 00134 Woman(women[int(sys.argv[2])]) 00135 00136 elif args[0] == "women": 00137 for i in range(0,len(women)): 00138 print "spawn", i 00139 os.spawnl(os.P_NOWAIT, "marriage.py", "marriage.py", "woman", str(i)) 00140 #if os.fork() == 0: 00141 # os.execlp("./marriage.py", "marriage.py","woman", str(i)) 00142 00143

PyLinda is © Copyright 2004 Andrew Wilkinson.

Generated on Thu Jan 13 14:12:30 2005 for PyLinda by doxygen 1.3.7