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!

Hey If you get it to work plz update your code here I am having the same problem can't figure out the second part. I would really appreciate if someone is able to help us out here.

Hey guys, I am working on this too. The first thing I see wrong with this code is that your for loop is running through the graph. The pseudo code says it should be running thorugh the list of neighbors for the node that is input.

Try this:

def DFSnodewithDeletion(graph,node)
   count = 1
   for i in node.neighbors:
   node.neighbors.remove(i)
   i.neighbors.remove(node)
   count = count + DFSnodeWithDeletion(graph,i)

If your graph is connected I think it return the total number of nodes. Play around with it and let me know what happens.

Ok, I found out that this code break if you use the graph like on the HW pdf. That is if the graph looks like:
A: C
C: A, F, D
F: C
D: C, B, G
B: D
G: D
E: H
H: E

xhaui Can you upload your working code.

And plzz explain why it breaks b/c I am really confused with the whole thing

My code is the same code from the lecture notes, in terms of the load graph functions and everything. The aboce code break because there are 6 connected nodes in the graph, and then two nodes which are connected to eachother but no other nodes. When counting, the count should print 6, but it prints 3. If it printed 6, we could conclude that the graph is not ocnnected, because the total number of nodes is 8.

Lucky, have you gotten anywhere with this?

i am confused of your title as seem to be knowing the number of nodes without traversing. Looks like you are looking for connectedness.

xhaui, using your bit of code, I am getting this error.

Intro to CS (Python)/nodecount2.py", line 81, in DFSnodeWithDeletion
    for i in node.neighbors:
AttributeError: 'NoneType' object has no attribute 'neighbors'

where my input for node is findNode(graph,start)

Nevermind, that actually wasn't what was being input because of an oversight.

Now the problem is I'm not sure how to use the count; it's not being incremented correctly in the provided code.