This notebook was prepared by Donne Martin. Source and license info is on GitHub.

# Challenge Notebook¶

## Constraints¶

• Is it possible to have a cyclic graph as the input?
• Yes
• Can we assume we already have Graph and Node classes?
• Yes
• Can we assume this is a connected graph?
• Yes
• Can we assume the inputs are valid?
• Yes
• Can we assume this fits memory?
• Yes

## Test Cases¶

• projects: a, b, c, d, e, f, g
• dependencies: (d, g), (f, c), (f, b), (f, a), (c, a), (b, a), (a, e), (b, e)
• output: d, f, c, b, g, a, e

Note: Edge direction is down

    f     d
/|\    |
c | b   g
\|/|
a |
|/
e


Test a graph with a cycle, output should be None

## Algorithm¶

Refer to the Solution Notebook. If you are stuck and need a hint, the solution notebook's algorithm discussion might be a good place to start.

## Code¶

In [ ]:
class Dependency(object):

def __init__(self, node_key_before, node_key_after):
self.node_key_before = node_key_before
self.node_key_after = node_key_after

In [ ]:
%run ../graph/graph.py

In [ ]:
class BuildOrder(object):

def __init__(self, dependencies):
# TODO: Implement me
pass

def find_build_order(self):
# TODO: Implement me
pass


## Unit Test¶

The following unit test is expected to fail until you solve the challenge.

In [ ]:
# %load test_build_order.py
import unittest

class TestBuildOrder(unittest.TestCase):

def __init__(self, *args, **kwargs):
super(TestBuildOrder, self).__init__()
self.dependencies = [
Dependency('d', 'g'),
Dependency('f', 'c'),
Dependency('f', 'b'),
Dependency('f', 'a'),
Dependency('c', 'a'),
Dependency('b', 'a'),
Dependency('a', 'e'),
Dependency('b', 'e'),
]

def test_build_order(self):
build_order = BuildOrder(self.dependencies)
processed_nodes = build_order.find_build_order()

expected_result0 = ('d', 'f')
expected_result1 = ('c', 'b', 'g')
self.assertTrue(processed_nodes[0].key in expected_result0)
self.assertTrue(processed_nodes[1].key in expected_result0)
self.assertTrue(processed_nodes[2].key in expected_result1)
self.assertTrue(processed_nodes[3].key in expected_result1)
self.assertTrue(processed_nodes[4].key in expected_result1)
self.assertTrue(processed_nodes[5].key is 'a')
self.assertTrue(processed_nodes[6].key is 'e')

print('Success: test_build_order')

def test_build_order_circular(self):
self.dependencies.append(Dependency('e', 'f'))
build_order = BuildOrder(self.dependencies)
processed_nodes = build_order.find_build_order()
self.assertTrue(processed_nodes is None)

print('Success: test_build_order_circular')

def main():
test = TestBuildOrder()
test.test_build_order()
test.test_build_order_circular()

if __name__ == '__main__':
main()


## Solution Notebook¶

Review the Solution Notebook for a discussion on algorithms and code solutions.