Commits

Anonymous committed 822e1b4

small fix in A* algorithm and some (minior) work on documentation

  • Participants
  • Parent commits 89d9ef5

Comments (0)

Files changed (4)

File docs/algorithms/astar.rst

 * optimal efficient (there is no algorithm which needs to check less Nodes than
   A*)
 
+This implementation has a (worst case) running time of :math:`O( V ^2)`, where
+`V` is the number of vertices in the graph. If searching a Node in
+:class:`~pyreia.core.heap.Heap` would be constant (instead of linear), a
+running time of :math:`O( V \log V)`.
+
 .. autofunction:: pyreia.algorithms.astar_al.astar
 
 This function can be imported from `pyreia.algorithms` directly.

File docs/algorithms/prim.rst

 
 This function can be imported from `pyreia.algorithms` directly.
 
+.. rubric:: Footnotes
+
 .. [#] Time complexy information by
    `Wikipedia <http://en.wikipedia.org/wiki/Prim%27s_algorithm#Time_complexity>`_

File docs/core/heap.rst

 
 .. autoclass:: pyreia.core.heap.Heap
    :members:
+
+:TODO: Implement Fibonacci heaps.
+:TODO: Implement constant search of items.

File pyreia/algorithms/astar_al.py

         self._clear()
         PathAlgorithmNode.__init__(self, node)
 
+    def __cmp__(self, other):
+        return cmp(self.f, other.f)
+
     def _clear(self):
         self.f = 0
         self.g = 0
         A more usefull docstring can be found at
         func:`~pyreia.algorithms.astar_al.astar`.
         """
-        _cmp = lambda node, other: cmp(node.f, other.f)
-        open_heap = Heap([self], cmp_func=_cmp)
+        open_heap = Heap([self])
 
         while open_heap:
             chosen = open_heap.heappop()