Finding a cycle in a DFS directed graph

Question

I'm trying to find a cycle in an directed graph using a dfs search. I'm reading in the file from a text file that holds all the neighbors of a vertex. Whenever I call the cycle_exists method I keep getting all false, so the answer never changes.

Vertex.py 
"""
__version__ = 'October 2015'

Vertex class reads in our graph and
performs a depth first search on it
and performs the transitive closure operation.
Vertex class also checks for cycles in our graph.
"""


import sys
class Graph:

    def __init__(self):
        """
        Initialize the variable used in Graph
        """
        self.dfsPaths = [] #list for dfsPaths
        self.VertexList = {} #list for adjacent vertices


    def readInputGraph(self, inputFile):
        """
        Reads specified input file and stores in
        adjacency list
        :param inputFile: file to be rad in
        :return: the VertexList
        """
        file = open(inputFile, 'r') #open the file and read it
        for line in file: #for each element in the file
            (vertex,val) = line.split() #vertex gets first value in the line, val gets second
            if vertex not in self.VertexList: #if vertex not in VertexList
               self.VertexList[vertex] = set([val]) #add adjacent pairs
            else:   #else
                self.VertexList.get(vertex).add(val) #add the values


        for i in list(self.VertexList.keys()): #for each element in the list of the vertex keys
            for j in self.VertexList[i]: # for each vertex that's in i
                if j not in self.VertexList: #if j is not in the vertex list
                    self.VertexList[j] = set() #we add it to the vertex list

        return self.VertexList #return list of adjacent vertices

    def dfsSearch(self, graph, start, end, path = []):
        """
        Performs a depth first search on
        the graph that is read in from the file
        :param graph: the graph that we are performing the search on
        :param start: the starting vertex
        :param end: the target vertex
        :param path: a list of the paths
        :return: the paths from the search
        """
        path = path + [start] #path
        if start == end: #if the start element and end element are the same
            return [path] #return the list of paths
        if start not in graph: #if the start element is not in the graph
            print( 'Not Found')#prints out not found
            return [] #return an empty list
        paths = [] #path list
        for node in graph[start]: #for node in the graph

            if node not in path: #if not in the path
                newpaths = self.dfsSearch(graph, node, end, path) #new paths we found

                for newpath in newpaths: #for each new path in the list of new paths
                    paths.append(newpath) #add the new path to our list of paths

        paths.sort() #sort our paths
        self.cycle_exists(graph)
        #print(self.cycle_exists(graph))

        return paths #return our paths


    def cycle_exists(self, graph): # -graph is our graph.
        color = { node : "white" for node in graph}  #color all nodes white to begin with
        found_cycle = False # found_cycle set to false

        for node in graph: # for each node in graph.
            if color[node]:#if the color[node] is white
                self.dfs_visit(graph, node, color, found_cycle) #we call the dfs_visit method
            if found_cycle:#if a cycle is found
                found_cycle = True
                break#break
        return found_cycle #return the true or false

    def dfs_visit(self,graph, node, color, found_cycle):
        #print(color)
        if found_cycle: # if a cycle is found return to the cycle_exists method
            return
        color[node] = "gray"#else color the node gray
        for neighbor in graph[node]: #for every neighbor in the graph of the node
            if color[neighbor] == "gray": #If neighbor is gray
                found_cycle = True # then a cycle exists.
                return
            if color[neighbor] == "white": #if the neighbor is white
                #print(color[neighbor])
                self.dfs_visit(graph, neighbor, color, found_cycle)# call dfs_visit .

        color[node] = "black"# color the original node black

GraphDriver.py from Vertex import * import sys

class GraphDriver:
    def __init__(self):
        self.graph = Graph()

def main():
    graph = Graph()
    inFile = sys.argv[1]
    d = graph.readInputGraph(inFile)

    userInput = input("Enter a source and destination:")

    dog = userInput.split(" ", -1)


    for path in graph.dfsSearch(d, dog[0], dog[1]):
        print(path)




if __name__ == '__main__':
    main()

Input.txt 0 1 0 6 1 2 1 5 2 3 2 4 4 3 4 0 5 4 6 5

Answer 1

The problem with your code is that it expects the boolean variable found_cycle to be passed by-reference to dfs_visit. However, Python does pass by-value (link, link). Therefore, when dfs_visit sets the parameter found_cycle to True, this modification will not affect the found_cycle variable passed into dfs_visit by the caller.

You can fix this by changing dfs_visit to return whether a cycle was found:

    def cycle_exists(self, graph):
        color = { node : "white" for node in graph}

        for node in graph:
            if color[node] == "white":
                if self.dfs_visit(graph, node, color):
                    return True

        return False

    def dfs_visit(self,graph, node, color):
        color[node] = "gray"

        for neighbor in graph[node]:
            if color[neighbor] == "gray":
                return True
            if color[neighbor] == "white":
                if self.dfs_visit(graph, neighbor, color):
                    return True

        color[node] = "black"
        return False

Background information

Regarding the passing of boolean variables, consider the following example:

def f(my_bool):
  my_bool = True

my_bool = False
f(my_bool)

print(my_bool)

This code will print False. In the global scope, the variable my_bool is initialized with False and is then passed to f. It is passed by-value, so in f the parameter my_bool receives the value False. However, this variable my_bool is unrelated to the variable my_bool outside f. So modifying the my_bool in f does not affect the my_bool outside f.

Note that this does not mean that you cannot pass references to objects, only that the reference is passed by-value. Consider the following example:

class MyObject:
  def __init__(self):
    self.x = 13

def f(my_object):
  my_object.x = 17

def g(my_object):
  my_object = MyObject()
  my_object.x = 19

my_object = MyObject()

print(my_object.x)
f(my_object)
print(my_object.x)
g(my_object)
print(my_object.x)

This example prints:

13
17
17

In the global scope, the variable my_object is initialized with an instance of MyObject. The constructor of MyObject initializes the member variable x to 13, which is the first printed value. The my_object variable is then passed to the function f. The variable is passed by-value, so the variable my_object in f is a different variable than the variable my_object in the global scope. However, both point to the same instance of MyObject. So when f sets my_object.x = 17, the next print in the global scope will show this value.

Next, in the global scope the variable my_object is passed to g. Again, the variable is passed by-value, so the variable my_object in g is different from the variable my_object in the global scope, but both point to the same instance of MyObject. In g the my_object variable is then assigned a new instance of MyObject. This does not affect the my_object in the global scope, which still points to the previous instance of MyObject. Therefore, the final print in the global scope will still show the 17 that has been assigned to the x of the first instance of MyObject, not the 19 that was assigned in g to the x in the second instance of MyObject.

So this is why e.g. your color variable is not affected by the same problem as your found_cycle variable. For color, you pass by-value for each call to dfs_visit, as for found_cycle, but you never assign a new value to color in dfs_visit. Therefore, the modifications done to color are done to the same object as pointed to by the original color variable in the cycle_exists function.