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

# Challenge Notebook¶

## Constraints¶

• Is the graph directed?
• Implement both
• Do the edges have weights?
• Yes
• Can the graph have cycles?
• Yes
• If we try to add a node that already exists, do we just do nothing?
• Yes
• If we try to delete a node that doesn't exist, do we just do nothing?
• 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¶

Input:

Result:

• source and destination nodes within graph are connected with specified weight.

Note:

• The Graph class will be used as a building block for more complex graph challenges.

## 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 [ ]:
from enum import Enum  # Python 2 users: Run pip install enum34

class State(Enum):

unvisited = 0
visiting = 1
visited = 2

class Node:

def __init__(self, key):
self.key = key
self.visit_state = State.unvisited
self.incoming_edges = 0
self.adj_nodes = {}  # Key = key, val = Node
self.adj_weights = {}  # Key = key, val = weight

def __repr__(self):
return str(self.key)

def __lt__(self, other):
return self.key < other.key

# TODO: Implement me
pass

def remove_neighbor(self, neighbor):
# TODO: Implement me
pass

class Graph:

def __init__(self):
self.nodes = {}  # Key = key, val = Node

# TODO: Implement me
pass

# TODO: Implement me
pass

# TODO: Implement me
pass

## Unit Test¶

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

In [ ]:
import unittest

class TestGraph(unittest.TestCase):

def create_graph(self):
graph = Graph()
for key in range(0, 6):
return graph

def test_graph(self):
graph = self.create_graph()

self.assertEqual(graph.nodes[0].incoming_edges, 1)
self.assertEqual(graph.nodes[1].incoming_edges, 1)
self.assertEqual(graph.nodes[2].incoming_edges, 2)
self.assertEqual(graph.nodes[3].incoming_edges, 1)
self.assertEqual(graph.nodes[4].incoming_edges, 2)
self.assertEqual(graph.nodes[5].incoming_edges, 2)

graph.nodes[0].remove_neighbor(graph.nodes[1])
self.assertEqual(graph.nodes[1].incoming_edges, 0)
graph.nodes[3].remove_neighbor(graph.nodes[4])
self.assertEqual(graph.nodes[4].incoming_edges, 1)

self.assertEqual(graph.nodes[0] < graph.nodes[1], True)

print('Success: test_graph')

def test_graph_undirected(self):
graph = self.create_graph()

print('Success: test_graph_undirected')

def main():
test = TestGraph()
test.test_graph()
test.test_graph_undirected()

if __name__ == '__main__':
main()

## Solution Notebook¶

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