IMP logo
IMP Reference Guide  develop.63b38c487d,2024/12/21
The Integrative Modeling Platform
version 20241221.develop.63b38c487d
domino/marina_party.py

This is a not very serious example that shows how to use domino from scratch to solve a problem. It is illustrative of creating your own type of particles, a pair score, particle states for DOMINO, a decorator, and using subset filter tables with DOMINO.

Solution of the Marina Party Problem with DOMINO:

1 ## \example domino/marina_party.py
2 #
3 # This is a not very serious example that shows how to use domino from scratch
4 # to solve a problem. It is illustrative of creating your own type of
5 # particles, a pair score, particle states for DOMINO, a decorator, and using
6 # subset filter tables with DOMINO.
7 #
8 # Solution of the Marina Party Problem with DOMINO:
9 #
10 # - Girls attend a party
11 # - Each girl has dresses of different price
12 # - There can not be repeated dresses in the party within a group of connected
13 # people
14 # - Girls that are friends can call each other to agree
15 # - The objective is to maximize the total price of all dresses in the party
16 #
17 #
18 
19 import IMP
20 import IMP.domino
21 import IMP.core
22 import random
23 import sys
24 
25 IMP.setup_from_argv(sys.argv, "marina party")
26 
27 
28 class SumPricePairScore(IMP.PairScore):
29 
30  def evaluate_index(self, m, pair, accum):
31  price0 = Price(m.get_particle(pair[0])).get_price()
32  price1 = Price(m.get_particle(pair[1])).get_price()
33  return price0 + price1
34 
35  def do_get_inputs(self, m, pis):
36  return IMP.get_particles(m, pis)
37 
38 
39 class PriceStates(IMP.domino.ParticleStates):
40 
41  def __init__(self, prices):
42  self.prices = prices
43  IMP.domino.ParticleStates.__init__(self)
44 
45  def load_particle_state(self, i, particle):
46  pr = Price(particle)
47  pr.set_price(self.prices[i])
48 
49  def get_number_of_particle_states(self):
50  return len(self.prices)
51 
52 
53 class Price(IMP.Decorator):
54  price_key = IMP.IntKey("price")
55 
56  def __init__(self, p):
57  if not self.get_is_setup(p):
58  self.setup_particle(p)
59  self.particle = p
60 
61  def setup_particle(self, p):
62  p.add_attribute(self.price_key, 0)
63  self.particle = p
64 
65  def get_price(self):
66  return self.particle.get_value(self.price_key)
67 
68  def set_price(self, x):
69  self.particle.set_value(self.price_key, int(x))
70 
71  def get_is_setup(self, p):
72  return p.has_attribute(self.price_key)
73 
74 
75 def get_total_price(states_table, subset, assignment):
76  total_price = 0
77  for i, p in enumerate(subset):
78  price_states = states_table.get_particle_states(p)
79  price_states.load_particle_state(assignment[i], p)
80  price = Price(p).get_price()
81  total_price += price
82  return total_price
83 
84 
85 def print_assignment(states_table, subset, assignment):
86  print("########## solution assignment", assignment)
87  for i, p in enumerate(subset):
88  price_states = states_table.get_particle_states(p)
89  price_states.load_particle_state(assignment[i], p)
90  price = Price(p).get_price()
91  print(p.get_name(), "price", price)
92 
93 
94 n_girls = 10
95 n_edges = 20
96 girls = []
97 prices = [100, 200, 400, 600, 800]
98 
99 
100 model = IMP.Model()
101 
102 # prepare filter tables for DOMINO
103 states_table = IMP.domino.ParticleStatesTable()
104 sampler = IMP.domino.DominoSampler(model, states_table)
105 all_possible_states = PriceStates(prices)
106 
107 
108 # set_states
109 for i in range(n_girls):
110  p = IMP.Particle(model, "girl-%d" % i)
111  pr = Price(p)
112  girls.append(p)
113  # add possible dresses
114  states_table.set_particle_states(p, all_possible_states)
115 
116  # dresses
117  if len(prices) == 1:
118  n_dresses = 1
119  else:
120  n_dresses = random.randrange(1, len(prices) + 1)
121 
122  # Each girl has a selection of dresses
123  selection = random.sample(prices, n_dresses)
124  allowed_states_indices = [prices.index(price) for price in selection]
125  print(p.get_name(), "prices selected", selection, "indices",
126  allowed_states_indices)
127  list_states_table = IMP.domino.ListSubsetFilterTable(states_table)
128  list_states_table.set_allowed_states(p, allowed_states_indices)
129  sampler.add_subset_filter_table(list_states_table)
130 
131 # create restraints
132 rs = []
133 for z in range(n_edges):
134  # pair of friends
135  i = random.randrange(0, n_girls)
136  j = random.randrange(0, n_girls)
137  friends = IMP.ParticlePair(girls[i], girls[j])
138  # restraint
139  score = SumPricePairScore()
140  rs.append(IMP.core.PairRestraint(model, score, friends))
141  # Exclusion states. Two girls can't have same dress
142  ft = IMP.domino.ExclusionSubsetFilterTable()
143  ft.add_pair(friends)
144  sampler.add_subset_filter_table(ft)
145 sampler.set_restraints(rs)
146 
147 subset = states_table.get_subset()
148 solutions = sampler.get_sample_assignments(subset)
149 
150 if len(solutions) == 0:
151  print("There are no solutions to the problem")
152 else:
153  most_expensive = 0
154  best_solution = solutions[0]
155  for assignment in solutions:
156  total_price = get_total_price(states_table, subset, assignment)
157  if(total_price > most_expensive):
158  most_expensive = total_price
159  best_solution = assignment
160  print(" There are", len(solutions), "possible solutions")
161  print("=================> BEST SOLUTION <==============")
162  print_assignment(states_table, subset, best_solution)