Repository: capsulecorplab/mindgraph

Issue:
add method that returns a generator of a "sorted to-do list"
As eluded to in #5, this would be a `Node` object method that traverses its threads, and returns a sequential data structure of all head nodes. Nodes should be sorted by weight, but nodes containing dependencies should be preceded by their dependencies.

I'm thinking this should be a [generator](https://www.programiz.com/python-programming/generator) w/ the following behavior...
e.g.,
```
>>> print(graph)
build a thing:
- task 1: # has a weight of 3 (default weight: 1)
  - task 1.1
  - task 1.2 # depends on task 2.2
  - task 1.3 # has a weight of 3
- task 2: # has a weight of 2
  - task 2.1
  - task 2.2:
    - task 2.2.1
    - task 2.2.2
- task 3:
 - task 3.1
 - task 3.2 # depends on task 2.2
>>> todo = graph.sorted()
>>> next(todo)
task 1.3
>>> next(todo)
task 1.1
>>> next(todo)
task 2.2.1
>>> next(todo)
task 2.2.2
>>> next(todo)
task 1.2
>>> next(todo)
task 2.1
>>> next(todo)
task 3.1
>>> next(todo)
task 3.2
```

Feel free to point out any edge cases I may've missed, such as cyclic graphs (see #1)

Discussion:

Patch:
diff --git a/mindgraph/graph.py b/mindgraph/graph.py
index 640c52d..a1a5ad7 100644
--- a/mindgraph/graph.py
+++ b/mindgraph/graph.py
@@ -1,7 +1,8 @@
 # -*- coding: utf-8 -*-
 import functools
+from typing import (Any, Callable, Generator, Iterator, List, Optional, Set,
+                    Tuple)
 
-from typing import List
 from yaml import dump, load
 
 
@@ -72,9 +73,42 @@ class Node(object):
                                          functools.partial(node.custom_repr,
                                                            depth=depth + 1),
                                          node.threads))
-
         return "    " * (depth - 1) + "- {}".format(node.name)
 
+    def _postorder(self,
+                   depth: int = 0,
+                   visited: Set["Node"] = None,
+                   node_key: Callable[["Node"], Any]=None,
+                   ) -> Generator[Tuple[int, "Node"], None, Set["Node"]]:
+        """Post-order traversal of graph rooted at node"""
+        if visited is None:
+            visited = set()
+
+        children = self._threads
+        if node_key is not None:
+            children = sorted(self._threads, key=node_key)
+
+        for child in children:
+            if child not in visited:
+                visited = yield from child._postorder(depth+1,
+                                                      visited,
+                                                      node_key)
+
+        yield (depth, self)
+        visited.add(self)
+
+        return visited
+
+    def todo(self) -> Iterator["Node"]:
+        """Generate nodes in todo order
+
+        Nodes are scheduled by weight and to resolve blocking tasks
+        """
+        # sorts by weight (2 before 1), then alphabetical
+        def node_key(node):
+            return (-node.weight, node.name)
+        return (x[1] for x in self._postorder(node_key=node_key))
+
     def __str__(self) -> str:
         return dump(load(str(self.__repr__())), default_flow_style=False)
 


Test patch:
diff --git a/test/test_mindgraph.py b/test/test_mindgraph.py
index f21f08d..9dbac53 100644
--- a/test/test_mindgraph.py
+++ b/test/test_mindgraph.py
@@ -1,7 +1,9 @@
-from mindgraph import *
+import os
+
 import pytest
 import yaml
-import os
+
+from mindgraph import *
 
 
 @pytest.fixture(scope="module")
@@ -10,6 +12,56 @@ def graph():
     return graph
 
 
+@pytest.fixture
+def task_graph():
+    # setup example graph from issue #14
+    g = Graph('build a thing')
+
+    t1 = g.append('task 1')
+    t1.weight = 3
+    t11 = t1.append('task 1.1')
+    t12 = t1.append('task 1.2')
+    t13 = t1.append('task 1.3')
+    t13.weight = 3
+
+    t2 = g.append('task 2')
+    t2.weight = 2
+    t21 = t2.append('task 2.1')
+    t22 = t2.append('task 2.2')
+    t221 = t22.append('task 2.2.1')
+    t222 = t22.append('task 2.2.2')
+
+    t3 = g.append('task 3')
+    t31 = t3.append('task 3.1')
+    t32 = t3.append('task 3.2')
+
+    t32.threads.append(t22)
+    t12.threads.append(t22)
+    return g
+
+
+def test_todo_high_weights_win(task_graph):
+    """High weights are scheduled before low weights"""
+    todo = [n.name for n in task_graph.todo()]
+    assert todo.index('task 1') < todo.index('task 2')
+    assert todo.index('task 1') < todo.index('task 3')
+    assert todo.index('task 1.3') < todo.index('task 1.1')
+
+
+def test_todo_blocking_tasks_win(task_graph):
+    """Blocking tasks are scheduled before blocked tasks"""
+    todo = [n.name for n in task_graph.todo()]
+    assert todo.index('task 2.2') < todo.index('task 3.2')
+    assert todo.index('task 2.2') < todo.index('task 1.2')
+    assert todo.index('task 1.1') < todo.index('task 1.2')
+
+
+def test_postorder_default_weights_ignored(task_graph):
+    """Post-order traversal ignores node weights by default"""
+    po = [n.name for _, n in task_graph._postorder()]
+    assert po.index('task 1.1') < po.index('task 1.3')
+
+
 def test_node_init_typeerror():
     with pytest.raises(TypeError) as info:
         node = Node(47)