-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathalgorithm.py
More file actions
119 lines (93 loc) · 5.87 KB
/
algorithm.py
File metadata and controls
119 lines (93 loc) · 5.87 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
from pulp import *
def check_host_guest_match(host, guest):
match_result = True
host_seats = host["seats_available"]
#print "seats in host = ", host_seats
guest_seats = guest["seats_requested"]
#print "seats for guest = ", guest_seats
if(host_seats < guest_seats):
match_result = False
if((host["children_ok"] == False) and (guest["children_requested"] == True)):
match_result = False
if((host["babies_ok"] == False) and (guest["babies_requested"] == True)):
match_result = False
if((host["vegetarians_ok"] == False) and (guest["vegetarians_requested"] == True)):
match_result = False
#check if host banned the guest
guest_id = guest["user_id"]
for banned_guest_id in host["Banned_users"]:
if(guest_id == banned_guest_id):
match_result = False
#check if guest banned the host
host_id = host["user_id"]
for banned_host_id in guest["Banned_users"]:
if(host_id == banned_host_id):
match_result = False
return match_result
def matching_algorithm(info_dict):
#create the list of variables
edge_num = -1;
edges = []
for host in info_dict["hosts"]:
for guest in info_dict["guests"]:
if (check_host_guest_match(host,guest)):
edge_num+=1
variable_name = "edge"+str(edge_num)
print variable_name
var = LpVariable(variable_name, 0, 1, pulp.LpInteger)
edge = {"variable": var, "guest_id": guest["user_id"], "host_id": host["user_id"], "weight": guest["seats_requested"]}
edges.append(edge)
print "The total number of edges is ", len(edges)
prob = LpProblem("MealMatch", LpMinimize)
# create cost function
objective = 0;
for edge in edges:
objective+= edge["variable"]
prob += -objective, "total number of matches"
# constraint: each guest only goes to one house
for guest in info_dict["guests"]:
guest_unique_host = 0;
for e in edges:
if(e["guest_id"] == guest["user_id"]):
guest_unique_host += e["variable"]
costraint_name = "GestToUniqueHost"+str(guest["user_id"])
prob += guest_unique_host <=1, costraint_name
#print "the guest id is = ", guest["user_id"]
#print guest_single_house_constraint
# constraint: each host can only accept a certain number of guest
for host in info_dict["hosts"]:
host_total_guest_constraint = 0;
for e in edges:
if(e["host_id"] == host["user_id"]):
host_total_guest_constraint += e["variable"]*e["weight"]
costraint_name = "TotalGuestPerHost"+str(host["user_id"])
prob += host_total_guest_constraint <=host["seats_available"], costraint_name
prob.solve()
print("Status:", [prob.status])
for v in prob.variables():
#print(v.name, "=", v.varValue)
if(v.varValue >0):
for e in edges:
if(e["variable"].name == v.name):
print "Guest ", e["guest_id"]," will be hosted by Host ", e["host_id"]
host0 = {"user_id": 0, "seats_available": 3, "children_ok": False, "vegetarians_ok": False, "babies_ok": False, "Is_Meat": True, "Banned_users": [10]}
host1 = {"user_id": 1, "seats_available": 2, "children_ok": False, "vegetarians_ok": False, "babies_ok": False, "Is_Meat": True, "Banned_users": [10]}
host2 = {"user_id": 2, "seats_available": 3, "children_ok": False, "vegetarians_ok": True, "babies_ok": False, "Is_Meat": False, "Banned_users": [10]}
host3 = {"user_id": 3, "seats_available": 4, "children_ok": True, "vegetarians_ok": True, "babies_ok": True, "Is_Meat": True, "Banned_users": [11,12]}
host4 = {"user_id": 4, "seats_available": 2, "children_ok": False, "vegetarians_ok": False, "babies_ok": False, "Is_Meat": True, "Banned_users": []}
host5 = {"user_id": 5, "seats_available": 3, "children_ok": False, "vegetarians_ok": True, "babies_ok": False, "Is_Meat": True, "Banned_users": [19]}
host6 = {"user_id": 6, "seats_available": 2, "children_ok": False, "vegetarians_ok": True, "babies_ok": False, "Is_Meat": False, "Banned_users": []}
guest0 = {"user_id": 10, "seats_requested": 1, "babies_requested": False, "children_requested": False, "vegetarians_requested": False, "Meat_ok": True, "Dairy_ok": True, "Banned_users": []}
guest1 = {"user_id": 11, "seats_requested": 2, "babies_requested": False, "children_requested": False, "vegetarians_requested": False, "Meat_ok": True, "Dairy_ok": True, "Banned_users": [0]}
guest2 = {"user_id": 12, "seats_requested": 1, "babies_requested": False, "children_requested": False, "vegetarians_requested": False, "Meat_ok": False, "Dairy_ok": True, "Banned_users": []}
guest3 = {"user_id": 13, "seats_requested": 2, "babies_requested": False, "children_requested": False, "vegetarians_requested": False, "Meat_ok": True, "Dairy_ok": True, "Banned_users": [0,2,3]}
guest4 = {"user_id": 14, "seats_requested": 2, "babies_requested": False, "children_requested": False, "vegetarians_requested": False, "Meat_ok": True, "Dairy_ok": True, "Banned_users": []}
guest5 = {"user_id": 15, "seats_requested": 1, "babies_requested": False, "children_requested": False, "vegetarians_requested": False, "Meat_ok": True, "Dairy_ok": True, "Banned_users": [0,4]}
guest6 = {"user_id": 16, "seats_requested": 2, "babies_requested": False, "children_requested": False, "vegetarians_requested": False, "Meat_ok": False, "Dairy_ok": True, "Banned_users": []}
guest7 = {"user_id": 17, "seats_requested": 2, "babies_requested": False, "children_requested": False, "vegetarians_requested": False, "Meat_ok": True, "Dairy_ok": False, "Banned_users": []}
guest8 = {"user_id": 18, "seats_requested": 4, "babies_requested": False, "children_requested": True, "vegetarians_requested": False, "Meat_ok": True, "Dairy_ok": True, "Banned_users": []}
guest9 = {"user_id": 19, "seats_requested": 1, "babies_requested": False, "children_requested": False, "vegetarians_requested": False, "Meat_ok": True, "Dairy_ok": True, "Banned_users": []}
check = check_host_guest_match(host0,guest0)
print "the host and guest 0 match as: ", check
x = {"hosts": [host0, host1, host2, host3, host4, host5, host6], "guests": [guest0, guest1, guest2, guest3, guest4, guest5, guest6, guest7, guest8, guest9]}
matching_algorithm(x)