Implementing a (modified) DFS in a Graph

Question

I have implemented a simple graph data structure in Python with the following structure below. The code is here just to clarify what the functions/variables mean, but they are pretty self-explanatory so you can skip reading it.

class Node: 

    def __init__(self, label):   
        self.out_edges = []
        self.label = label
        self.is_goal = False
        self.is_visited = False


    def add_edge(self, node, weight):              
        self.out_edges.append(Edge(node, weight))

    def visit(self):                              
        self.is_visited = True


class Edge:

    def __init__(self, node, weight):              
        self.node = node
        self.weight = weight


    def to(self):                                  
        return self.node


class Graph:    

    def __init__(self): 
        self.nodes = []


    def add_node(self, label):                    
        self.nodes.append(Node(label))


    def visit_nodes(self):                                                 
        for node in self.nodes:
            node.is_visited = True

Now I am trying to implement a depth-first search which starts from a given node v, and returns a path (in list form) to a goal node. By goal node, I mean a node with the attribute is_goal set to true. If a path exists, and a goal node is found, the string ':-)' is added to the list. Otherwise, the function just performs a DFS and goes as far as it can go. (I do this here just to easily check whether a path exists or not).

This is my implementation:

def dfs(G, v):
    path = []                                   # path is empty so far

    v.visit()                                   # mark the node as visited
    path.append(v.label)                        # add to path

    if v.is_goal:                               # if v is a goal node
        path.append(':-)')                      # indicate a path is reached
        G.visit_nodes()                         # set all remaining nodes to visited

    else:
        for edge in v.out_edges:                # for each out_edge of the starting node
            if not edge.to().is_visited:        # if the node pointed to is not visited
                path += dfs(G, edge.to())       # return the path + dfs starting from that node

    return path

Now the problem is, I have to set all the nodes to visited (line 9, visit_nodes()) for the algorithm to end once a goal node is reached. In effect, this sort of breaks out of the awaiting recursive calls since it ensures no other nodes are added to the path. My question is:

Is there a cleaner/better way to do this?

The solution seems a bit kludgy. I'd appreciate any help.

Answer 1

It would be better not to clutter the graph structure with visited information, as that really is context-sensitive information linked to a search algorithm, not with the graph itself. You can use a separate set instead.

Secondly, you have a bug in the code, as you keep adding to the path variable, even if your recursive call did not find the target node. So your path will even have nodes in sequence that have no edge between them, but are (close or remote) siblings/cousins.

Instead you should only return a path when you found the target node, and then after making the recursive call you should test that condition to determine whether to prefix that path with the current edge node you are trying with.

There is in fact no need to keep a path variable, as per recursion level you are only looking for one node to be added to a path you get from the recursive call. It is not necessary to store that one node in a list. Just a simple variable will do.

Here is the suggested code (not tested):

def dfs(G, v):
    visited = set() # keep visited information away from graph

    def _dfs(v):
        visited.add(v) # mark the node as visited
        if v.is_goal:
            return [':-)'] # return end point of path
        for edge in v.out_edges:
            neighbor = edge.to() # to avoid calling to() several times
            if neighbor not in visited:
                result = _dfs(neighbor)
                if result: # only when successful
                    # we only need 1 success: add current neighbor and exit
                    return [neighbor.label] + result 
                # otherwise, nothing should change to any path: continue

        # don't return anything in case of failure

    # call nested function: the visited and Graph variables are shared
    return _dfs(v) 

Remark

For the same reason as for visited, it is maybe better to remove the is_goal marking from the graph as well, and pass that target node as an additional argument to the dfs function.

It would also be nice to give a default value for the weight argument, so that you can use this code for unweighted graphs as well.

See how it runs on a sample graph with 5 nodes on repl.it.