Question

I've been reviewing the code from lecture 22 in order to complete problem set 11 and I think there's something wrong with the way the Digraph class is set up. It seems to me that the addNode definition will add any node regardless of whether the node's name is the same because the nodes in self.nodes are the actual node objects rather than the string representations of the nodes' names. So when it tests to see if the node's name is already in self.nodes, it doesn't find it and adds the new node object. Am I missing something? I'll post the code below.

Answer 1

import random

class Node(object):
def __init__(self, name):
self.name = name
def getName(self):
return self.name
def __str__(self):
return self.name

class Edge(object):
def __init__(self, src, dest):
self.src = src
self.dest = dest
def getSource(self):
return self.src
def getDestination(self):
return self.dest
def getWeight(self):
return self.weight
def __str__(self):
return str(self.src) + '->' + str(self.dest)

class Digraph(object):
def __init__(self):
self.nodes = set([])
self.edges = {}
def addNode(self, node):
if node.getName() in self.nodes:
raise ValueError('Duplicate node')
else:
self.nodes.add(node)
self.edges[node] = []
def addEdge(self, edge):
src = edge.getSource()
dest = edge.getDestination()
if not(src in self.nodes and dest in self.nodes):
raise ValueError('Node not in graph')
self.edges[src].append(dest)
def childrenOf(self, node):
return self.edges[node]
def hasNode(self, node):
return node in self.nodes
def __str__(self):
res = ''
for k in self.edges:
for d in self.edges[k]:
res = res + str(k) + '->' + str(d) + '\n'
return res[:-1]

class Graph(Digraph):
def addEdge(self, edge):
Digraph.addEdge(self, edge)
rev = Edge(edge.getDestination(), edge.getSource())
Digraph.addEdge(self, rev)

def test1(kind):
nodes = []
for name in range(10):
nodes.append(Node(str(name)))
g = kind()
for n in nodes:
g.addNode(n)
g.addEdge(Edge(nodes[0],nodes[1]))
g.addEdge(Edge(nodes[1],nodes[2]))
g.addEdge(Edge(nodes[2],nodes[3]))
g.addEdge(Edge(nodes[3],nodes[4]))
g.addEdge(Edge(nodes[3],nodes[5]))
g.addEdge(Edge(nodes[0],nodes[2]))
g.addEdge(Edge(nodes[1],nodes[1]))
g.addEdge(Edge(nodes[1],nodes[0]))
g.addEdge(Edge(nodes[4],nodes[0]))
print 'The graph:'
print g

##test1(Digraph)
##test1(Graph)

def shortestPath(graph, start, end, toPrint = False, visited = []):
global numCalls
numCalls += 1
if toPrint: #for debugging
print start, end
if not (graph.hasNode(start) and graph.hasNode(end)):
raise ValueError('Start or end not in graph.')
path = [str(start)]
if start == end:
return path
shortest = None
for node in graph.childrenOf(start):
if (str(node) not in visited): #avoid cycles
visited = visited + [str(node)] #new list
newPath = shortestPath(graph, node, end, toPrint, visited)
if newPath == None:
continue
if (shortest == None or len(newPath) < len(shortest)):
shortest = newPath
if shortest != None:
path = path + shortest
else:
path = None
return path

def test2(kind, toPrint = False):
nodes = []
for name in range(10):
nodes.append(Node(str(name)))
g = kind()
for n in nodes:
g.addNode(n)
g.addEdge(Edge(nodes[0],nodes[1]))
g.addEdge(Edge(nodes[1],nodes[2]))
g.addEdge(Edge(nodes[2],nodes[3]))
g.addEdge(Edge(nodes[3],nodes[4]))
g.addEdge(Edge(nodes[3],nodes[5]))
g.addEdge(Edge(nodes[0],nodes[2]))
g.addEdge(Edge(nodes[1],nodes[1]))
g.addEdge(Edge(nodes[1],nodes[0]))
g.addEdge(Edge(nodes[4],nodes[0]))
print 'The graph:'
print g
shortest = shortestPath(g, nodes[0], nodes[4], toPrint)
print 'The shortest path:'
print shortest

##test2(Graph)
##test2(Digraph)

def bigTest1(kind, numNodes = 25, numEdges = 200):
nodes = []
for name in range(numNodes):
nodes.append(Node(str(name)))
g = kind()
for n in nodes:
g.addNode(n)
for e in range(numEdges):
src = nodes[random.choice(range(0, len(nodes)))]
dest = nodes[random.choice(range(0, len(nodes)))]
g.addEdge(Edge(src, dest))
print g
print shortestPath(g, nodes[0], nodes[4])

##bigTest1(Digraph)

##test2(Graph, toPrint = True)

def dpShortestPath(graph, start, end, visited = [], memo = {}):
global numCalls
numCalls += 1
if not (graph.hasNode(start) and graph.hasNode(end)):
raise ValueError('Start or end not in graph.')
path = [str(start)]
if start == end:
return path
shortest = None
for node in graph.childrenOf(start):
if (str(node) not in visited):
visited = visited + [str(node)]
try:
newPath = memo[node, end]
except:
newPath = dpShortestPath(graph, node, end,
visited, memo)
if newPath == None:
continue
if (shortest == None or len(newPath) < len(shortest)):
shortest = newPath
memo[node, end] = newPath
if shortest != None:
path = path + shortest
else:
path = None
return path

def test3(kind):
nodes = []
for name in range(10):
nodes.append(Node(str(name)))
g = kind()
for n in nodes:
g.addNode(n)
g.addEdge(Edge(nodes[0],nodes[1]))
g.addEdge(Edge(nodes[1],nodes[2]))
g.addEdge(Edge(nodes[2],nodes[3]))
g.addEdge(Edge(nodes[3],nodes[4]))
g.addEdge(Edge(nodes[3],nodes[5]))
g.addEdge(Edge(nodes[0],nodes[2]))
g.addEdge(Edge(nodes[1],nodes[1]))
g.addEdge(Edge(nodes[1],nodes[0]))
g.addEdge(Edge(nodes[4],nodes[0]))
print 'The graph:'
print g
shortest = shortestPath(g, nodes[0], nodes[4])
print 'The shortest path:'
print shortest
shortest = dpShortestPath(g, nodes[0], nodes[4])
print 'The shortest path:'
print shortest

##test3(Digraph)

def bigTest2(kind, numNodes = 25, numEdges = 200):
global numCalls
nodes = []
for name in range(numNodes):
nodes.append(Node(str(name)))
g = kind()
for n in nodes:
g.addNode(n)
for e in range(numEdges):
src = nodes[random.choice(range(0, len(nodes)))]
dest = nodes[random.choice(range(0, len(nodes)))]
g.addEdge(Edge(src, dest))
print g
numCalls = 0
print shortestPath(g, nodes[0], nodes[4])
print 'Number of calls to shortest path =', numCalls
numCalls = 0
print dpShortestPath(g, nodes[0], nodes[4])
print 'Number of calls to dp shortest path =', numCalls

bigTest2(Digraph)

class Item(object):
def __init__(self, n, v, w):
self.name = n
self.value = float(v)
self.weight = float(w)
def getName(self):
return self.name
def getValue(self):
return self.value
def getWeight(self):
return self.weight
def __str__(self):
result = '<' + self.name + ', ' + str(self.value) + ', ' + str(self.weight) + '>'
return result

def buildManyItems(numItems, maxVal, maxWeight):
Items = []
for i in range(numItems):
Items.append(Item(str(i), random.randrange(1, maxVal),
random.randrange(1, maxWeight)))
return Items

def solve(toConsider, avail):
global numCalls
numCalls += 1
if toConsider == [] or avail == 0:
result = (0, ())
elif toConsider[0].getWeight() > avail:
result = solve(toConsider[1:], avail)
else:
nextItem = toConsider[0]
#Explore left branch
withVal, withToTake = solve(toConsider[1:],
avail - nextItem.getWeight())
withVal += nextItem.getValue()
#Explore right branch
withoutVal, withoutToTake = solve(toConsider[1:], avail)
#Choose better branch
if withVal > withoutVal:
result = (withVal, withToTake + (nextItem,))
else:
result = (withoutVal, withoutToTake)
return result

def smallTest(numItems = 10, maxVal = 20, maxWeight = 15):
global numCalls
numCalls = 0
Items = buildManyItems(numItems, maxVal, maxWeight)
val, taken = solve(Items, 50)
for item in taken:
print(item)
print 'Total value of items taken = ' + str(val)
print 'Number of calls = ' + str(numCalls)

##smallTest()

Answer 2

No you're not. I tested a sample of it, and it looks like it would need to iterate through the node.name s in the set.

Answer 3

Thanks! It's nice to know I actually understood this issue.

Answer 4

Also, have you by any chance solved this problem set? I don't know if it was in the version of this class you said you'd done. If you have, I'd love to see your solutions.

Answer 5

Sorry, PS11 is a robot vacuum and PS12 is a medicine study.