Skip to content

Instantly share code, notes, and snippets.

@RavuAlHemio

RavuAlHemio/apples.py

Created January 19, 2014 15:24
Show Gist options
  • Save RavuAlHemio/8506300 to your computer and use it in GitHub Desktop.
Save RavuAlHemio/8506300 to your computer and use it in GitHub Desktop.
Download ZIP
given a set of wanted apple types, find combinations of apple types that ensure every apple tree is well-pollinated
Raw
apples.py
import logging
__author__ = 'ondra'
logger = logging.getLogger("apples")
class Apple:
def __init__(self, number, name, bloom_time, good_donors=None, other_donors=None,
triploid=False):
"""
Constructs an apple.
:param number: The ID number of the apple.
:param name: The name of the apple.
:param bloom_time: What time the apple blooms in.
:param good_donors: Which apple types are good pollen donors for this apple.
:param other_donors: Which apple types are not-as-good pollen donors for this apple.
:param triploid: Whether this apple is triploid, i.e. a poor pollen donor.
:type number: int
:type name: str
:type bloom_time: str
:type good_donors: set[int]|None
:type other_donors: set[int]|None
:type triploid: bool
"""
self.number = number
""":type: int"""
self.name = name
""":type: str"""
self.bloom_time = bloom_time
""":type: str"""
self.good_donors = good_donors if good_donors is not None else set()
""":type: set[int]"""
self.other_donors = other_donors if other_donors is not None else set()
""":type: set[int]"""
self.triploid = triploid
""":type: bool"""
self.good_targets = set()
""":type: set[int]"""
self.other_targets = set()
""":type: set[int]"""
@staticmethod
def from_string_donors(number, name, bloom_time, donor_string, triploid=False):
"""
Constructs an apple from a donor string.
:param number: The ID number of the apple.
:param name: The name of the apple.
:param bloom_time: What time the apple blooms in.
:param donor_string: The string describing the donors.
:param triploid: Whether this apple is triploid, i.e. a poor pollen donor.
:type number: int
:type name: str
:type bloom_time: str
:type donor_string: str
:type triploid: bool
:rtype: Apple
"""
donor_strings = donor_string.split(" ")
good_donors = set()
other_donors = set()
for donor in donor_strings:
if len(donor) == 0:
continue
if donor[-1] == "*":
other_donors.add(int(donor[:-1]))
else:
good_donors.add(int(donor))
return Apple(number, name, bloom_time, good_donors, other_donors, triploid)
def __str__(self):
print("Apple({0})".format(self.name))
def __repr__(self):
return "Apple({0}, {1}, {2}, {3}, {4}, {5})".format(
repr(self.number), repr(self.name), repr(self.bloom_time), repr(self.good_donors),
repr(self.other_donors), repr(self.triploid)
)
# Data copied from:
# Kellerhals, M.; Ladner, J.; Lorenz, B.; Rusterholz, P.: "Befruchtung der Obstsorten".
# Eidgenössiche Forschungsanstalt für Obst-, Wein- und Gartenbau; CH-8820 Wädenswil
apples = [
Apple(1, "Alkmene", "f", {4, 5, 20, 23, 25, 43, 47, 62, 64, 94, 95, 102},
{16, 19, 27, 33, 34, 35, 39, 51, 59}),
Apple(2, "Ananas Reinette", "mf", {6, 16, 35, 56, 100}),
Apple(3, "Ariwa", "msp", {78, 80, 83}),
Apple(4, "Arlet", "mf", {1, 5, 16, 26, 27, 31, 32, 34, 43, 47, 51, 60, 66, 75, 95}, {25, 33}),
Apple(5, "Berlepsch", "mf", {2, 16, 32, 34, 35, 43, 51, 56, 90}, {33}),
Apple(6, "Berner Rosen", "msp", {2, 5, 14, 16, 18, 32, 33, 34, 35, 51, 56, 71, 88, 98}, {56}),
Apple(7, "Bittenfelder", "sp"),
Apple(8, "Blauacher, echter", "sp", {42, 69, 97}),
Apple(9, "Blauacher W\xE4denswil", "msp", {47, 64, 89, 91, 97}, {58}, True),
Apple(10, "Bohnapfel", "mf", {2, 6, 32, 35, 56, 71, 88, 98}, None, True),
Apple(11, "Boskoop", "mf", {1, 2, 4, 5, 6, 12, 16, 18, 19, 20, 23, 26, 27, 28, 32, 35, 43, 45,
47, 48, 51, 56, 62, 64, 71, 88, 90, 91, 93, 94, 95}, {33}, True),
Apple(12, "Braeburn", "msp", {25, 31, 33, 34, 43, 74, 81}, {20}),
Apple(13, "Bramleys Seedling", "m", {18, 31, 33, 34, 91}),
Apple(14, "Champagner Reinette", "sp", {6, 18, 29, 32, 34, 35, 51, 57, 71, 97, 98}),
Apple(15, "Close", "f-mf", {43, 47, 56, 93}),
Apple(16, "Cox Orange", "msp", {1, 4, 5, 23, 25, 27, 31, 32, 33, 34, 35, 39, 43, 47, 48, 51, 60,
64, 71, 90, 91, 102}, {20, 93, 95, 100}),
Apple(17, "Damason Reinette", "mf", {47}, None, True),
Apple(18, "Danziger Kantapfel", "msp", {2, 6, 14, 32, 35, 51, 71, 88, 97, 98}),
Apple(19, "Delbard Jubil\xE9 (Delgollune)", "msp", {34}, {1, 4, 23, 43, 47, 48, 75, 82, 94,
95}),
Apple(20, "Delcorf (Delbarestivale)", "f", {1, 4, 23, 43, 47, 48, 75, 82, 94, 95}, {34}),
Apple(21, "Deljeni (Primgold)", "msp", {19, 31, 34}),
Apple(22, "Delorina", "msp", {12, 34, 81}),
Apple(23, "Discovery", "mf", {1, 16, 27, 34, 43, 47, 48, 56, 93, 95, 102}, {25, 33}),
Apple(24, "Diwa", "mf", {12, 34, 44, 61, 73}),
Apple(25, "Elstar", "sp", {16, 28, 31, 32, 33, 34, 39, 45, 51, 55, 66, 73, 74, 82, 83, 91, 94},
{1, 4, 12, 19, 20, 23, 24, 26, 43, 47, 60, 62, 64, 75, 95, 102}),
Apple(26, "Empire", "mf", {4, 34, 43, 51, 52, 64, 91, 94, 95}),
Apple(27, "Fiesta", "msp", {16, 19, 25, 28, 31, 33, 34, 43, 60, 67, 91}, {1}),
Apple(28, "Florina", "msp", {4, 19, 25, 27, 31, 33, 34, 35, 39, 66, 85, 94}, {58}),
Apple(29, "Fraurotacher", "sp", {14, 32, 69}),
Apple(30, "Fuji", "msp", {12, 31, 34, 39, 43, 66, 79, 82}),
Apple(31, "Gala", "msp", {16, 25, 28, 30, 32, 33, 34, 39, 43, 44, 47, 48, 51, 60, 66, 75, 76,
85, 91, 94}, {20}),
Apple(32, "Glockenapfel", "m", {5, 6, 16, 18, 26, 33, 34, 35, 43, 44, 47, 51, 56, 60, 71, 88,
91, 98}),
Apple(33, "Gloster", "sp", {16, 25, 27, 31, 32, 34, 35, 39, 45, 51, 55, 66, 73, 85, 91, 94},
{1, 23, 26, 43, 47, 48, 60, 95, 102}),
Apple(34, "Golden Delicious", "msp", {6, 12, 16, 18, 23, 24, 25, 26, 27, 30, 31, 32, 33, 35, 39,
43, 44, 45, 47, 48, 51, 55, 66, 73, 74, 77, 80, 82, 83,
85, 90, 91, 94, 102}, {1, 4, 20, 95}),
Apple(35, "Goldparm\xE4ne", "msp", {2, 5, 6, 14, 16, 18, 28, 32, 34, 43, 47, 51, 55, 60, 71, 75,
91, 97, 98}, {56}),
Apple(36, "Goldrush", "mf", {12, 23, 27, 30, 39}),
Apple(37, "Goldstar", "msp", {76, 23}),
Apple(38, "Goro", "sp", {16, 34, 51, 55, 91}),
Apple(39, "Granny Smith", "msp", {16, 25, 28, 31, 33, 34, 35, 43, 48, 51, 66, 74, 75, 94, 102},
{1}),
Apple(40, "Gravensteiner", "f", {1, 2, 5, 23, 32, 43, 47, 52, 56, 60, 64, 88, 93, 94, 100},
{16, 33, 34, 35, 39, 51}, True),
Apple(41, "Heimenhofer", "msp", {42, 91}),
Apple(42, "Hordapfel, grauer", "msp", {41, 57, 88, 97, 98}),
Apple(43, "Idared", "mf", {1, 4, 5, 26, 27, 31, 32, 34, 35, 39, 47, 48, 51, 52, 56, 58, 60, 64,
66, 73, 75, 78, 79, 80, 90, 91, 93, 94, 102}, {33, 83}),
Apple(44, "Iduna", "msp", {4, 12, 32, 34, 43, 60, 73, 85}),
Apple(45, "Ingrid Marie", "msp", {16, 25, 32, 33, 34, 35, 47, 51}),
Apple(46, "Jakob Level", "mf", {6, 16, 18, 32, 51, 56, 71}, {14}, True),
Apple(47, "James Grieve", "mf", {1, 4, 5, 16, 23, 32, 34, 35, 43, 48, 51, 56, 59, 64, 88, 91,
93, 95, 102}, {25, 33}),
Apple(48, "Jerseymac", "mf", {16, 23, 31, 34, 35, 39, 43, 47, 60, 75, 91, 95, 102}, {25}),
Apple(49, "Jerseyred", "msp", {34, 43, 47, 91}, None, True),
Apple(50, "Jonagold", "msp", {4, 5, 12, 16, 19, 23, 24, 25, 26, 27, 31, 32, 33, 35, 38, 39, 43,
45, 47, 48, 51, 52, 55, 64, 66, 74, 75, 85, 91, 94, 102}, {1, 20},
True),
Apple(51, "Jonathan", "msp", {4, 5, 6, 14, 16, 18, 25, 29, 31, 32, 33, 34, 35, 38, 39, 42, 43,
47, 60, 64, 71, 85, 88, 91, 94, 97, 98}, {1, 56, 93, 95, 100}),
Apple(52, "Julyred", "mf", {16, 26, 34, 43, 47, 51, 56, 64, 75, 91, 94, 95, 102}, {25, 33}),
Apple(53, "Kanada Reinette", "mf", {2, 16, 18, 32, 34, 51, 71}, None, True),
Apple(54, "Karmijn", "mso", {23, 25, 32, 33, 34, 43, 47, 55, 60, 62, 85, 91, 102}, {1, 95},
True),
Apple(55, "Kidds Orange", "sp", {25, 31, 32, 33, 34, 35, 38, 51, 60, 88, 91, 94}, {43, 95}),
Apple(56, "Klarapfel, weisser", "f", {2, 5, 32, 43, 47, 51, 64, 88, 93, 100}, {6, 16, 34, 35,
38}),
Apple.from_string_donors(57, "Leuenapfel", "sp", "14 29 42 69 97 98"),
Apple.from_string_donors(58, "Liberty", "f", "1 19* 20 28* 34* 39* 43 47 64 75 91* 94"),
Apple.from_string_donors(59, "Lobo", "msp", "16 34 35 47 51 91"),
Apple.from_string_donors(60, "Maigold", "mf", "4 12 16 18 25* 26 27 28 31 32 33* 35 43 47 48 " +
"51 52 55* 56 64 66 90 91 93 94 95 102"),
Apple.from_string_donors(61, "Mairac", "mf", "12 24 25 31 34 43 72"),
Apple.from_string_donors(62, "Mantet", "mf", "16 25* 35 47 59 70"),
Apple.from_string_donors(63, "Marina", "msp", "34 44 85"),
Apple.from_string_donors(64, "McIntosh", "mf", "4 16 26 32 34 35 43 47 51 52 56 91 93"),
Apple.from_string_donors(65, "Menznauer J\xE4ger", "msp", "14 35 71"),
Apple.from_string_donors(66, "Meran", "msp", "12 19 25 27 30 31 33 34 39 60 85"),
Apple.from_string_donors(67, "Morgenduft", "sp", "51 70* 92"),
Apple.from_string_donors(68, "Mutsu", "msp", "16 33 35 43 45 47 51 64 91 94", True),
Apple.from_string_donors(69, "Oberrieder Glanzreinette", "sp", "14 29 88* 97"),
Apple.from_string_donors(70, "Oldenburg", "mf", "16 34 35 47 56"),
Apple.from_string_donors(71, "Ontario", "msp", "2 14 16 18 32 35 51 88 97 98"),
Apple.from_string_donors(72, "Pink Lady", "msp", "12 39"),
Apple.from_string_donors(73, "Pinova", "msp", "25 31 33 34 43 47 77 79 80 82 83 85"),
Apple.from_string_donors(74, "Prima", "m", "102"),
Apple.from_string_donors(75, "Primerouge", "mf", "16 31 33 34 35 39 43 47 60 91 94 95 102"),
Apple.from_string_donors(76, "Rajka", "m", "37 99"),
Apple.from_string_donors(77, "Reanda", "m", "34 43 47 73 74 79 82 83"),
Apple.from_string_donors(78, "Regine", "msp", "34 43 47 73 83"),
Apple.from_string_donors(79, "Reglindis", "msp", "1 28 43 47 58 73 74 77 82"),
Apple.from_string_donors(80, "Resi", "msp", "3 43 47 74 79 82 83 97 99"),
Apple.from_string_donors(81, "Resista", "msp", "3 99"),
Apple.from_string_donors(82, "Retina", "m", "1 28 34 43 47 74 77 79 83"),
Apple.from_string_donors(83, "Rewena", "sp", "1* 34 43* 47* 58* 73 74 77 79 82"),
Apple.from_string_donors(84, "Rubens", "?", ""),
Apple.from_string_donors(85, "Rubinette", "msp", "1 4 26 28 31 32 33 34 43 47 48 51 52 55 58 " +
"60 64 66 75 91 102"),
Apple.from_string_donors(86, "Rubinola", "m", "76 99"),
Apple.from_string_donors(87, "Saturn", "msp", "19 80 99"),
Apple.from_string_donors(88, "Sauergrauech", "mf", "2 6 16 18 32 42 47 51 56 64 71 98 100"),
Apple.from_string_donors(89, "Schneiderapfel", "msp", ""),
Apple.from_string_donors(90, "Schweizer Orangenapfel", "mf", "32 34 35 43 51 60 94"),
Apple.from_string_donors(91, "Spartan", "msp", "16 25 26 27 31 32 33 34 35 43 47 48 51 52 " +
"55 59 60 64 66 85 94"),
Apple.from_string_donors(92, "St\xE4fner Rosen", "sp", "6 14 18 35 51 57 71 97 98", True),
Apple.from_string_donors(93, "Stark Earliest", "f", "16* 34* 43 47 51* 56 60 64 100"),
Apple.from_string_donors(94, "Starkring, Starkrimson", "m", "1 16 25 26 28 33 34 35 39 43 48 " +
"51 52 55 60 64 66 74 75 91 95 " +
"102"),
Apple.from_string_donors(95, "Summerred", "f", "1 4 16* 23 25* 26 27* 34* 35* 39* 43 47 48 " +
"51* 60 74 75 94 102"),
Apple.from_string_donors(96, "Tentation", "msp", "24 39"),
Apple.from_string_donors(97, "Thurgauer Weinapfel", "sp", "6 14 18 32 35 51 57 69 71 98"),
Apple.from_string_donors(98, "Tobi\xE4sler", "msp", "6 14 16 18 32 35 51 57 71 88 97"),
Apple.from_string_donors(99, "Topaz", "msp", "23 76 78 80 85 87"),
Apple.from_string_donors(100, "Transparent von Croncels", "f", "2 6* 16* 18* 32 35* 47 56 " +
"71* 88 93"),
Apple.from_string_donors(101, "Usterapfel", "m", "5 58 85"),
Apple.from_string_donors(102, "Vista Bella", "mf", "1 34 43 47 48 52 75 91 94 95")
]
def build_apple_map():
"""
Build the apple map from the list of apples.
:return: The mapping of apple numbers to apple objects.
:rtype: dict[int, Apple]
"""
apple_map = {}
for apple in apples:
if apple.number in apple_map:
raise ValueError("duplicate apple #{0}".format(apple.number))
apple_map[apple.number] = apple
for apple in apple_map.values():
for donor_number in apple.good_donors:
if donor_number not in apple_map:
raise ValueError("apple #{0} has invalid donor #{1}".format(apple.number,
donor_number))
apple_map[donor_number].good_targets.add(apple.number)
for donor_number in apple.other_donors:
if donor_number not in apple_map:
raise ValueError("apple #{0} has invalid donor #{1}".format(apple.number,
donor_number))
apple_map[donor_number].other_targets.add(apple.number)
return apple_map
def apple_cycle_finder(apple_map, wanted_apple_numbers, apple_numbers_to_pollinate,
pollinated_apple_numbers, max_apple_types, good_only=True):
"""
Actually finds apple cycles. You probably want to call apple_cycle instead.
:param apple_map: The mapping of apple numbers to apple objects.
:type apple_map: dict[int, Apple]
:param wanted_apple_numbers: Set of apple numbers of the apple types wanted in the orchard and
not yet taken care of.
:type wanted_apple_numbers: set[int]|frozenset[int]
:param apple_numbers_to_pollinate: Set of apple numbers of the apple types which will be in the
orchard but whose pollination has not been established yet.
:type apple_numbers_to_pollinate: set[int]|frozenset[int]
:param pollinated_apple_numbers: Set of apple numbers of the apple types which will be in the
orchard and for which a pollen donor has been found.
:type pollinated_apple_numbers: set[int]|frozenset[int]
:param max_apple_types: Maximum number of apple types in the orchard. Used for limiting each
iteration of the iterative deepening search in use here.
:type max_apple_types: int
:param good_only: Only consider the "good" donors. Considers all donors if False.
:type good_only: bool
:return: List of apple number sets wherein each apple tree has a pollen donor.
:rtype: list[frozenset[int]]
"""
# remove pollinated apples from wanted apples
needed_apple_numbers = wanted_apple_numbers - pollinated_apple_numbers
logger.debug("needed: {0}, pollinate: {1}, pollinated: {2}".format(
needed_apple_numbers, apple_numbers_to_pollinate, pollinated_apple_numbers
))
if len(needed_apple_numbers) == 0 and len(apple_numbers_to_pollinate) == 0:
return [pollinated_apple_numbers]
elif len(pollinated_apple_numbers) >= max_apple_types:
# too many trees
return []
shortest_cycles = []
for needed_apple_number in needed_apple_numbers:
logger.debug("trying apple #{0}".format(needed_apple_number))
# pop it
my_needed_apple_numbers = needed_apple_numbers - {needed_apple_number}
my_apple_numbers_to_pollinate = apple_numbers_to_pollinate | {needed_apple_number}
for apple_number in my_apple_numbers_to_pollinate:
logger.debug("I'm gonna pollinate #{0}".format(apple_number))
apple = apple_map[apple_number]
# consider this apple pollinated
sub_apple_numbers_to_pollinate = my_apple_numbers_to_pollinate - {apple_number}
sub_pollinated_apple_numbers = pollinated_apple_numbers | {apple_number}
# check out all of its pollen donor candidates
donors = set(apple.good_donors)
if not good_only:
donors |= apple.other_donors
for donor_candidate_number in donors:
logger.debug("a donor would be #{0}".format(donor_candidate_number))
sub_needed_apple_numbers = my_needed_apple_numbers | {donor_candidate_number}
sub_cycles = apple_cycle_finder(apple_map, sub_needed_apple_numbers,
sub_apple_numbers_to_pollinate,
sub_pollinated_apple_numbers, max_apple_types,
good_only)
if len(sub_cycles) > 0:
logger.debug("found cycles {0}".format(sub_cycles))
if len(shortest_cycles) == 0:
#logger.info("new shortest cycles {0}".format(sub_cycles))
shortest_cycles = sub_cycles
elif len(shortest_cycles[0]) > len(sub_cycles[0]):
#logger.info("new shortest cycles {0}".format(sub_cycles))
shortest_cycles = sub_cycles
elif len(shortest_cycles[0]) == len(sub_cycles[0]):
shortest_cycles += sub_cycles
return shortest_cycles
def apple_cycle(apple_map, wanted_apple_numbers, good_only=True):
"""
:param apple_map: The mapping of apple numbers to apple objects.
:type apple_map: dict[int, Apple]
:param wanted_apple_numbers: Set of apple numbers of the apple types wanted in the orchard.
:type wanted_apple_numbers: set[int]|frozenset[int]
:param good_only: Only consider the "good" donors (i.e. donors whose bloom time intersects
sufficiently with the recipient). Considers all donors if False.
:type good_only: bool
:return: Set of apple number sets wherein each apple tree has a pollen donor.
:rtype: frozenset[frozenset[int]]
"""
for max_apple_types in range(len(wanted_apple_numbers), len(apple_map)+1):
logger.info("trying with {0} trees".format(max_apple_types))
cycles = apple_cycle_finder(apple_map, wanted_apple_numbers, frozenset(), frozenset(),
max_apple_types, good_only)
if len(cycles) > 0:
# remove duplicates by converting into a set
return frozenset(cycles)
def dot_apple_set(apple_map, apple_set, graph_name="apples"):
"""
Returns a GraphViz directed graph of the interactions of the given apple set.
:param apple_map: The mapping of apple numbers to apple objects.
:type apple_map: dict[int, Apple]
:param apple_set: The set of apple numbers whose interactions to graph.
:type apple_set: set[int]|frozenset[int]
:param graph_name: Name of the digraph in the returned string.
:type graph_name: str
:return: The GraphViz graph of the interactions of the given apple set.
:rtype: str
"""
ret = "digraph {0} {{\n".format(graph_name)
# nodes
for apple_number in apple_set:
apple = apple_map[apple_number]
ret += '\tnode [label = "{0}"]; A{1};\n'.format(apple.name, apple.number)
# edges
for apple in apple_map.values():
if apple.number not in apple_set:
continue
for donor_number in apple.good_donors:
if donor_number not in apple_set:
continue
ret += '\tA{0} -> A{1};\n'.format(donor_number, apple.number)
ret += "}\n"
return ret
def apply_blacklist_to_map(apple_map, blacklist):
"""
Returns an apple map with the unwanted apples and references to them removed.
:param apple_map: The mapping of apple numbers to apple objects to filter.
:type apple_map: dict[int, Apple]
:param blacklist: Set of apple numbers to remove from the map.
:type blacklist: set[int]|frozenset[int]
:returns: The filtered apple map, with references to the blacklisted apples removed.
:rtype: dict[int, Apple]
"""
new_apple_map = {}
for apple in apple_map.values():
if apple.number in blacklist:
continue
new_good_donors = apple.good_donors - blacklist
new_other_donors = apple.other_donors - blacklist
new_apple = Apple(apple.number, apple.name, apple.bloom_time, new_good_donors,
new_other_donors, apple.triploid)
new_apple.good_targets = apple.good_targets - blacklist
new_apple.other_targets = apple.other_targets - blacklist
new_apple_map[new_apple.number] = new_apple
return new_apple_map
if __name__ == '__main__':
handler = logging.StreamHandler()
handler.setLevel(logging.DEBUG)
#logger.setLevel(logging.DEBUG)
logger.setLevel(logging.INFO)
logger.addHandler(handler)
built_apple_map = build_apple_map()
# blacklist Idared
apple_map_after_blacklist = apply_blacklist_to_map(built_apple_map, {43})
# Boskoop, Jonathan, weisser Klarapfel
cycles = apple_cycle(apple_map_after_blacklist, {56, 11, 51}, True)
for cycle in cycles:
print(dot_apple_set(apple_map_after_blacklist, cycle))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment