Anonymous avatar Anonymous committed 814d613

lots of minior changes and bug fixes; so prim() works fine now

Comments (0)

Files changed (7)

pyreia/algorithms/astar_al.py

 
 class ANode(PathAlgorithmNode):
 
-    def __init__(self, node):
+    def __init__(self, *args, **kwargs):
         self._clear()
-        PathAlgorithmNode.__init__(self, node)
+        PathAlgorithmNode.__init__(self, *args, **kwargs)
 
     def __cmp__(self, other):
         return cmp(self.f, other.f)

pyreia/algorithms/prim_al.py

 
 class PNode(PathAlgorithmNode):
 
-    def __init__(self, node):
-        PathAlgorithmNode.__init__(self, node)
+    def __init__(self, *args, **kwargs):
+        PathAlgorithmNode.__init__(self, *args, **kwargs)
 
         self.cost = float('inf')
         self.parent = None
         node_map = {}
         if in_place:
             self.node.clean_tree()
-            for node in self.tree:
-                node_map[node] = node.node
+            for pnode in self.tree:
+                node_map[pnode] = pnode.node
         else:
-            for node in self.tree:
-                node_map[node] = Node()
+            for pnode in self.tree:
+                node_map[pnode] = Node(name=pnode.name)
 
         for pnode, node in node_map.iteritems():
             if pnode.parent:
-                node_map[pnode.parent].add_child(node, pnode.cost, reverse=reverse)
+                nnode = node_map[pnode.parent]
+                nnode.add_child(node, pnode.cost, reverse=reverse)
 
         return node_map[self].tree
 
     def prim(self, *args, **kwargs):
         """
-        Create Nodes from the PNodes structure.
+        Algorithm of Prim to find a minimum spanning tree.
 
         See func:~`pyreia.algorithms.prim_al.prim` for a more useful docstring.
         """
             for child, cost in node.children.iteritems():
                 if child in heap and cost < child.cost:
                     child.parent = node
+
+                    ## decrese_key workaround
                     child.cost = cost
+                    heap._siftdown(0, heap.index(child))
 
         ## all trees are equal, it does not matter which node is chosen
         return self._create_graph(*args, **kwargs)

pyreia/algorithms/utils.py

         tree = self.node.tree if all else self.node.all_children
         node_map = {}
         for node in tree:
-            node_map[node] = SpecialNode(node)
+            node_map[node] = SpecialNode(node, name=node.name)
         node_map[self.node] = self
 
         for node in node_map:

pyreia/core/heap.py

     :copyright: 2010 by the pyreia Team, see AUTHORS for more details.
     :license: GNU GPL, see LICENSE for more details.
 """
-import bisect
-
 class Heap(list):
     """
     `Heap` is a object orientated Binary Heap implementation. It copies the
     :param cmp_func: Function `func(self, other)` which returns negative, if
                      `other > self`, 0 if `other == self` and positive if `self
                      > other`. Defaults to built in `cmp`.
-    :param fast_index: If `True` (default), :func:`~pyreia.heap.Heap.index`
+    :param fast_index: If `True` (default), :func:`~pyreia.core.heap.Heap.index`
                        runs much faster (constant instead of linear time). This
                        does only work, if no two items in the heap are the
                        same. If `False`, the common `list.index` method is
 
         Example Usage:
 
-            >>> heap = Heap([16, 8, 4, 2, 1])
+            >>> heap = Heap([16, 8, 6, 2, 9, 1])
             >>> heap.heappop()
             1
             >>> 1 in heap
             False
