Mercurial > sypikslang

comparison gamelib/lab.py @ 153:a644f6b64a6d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Implement just the tiny bit of networkx we actually need, so we can drop the extra dependency.
author Jeremy Thurgood <firxen@gmail.com>
date Fri, 11 May 2012 20:27:37 +0200
parents 372d886f9e70
children 4bbd4a1879f8
comparison
equal deleted inserted replaced
152:5b58e2150a4f 153:a644f6b64a6d
1 # -*- test-case-name: gamelib.tests.test_lab -*- 1 # -*- test-case-name: gamelib.tests.test_lab -*-
2 2
3 from random import random, choice, sample 3 from random import random, choice, sample
4
5 import networkx
6 4
7 from gamelib import research, schematics 5 from gamelib import research, schematics
8 from gamelib.game_base import get_subclasses 6 from gamelib.game_base import get_subclasses
9 7
10 8
11 class ScienceGraph(object): 9 class ScienceGraph(object):
12 def __init__(self, all_science, known_science): 10 def __init__(self, all_science, known_science):
13 self.graph = networkx.DiGraph() 11 self._graph = {}
12 self.node = {}
14 self.all_science = all_science 13 self.all_science = all_science
15 self.known_science = known_science 14 self.known_science = known_science
16 self.add_all_science() 15 self.add_all_science()
17 self.tag_known_science() 16 self.tag_known_science()
18 assert networkx.is_directed_acyclic_graph(self.graph)
19 17
20 def add_all_science(self): 18 def add_all_science(self):
21 # Add level 0 of everything to the graph. 19 # Add level 0 of everything to the graph.
22 for science in self.all_science: 20 for science in self.all_science:
23 self.graph.add_node((science, 0), known=False) 21 self.add_node((science, 0), known=False)
24 22
25 # Walk dependencies and fill in intermediate nodes. 23 # Walk dependencies and fill in intermediate nodes.
26 for science in self.all_science: 24 for science in self.all_science:
27 for dep in science.PREREQUISITES: 25 for dep in science.PREREQUISITES:
28 self.add_node_string(*dep) 26 self.add_node_string(*dep)
29 self.graph.add_edge(dep, (science, 0)) 27 self.add_edge(dep, (science, 0))
28
29 def add_node(self, node, **attrs):
30 self.node[node] = attrs
31 self._graph[node] = {}
32
33 def add_edge(self, a, b, **attrs):
34 if a not in self._graph:
35 self.add_node(a)
36 if b not in self._graph:
37 self.add_node(b)
38 self._graph[a][b] = attrs
39
40 def predecessors(self, node):
41 preds = []
42 for n, e in self._graph.iteritems():
43 if node in e:
44 preds.append(n)
45 return preds
30 46
31 def add_node_string(self, science, level): 47 def add_node_string(self, science, level):
32 node = (science, level) 48 node = (science, level)
33 if node in self.graph: 49 if node in self._graph:
34 return node 50 return node
35 51
36 # We prepopulate with level 0 of eveything. 52 # We prepopulate with level 0 of eveything.
37 assert level >= 0 53 assert level >= 0
38 54
39 self.graph.add_node(node, known=False) 55 self.add_node(node, known=False)
40 parent = self.add_node_string(science, level - 1) 56 parent = self.add_node_string(science, level - 1)
41 self.graph.add_edge(parent, node) 57 self.add_edge(parent, node)
42 return node 58 return node
43 59
44 def tag_known_science(self): 60 def tag_known_science(self):
45 for science in self.known_science: 61 for science in self.known_science:
46 # We may know more of this than the graph has. 62 # We may know more of this than the graph has.
47 self.add_node_string(type(science), science.points + 1) 63 self.add_node_string(type(science), science.points + 1)
48 for i in range(science.points + 1): 64 for i in range(science.points + 1):
49 self.graph.node[(type(science), i)]['known'] = True 65 self.node[(type(science), i)]['known'] = True
50 66
51 def is_known(self, node): 67 def is_known(self, node):
52 return self.graph.node[node]['known'] 68 return self.node[node]['known']
53 69
54 def distances_to_known(self, science): 70 def distances_to_known(self, science):
55 nodes = set() 71 nodes = set()
56 nodes_to_check = [(science, 0)] 72 nodes_to_check = [(science, 0)]
57 73
58 while nodes_to_check: 74 while nodes_to_check:
59 node = nodes_to_check.pop() 75 node = nodes_to_check.pop()
60 if self.is_known(node) or node in nodes: 76 if self.is_known(node) or node in nodes:
61 continue 77 continue
62 nodes.add(node) 78 nodes.add(node)
63 nodes_to_check.extend(self.graph.predecessors(node)) 79 nodes_to_check.extend(self.predecessors(node))
64 80
65 distances = {} 81 distances = {}
66 for node in nodes: 82 for node in nodes:
67 distances.setdefault(node[0], 0) 83 distances.setdefault(node[0], 0)
68 distances[node[0]] += 1 84 distances[node[0]] += 1