In [19]:
"""
You need to change the Add() class below.
"""
class Node(object):
def __init__(self, inbound_nodes=[]):
# Nodes from which this Node receives values
self.inbound_nodes = inbound_nodes
# Nodes to which this Node passes values
self.outbound_nodes = []
# A calculated value
self.value = None
# Add this node as an outbound node on its inputs.
for n in self.inbound_nodes:
n.outbound_nodes.append(self)
# These will be implemented in a subclass.
def forward(self):
"""
Forward propagation.
Compute the output value based on `inbound_nodes` and
store the result in self.value.
"""
raise NotImplemented
In [20]:
class Input(Node):
def __init__(self):
# an Input node has no inbound nodes,
# so no need to pass anything to the Node instantiator
Node.__init__(self)
# NOTE: Input node is the only node that may
# receive its value as an argument to forward().
#
# All other node implementations should calculate their
# values from the value of previous nodes, using
# self.inbound_nodes
#
# Example:
# val0 = self.inbound_nodes[0].value
def forward(self, value=None):
if value is not None:
self.value = value
In [21]:
class Add(Node):
def __init__(self, x, y):
# You could access `x` and `y` in forward with
# self.inbound_nodes[0] (`x`) and self.inbound_nodes[1] (`y`)
Node.__init__(self, [x, y])
def forward(self):
"""
Set the value of this node (`self.value`) to the sum of its inbound_nodes.
Your code here!
"""
x_value = self.inbound_nodes[0].value
y_value = self.inbound_nodes[1].value
self.value = x_value + y_value
In [22]:
"""
No need to change anything below here!
"""
def topological_sort(feed_dict):
"""
Sort generic nodes in topological order using Kahn's Algorithm.
`feed_dict`: A dictionary where the key is a `Input` node and the value is the respective value feed to that node.
Returns a list of sorted nodes.
"""
input_nodes = [n for n in feed_dict.keys()]
G = {}
nodes = [n for n in input_nodes]
while len(nodes) > 0:
n = nodes.pop(0)
if n not in G:
G[n] = {'in': set(), 'out': set()}
for m in n.outbound_nodes:
if m not in G:
G[m] = {'in': set(), 'out': set()}
G[n]['out'].add(m)
G[m]['in'].add(n)
nodes.append(m)
L = []
S = set(input_nodes)
while len(S) > 0:
n = S.pop()
if isinstance(n, Input):
n.value = feed_dict[n]
L.append(n)
for m in n.outbound_nodes:
G[n]['out'].remove(m)
G[m]['in'].remove(n)
# if no other incoming edges add to S
if len(G[m]['in']) == 0:
S.add(m)
return L
In [23]:
def forward_pass(output_node, sorted_nodes):
"""
Performs a forward pass through a list of sorted nodes.
Arguments:
`output_node`: A node in the graph, should be the output node (have no outgoing edges).
`sorted_nodes`: A topologically sorted list of nodes.
Returns the output Node's value
"""
for n in sorted_nodes:
n.forward()
return output_node.value
In [24]:
# from nn.py
if __name__ == '__main__':
#from miniflow import *
x, y = Input(), Input()
f = Add(x, y)
feed_dict = {x: 10, y: 5}
sorted_nodes = topological_sort(feed_dict)
output = forward_pass(f, sorted_nodes)
# NOTE: because topological_sort set the values for the `Input` nodes we could also access
# the value for x with x.value (same goes for y).
print("{} + {} = {} (according to miniflow)".format(feed_dict[x], feed_dict[y], output))