+            >>> ## create sorted list using heappop()
+            >>> lst = []
+            >>> while heap:
+            ...     lst.append(heap.heappop())
+            >>> lst
+            [2, 6, 8, 9, 16]
+
         """
         lastelt = self.pop()   # raises appropriate IndexError if heap is empty
 
         else:
             return 'Node object'
 
-    def _find(self, iterable_str):
-        nodes = Graph([])
+    def _find(self, iterables, add_self=False):
+        graph = Graph([self]) if add_self else Graph([])
         stack = [self,]
 
         while stack:
             node = stack.pop()
-            iterable = getattr(node, iterable_str)
-            for child in iterable:
-                if child not in nodes:
-                    nodes.add(child)
-                    stack.append(child)
-        return nodes
+            for iterable_str in iterables:
+                iterable = getattr(node, iterable_str)
+                for new in iterable:
+                    if new not in graph:
+                        graph.add(new)
+                        stack.append(new)
+        return graph
 
     @property
     def all_children(self):
         """
-        (property) finds all children recursively
+        Find all children recursively.
 
         :rtype: :class:`~pyreia.nodes.Graph`
         """
-        return self._find('children')
+        return self._find(['children'])
 
     @property
     def all_parents(self):
         """
-        (property) finds all parents recursively
+        Find all parents recursively.
 
         :rtype: :class:`~pyreia.nodes.Graph`
         """
-        return self._find('parents')
+        return self._find(['parents'])
 
     @property
     def tree(self):
         """
-        (property) finds all parents and children recursively
+        Find all parents and children (including `self`) recursively.
 
         :rtype: :class:`~pyreia.nodes.Graph`
         """
-        graph = self.all_children.union(self.all_parents)
-        graph.add(self)
-        return graph
+        return self._find(['children', 'parents'], True)
+
 
     def add_child(self, node, cost=1, parent_add=True, reverse=False, reverse_cost=None):
         """
 
         :param node: the to removed Node
         :type node: :class:`~pyreia.nodes.Node`
-        :param parent_remove: if False, `node` assume this Node is one of its
-                              parents
-        :type parent_remove: boolean
         :param reverse: if True, this Node is removed from `node`.children
 
-        :raises KeyError: if `node` is not a child of this Node
+
         """
         del self.children[node]
         node.parents.discard(self)
 
         if reverse:
-            node.remove_child(self, parent_remove)
+            node.remove_child(self)
 
     def clean_tree(self):
         """
             for cost in node.children.itervalues():
                 weight += cost
         return weight
+
+    def __str__(self):
+        string = ''
+        names = [str(node) for node in self]
+        string += 'Graph of %s:\n' % str(names)
+        for node in self:
+            string += '\t%s: ' % node
+            if node.children:
+                for child, cost in node.children.iteritems():
+                    string += '(%s: %i) ' %(child.name, cost)
+                string += '\n'
+            else:
+                string += 'no children\n'
+        return string.rstrip('\n')
+

tests/test_nodes.py

         self.assertEqual(self.b.tree, self.c.tree)
         self.assertEqual(self.c.tree, set([self.root, self.a, self.b, self.c]))
 
+        ## test more complex situation (similar to the prim algorithm test
+        nodes = {}
+        for i in range(7):
+            char = chr(i + 97)
+            nodes[char] = Node(char)
+        nodes['a'].add_child(nodes['b'], 7)
+        nodes['a'].add_child(nodes['d'], 5)
+        nodes['b'].add_child(nodes['e'], 7)
+        nodes['e'].add_child(nodes['c'], 5)
+        nodes['d'].add_child(nodes['f'], 6)
+        nodes['e'].add_child(nodes['g'], 9)
+        nodes = [node for node in nodes.itervalues()]
+        for node in nodes:
+            self.assertEqual(node.tree, Graph(nodes))
+
+
 class TestGraph(unittest.TestCase):
 
     def setUp(self):
         nodes[1].add_child(nodes[0], 3)
         nodes[2].add_child(nodes[4], 2)
         nodes[3].add_child(nodes[2], 7)
-        nodes[4].add_child(nodes[3], 8)
+        nodes[4].add_child(nodes[3], 8, reverse=True)
 
         self.nodes = nodes
         self.graph = Graph(nodes)
         self.assertEqual(self.graph, self.nodes[0].tree)
 
     def test_weight(self):
