# HG changeset patch
# User Jeremy Thurgood <firxen@gmail.com>
# Date 1336760857 -7200
# Node ID a644f6b64a6d1f594c8e9d0a147df01d398b3a41
# Parent  5b58e2150a4f8012f1e0f672c6f8b791df06c47c
Implement just the tiny bit of networkx we actually need, so we can drop the extra dependency.

diff -r 5b58e2150a4f -r a644f6b64a6d gamelib/lab.py
--- a/gamelib/lab.py	Fri May 11 20:07:44 2012 +0200
+++ b/gamelib/lab.py	Fri May 11 20:27:37 2012 +0200
@@ -2,43 +2,59 @@
 
 from random import random, choice, sample
 
-import networkx
-
 from gamelib import research, schematics
 from gamelib.game_base import get_subclasses
 
 
 class ScienceGraph(object):
     def __init__(self, all_science, known_science):
-        self.graph = networkx.DiGraph()
+        self._graph = {}
+        self.node = {}
         self.all_science = all_science
         self.known_science = known_science
         self.add_all_science()
         self.tag_known_science()
-        assert networkx.is_directed_acyclic_graph(self.graph)
 
     def add_all_science(self):
         # Add level 0 of everything to the graph.
         for science in self.all_science:
-            self.graph.add_node((science, 0), known=False)
+            self.add_node((science, 0), known=False)
 
         # Walk dependencies and fill in intermediate nodes.
         for science in self.all_science:
             for dep in science.PREREQUISITES:
                 self.add_node_string(*dep)
-                self.graph.add_edge(dep, (science, 0))
+                self.add_edge(dep, (science, 0))
+
+    def add_node(self, node, **attrs):
+        self.node[node] = attrs
+        self._graph[node] = {}
+
+    def add_edge(self, a, b, **attrs):
+        if a not in self._graph:
+            self.add_node(a)
+        if b not in self._graph:
+            self.add_node(b)
+        self._graph[a][b] = attrs
+
+    def predecessors(self, node):
+        preds = []
+        for n, e in self._graph.iteritems():
+            if node in e:
+                preds.append(n)
+        return preds
 
     def add_node_string(self, science, level):
         node = (science, level)
-        if node in self.graph:
+        if node in self._graph:
             return node
 
         # We prepopulate with level 0 of eveything.
         assert level >= 0
 
-        self.graph.add_node(node, known=False)
+        self.add_node(node, known=False)
         parent = self.add_node_string(science, level - 1)
-        self.graph.add_edge(parent, node)
+        self.add_edge(parent, node)
         return node
 
     def tag_known_science(self):
@@ -46,10 +62,10 @@
             # We may know more of this than the graph has.
             self.add_node_string(type(science), science.points + 1)
             for i in range(science.points + 1):
-                self.graph.node[(type(science), i)]['known'] = True
+                self.node[(type(science), i)]['known'] = True
 
     def is_known(self, node):
-        return self.graph.node[node]['known']
+        return self.node[node]['known']
 
     def distances_to_known(self, science):
         nodes = set()
@@ -60,7 +76,7 @@
             if self.is_known(node) or node in nodes:
                 continue
             nodes.add(node)
-            nodes_to_check.extend(self.graph.predecessors(node))
+            nodes_to_check.extend(self.predecessors(node))
 
         distances = {}
         for node in nodes: