Hey guys, just like the other graph/node problem on here, I too have a problem with graphs.
The problem is as listed here: http://www.cs.rit.edu/~vcss241/Homeworks/08/AlternateDFS-stu.pdf
and the pseudocode for what I'm trying to do is this:
DFSnodeWithDeletion( graph, node ):
count the node itself
for every neighbor of node:
remove the edge(s) between the node and neighbor
add the result of DFSnodeWithDeletion( graph, neighbor ) to count
return the count
I have been able to complete the first method (Non-destructive) but the destructive one is giving me some problems. What I have now just goes through, counts every node and deletes it which is of no use to me because that will always say they are all connected. I need to to be deleting the connection between node and neighbor rather than the node.
I threw in a print statement after it deletes so you can see what I'm talking about.
Also, what's the flaw in the destructive example, if any?
Here's my code so far:
class Node:
''' Represents a node in the graph, neighbors should be a list of Nodes.'''
__slots__ = ['name', 'neighbors']
def makeNode(name):
''' Constructs a node object with the given name and no neighbors. '''
n = Node()
n.name = name
n.neighbors = []
return n
def findNode(graph,name):
''' returns the node from the graph with the given name. '''
for n in graph:
if n.name == name:
return n
def loadGraph(filename):
'''
Loads graph data from the file with the given name, assumes that
each line contains two strings (representing the two nodes of
an edge), in which case edges in both directions will be formed.
Nodes will be created on an as-needed basis.
Assumes a well-formed file. Returns a list of nodes.
'''
graph = []
for line in open(filename):
contents = line.split()
n1 = findNode(graph,contents[0])
if n1 == None:
n1 = makeNode(contents[0])
graph.append(n1)
n2 = findNode(graph,contents[1])
if n2 == None:
n2 = makeNode(contents[1])
graph.append(n2)
n1.neighbors.append(n2)
n2.neighbors.append(n1)
return graph
def printNode(n):
''' Prints the name of the node and its neighbors' names, all on one line. '''
print(n.name,end = ': ')
if len(n.neighbors) > 0:
for i in range(0,len(n.neighbors)-1):
print(n.neighbors[i].name, end=', ')
print(n.neighbors[len(n.neighbors)-1].name)
def printGraph(graph):
''' Prints a graph by simply printing each of its nodes. '''
for n in graph:
printNode(n)
def dfspNode(start,visited):
'''
Takes a graph and two node objects representing the start and goal of
the search, along with a list of nodes visited.
Returns a list of nodes forming a path.
'''
for n in start.neighbors:
if not n in visited:
visited.append(n)
path = dfspNode(n,visited)
if path != None:
return [start]+path
listCount = []
def DFSnodeWithDeletion2(graph,node,listCount):
for n in graph:
graph.remove(n)
printGraph(graph)
print('!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!')
listCount.append(1)
DFSnodeWithDeletion(graph,node)
return len(listCount)
def DFSnodeWithDeletion(graph,node):
return DFSnodeWithDeletion2(graph,node,listCount)
def dfspath(start):
'''
Performs a graph search given a start and goal and prints out
the resulting path.
'''
# start node needs to be marked as visited when we start
visited = [start]
# by passing in a named list here we will be able to see the
# final status of the visited list when the search is complete.
path = dfspNode(start,visited)
print(len(visited), "nodes were able to be visited")
print(len(graph), "total nodes")
if path == None:
if len(visited) != len(graph):
print("This graph has disconnected nodes")
else:
print("This graph is completely connected")
else:
for n in path:
print(n.name)
# read in the data:
graph = loadGraph(input("Enter graph data filename: "))
printGraph(graph)
# get start and goal from the user
start = findNode(graph,input("Enter any starting node name: "))
#goal = findNode(graph,input("Enter goal node name: "))
dfspath(start)
print('BEGIN DESTRUCTIVE TEST:')
if len(graph) == DFSnodeWithDeletion(graph,findNode(graph,start)):
print('All nodes were able to be reached and removed; the graph is completely connected')
print('The size of the graph has been reduced to: '+str(len(graph)))
else:
print('The graph is not completely connected')
print('There were '+str(len(graph)+' nodes that were unable to be reached'))Thanks in advance everyone!