-        self.assertEqual(self.graph.weight, 5 + 2 + 6 + 3 + 2 + 7 + 8)
+        self.assertEqual(self.graph.weight, 5 + 2 + 6 + 3 + 2 + 7 + 8 * 2)

tests/test_prim.py

         nodes['e'].add_child(nodes['g'], 9, reverse=True)
         nodes['f'].add_child(nodes['g'], 11, reverse=True)
         self.nodes = nodes
+        self.weight = 7 + 5 + 7 + 5 + 6 + 9
 
     def test_create_graph(self):
         nodes = self.nodes
         ## do prim() manually
-        node_map = {}
-        for node in nodes.itervalues():
-            node_map[node] = PNode(node)
+        pnodes = {}
+        for char, node in nodes.iteritems():
+            pnodes[char] = PNode(node, name=char)
 
-        node_map[nodes['b']].parent = nodes['a']
-        node_map[nodes['b']].cost = 7
+        pnodes['b'].parent = pnodes['a']
+        pnodes['b'].cost = 7
 
-        node_map[nodes['d']].parent = nodes['a']
-        node_map[nodes['d']].cost = 5
+        pnodes['d'].parent = pnodes['a']
+        pnodes['d'].cost = 5
 
-        node_map[nodes['e']].parent = nodes['b']
-        node_map[nodes['e']].cost = 7
+        pnodes['e'].parent = pnodes['b']
+        pnodes['e'].cost = 7
 
-        node_map[nodes['c']].parent = nodes['e']
-        node_map[nodes['c']].cost = 5
+        pnodes['c'].parent = pnodes['e']
+        pnodes['c'].cost = 5
 
-        node_map[nodes['f']].parent = nodes['d']
-        node_map[nodes['f']].cost = 6
+        pnodes['f'].parent = pnodes['d']
+        pnodes['f'].cost = 6
 
-        node_map[nodes['g']].parent = nodes['e']
-        node_map[nodes['g']].cost = 9
+        pnodes['g'].parent = pnodes['e']
+        pnodes['g'].cost = 9
 
-        pnode = node_map[nodes['a']]
+        ## pnode.tree need to work
+        ## waah, ugly... fortunately this is only a test
+        for pnode in pnodes.itervalues():
+            for child in pnodes.itervalues():
+                pnode.add_child(child)
+
+        ## the test itself
+        pnode = pnodes['c']
         graph = pnode._create_graph()
+        self.assertEqual(graph.weight, self.weight)
+
+        ## we can use any other pnode
+        pnode = pnodes['d']
+        graph = pnode._create_graph()
+        self.assertEqual(graph.weight, self.weight)
+
+        ## test reverse
+        graph = pnode._create_graph(reverse=True)
+        self.assertEqual(graph.weight, self.weight * 2)
 
     def test_prim(self):
         nodes = self.nodes
-        mst = prim(nodes['d'], in_place=True)
+        mst = prim(nodes['c'], in_place=True, reverse=True)
+
+        ## some random checks
         self.assertFalse(nodes['d'] in nodes['b'].children)
         self.assertFalse(nodes['c'] in nodes['b'].children)
         self.assertTrue(nodes['e'] in nodes['b'].children)
-
+        ## *2 because of the reverse parameter
+        self.assertEqual(mst.weight, self.weight * 2)
 
     def test_equality(self):
         nodes = self.nodes
-        msts = []
-        for node in nodes.itervalues():
-            msts.append(set([n.name for n in prim(node)]))
+        weights = [prim(node).weight for node in nodes.itervalues()]
+
         ## all msts should be equal
-        self.assertTrue(msts[0] == msts[1] == msts[2] == msts[3])
-        self.assertTrue(msts[3] == msts[4] == msts[5] == msts[6])
+        self.assertEqual(weights, sorted(weights))
+        self.assertEqual(weights, weights[::-1])
+
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.