Requesting help with my implementation of depth-first search

[tigerfuchs]

Hi all, I'm having trouble with my implementation of depth-first search. The implementation is based on code provided in Discrete Mathematics by Chartrand and Zhang.



My code can be found at https://github.com/tigerfuchs/dfs/blob/master/dfs.py .

Any help would be greatly appreciated.

Thank you for your time.

[micseydel]

Could you elaborate on what's wrong? Also, you'll be more likely to get a response if you paste your code into code tags here, rather than expecting people to follow a link.

[tigerfuchs]

The return value for the tree edges list - a list of the edges in the DFS search tree - is not correct. I am not quite sure at what point in the function I implemented the code incorrectly. I am thinking in the for loop, but I am not sure. Here is the code.

# the input graph is:

input_graph = {1:[3,4,8,9,11], 2:[3,8,12], 3:[1,2,5,11], 4:[1,6,9,10], 5:[3,12], 6:[4,10], 7:[8,12], 8:[1,2,7,10], 9:[1,4,11], 10:[4,6,8], 11:[1,3,9], 12:[2,5,7]}

def DFS(graph, root):
    parent_dictionary = {}
    parent_dictionary[root] = None 
    visited = [root] 
    tree_edges = [] 
    w = root 
    i = 0
    n = len(graph.keys())
    while i < (n-1): 
        for vertex in graph[w]:
            if vertex not in visited:
                visited.append(vertex)
                tree_edges.append((w,vertex))
                parent_dictionary[vertex] = w
                w = vertex
                i += 1
        w = parent_dictionary[w]
    return tree_edges 

print(DFS(input_graph, 1)) # Print value is: [(1, 3), (3, 4), (4, 8), (8, 9), (9, 11), (8, 2), (2, 7), (7, 10), (7, 12), (4, 6), (3, 5)]

# The print value should be [(1,3), (3,2), (2,8), (8,7), (8,10), (7,12), (12,5), (10,4), (4,6), (4,9), (9,11)]

# From the correct return value, I can then build the DFS tree, rooted at 1, which is:

DFS_tree = {1:[3],3:[2],2:[8],8:[7,10],7:[12],12:[5],5:[],10:[4],4:[6,9],6:[],9:[11],11:[]}

[ichabod801]

Look at the first wrong edge in the output: (3, 4). There is no such edge in your graph. How did it get that? When you add (1, 3), you change w to 3, but your for loop is still looping over the edges from 1. The next edge is (1, 4), but since you've changed w to 3, it stores it as (1, 4).

I don't understand how this algorithm is supposed to be working. I skipped that chapter when I read Discrete Mathematics because I'd done it with Introduction to Algorithms. That book uses a recursive search, which was my first instinct. I think to get it working without recursion you are going to have to reset your tracking variables a lot. When you change w, you have to change the list of edges you are going through. And when you go back after hitting a dead end I think you will need to reset i as well.

Edit: This gets the correct list of edges, just in a different order, and without recursion. It could probably be more efficient.

input_graph = {1:[3,4,8,9,11], 2:[3,8,12], 3:[1,2,5,11], 4:[1,6,9,10], 5:[3,12], 6:[4,10], 7:[8,12],
    8:[1,2,7,10], 9:[1,4,11], 10:[4,6,8], 11:[1,3,9], 12:[2,5,7]}

def DFS(graph, root):
    visited = set([root])
    current = root
    edges = []
    while len(visited) < len(graph):
        possible = [node for node in graph[current] if node not in visited]
        if possible:
            edges.append((current, possible[0]))
            visited.add(possible[0])
            current = possible[0]
        else:
            current = [start for start, end in edges if end == current][0]
    return edges

print(DFS(input_graph, 1))

[tigerfuchs]

This is great. Thank you very much.

[ichabod801]

Here's the more efficient version I was thinking of:

def DFS(graph, root):
    visited = set([root])
    current = root
    possibles = (node for node in graph[current] if node not in visited)
    search_stack = []
    edges = []
    while len(visited) < len(graph):
        try:
            possible = next(possibles)
            edges.append((current, possible))
            visited.add(possible)
            search_stack.append((current, possibles))
            current = possible
            possibles = (node for node in graph[current] if node not in visited)
        except StopIteration:
            current, possibles = search_stack.pop()
    return edges

[perfringo]

Raymond Hettinger (Python core developer) had excellent presentation last PyCon: Modern solvers: Problems well-defined are problems solved

It's more on higher level (with utilizing BFS and DFS) how to define and solve problems but there is code also: Depth First and Breath First Search.

I think that this is worth of looking at (both presentation and code).