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

# Solution 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:

• add_edge(source, destination, weight)
graph.add_edge(0, 1, 5)
graph.add_edge(5, 2, 9)

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¶

### Node¶

Node will keep track of its:

• id
• visit state
• incoming edge count (useful for algorithms such as topological sort)
• adjacent nodes and edge weights

• Update the adjacent nodes and edge weights
• Increment the neighbor's incoming edge count

Complexity:

• Time: O(1)
• Space: O(1)

#### remove_neighbor¶

• If the neighbor exists as an adjacent node
• Decrement the neighbor's incoming edge count
• Remove the neighbor as an adjacent node

Complexity:

• Time: O(1)
• Space: O(1)

### Graph¶

Graph will keep track of its:

• nodes

• If node already exists, return it
• Create a node with the given id
• Add the newly created node to the collection of nodes

Complexity:

• Time: O(1)
• Space: O(1)

• If the source node is not in the collection of nodes, add it
• If the dest node is not in the collection of nodes, add it
• Add a connection from the source node to the dest node with the given edge weight

• Also add a connection from the dest node to the source node with the given edge weight

Complexity:

• Time: O(1)
• Space: O(1)

## Code¶

In [1]:
%%writefile graph.py
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

if neighbor is None or weight is None:
raise TypeError('neighbor or weight cannot be None')
neighbor.incoming_edges += 1

def remove_neighbor(self, neighbor):
if neighbor is None:
raise TypeError('neighbor cannot be None')
neighbor.incoming_edges -= 1

class Graph:

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

if key is None:
raise TypeError('key cannot be None')
if key not in self.nodes:
self.nodes[key] = Node(key)
return self.nodes[key]

if source_key is None or dest_key is None:
raise KeyError('Invalid key')
if source_key not in self.nodes:
if dest_key not in self.nodes:

if src_key is None or dst_key is None:
raise TypeError('key cannot be None')

Overwriting graph.py

In [2]:
%run graph.py


## Unit Test¶

In [3]:
%%writefile test_graph.py
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()

Overwriting test_graph.py

In [4]:
%run -i test_graph.py

Success: test_graph
Success: test_graph_undirected