# Programmed by Robert Brodin. January 2017. Depth-First Search Algorithms Final Project. I might have gone overboard with the comments, *cough*
def dfs(graph, source):

    """
    Defines a function named DFS with arguments graph, a dictionary (contains keys E and V), and source, the starting point of the graph. The function will use the Depth-First Search Algorithm to find the time it takes to discover the vertice (discoveryTime), and the amount of time it takes to turn to the color black (finishTime). The function will return a dictionary, vertexInfo.
    """

    def adjacentVertex(edge, unwantedVertex):

        """
        Defines a function named adjacentVertex with arguments edge, a list, and the unwantedVertex, an integer. The function finds the other vertex in a list when given a vertex. The function returns an integer.
        """

        for vertice in edge:
            if vertice != unwantedVertex:
                return vertice

    def backTrack(originalSource, currentSource):

        """
        Defines a function named backTrack with arguments originalSource, the source specified at the start of the main function, DFS, and currentSource, the vertex that the finishTime is currently being calculated for. The function will find the finishTime, or the time it takes for the vertex to become black. The function does not return any values, it just edits the main dictionary, vertexInfo. Also, if you noticed, recursion is used. :)
        """

        # Checks if the source equals the currentSource. Is used to check if when backtracking, the currentSource is finally the point you started from originally.

        if originalSource != currentSource:

            # Updates dictionary vertexInfo with finishTime. finishTime is calculated by looking at the first index of the list descendants, and at that descendants finishTime. The currentSource's finishTime is set to it's descendants finishTime plus one. Side note, in our case, we are not adding weight to certain vertices, so the descendants will always have the same finishTime in the case of this problem. Meaning that we can use index 0 of the descendants list to get the finish time.

            vertexInfo[str(currentSource)]['finishTime'] = vertexInfo[str(vertexInfo[str(currentSource)]['descendants'][0])]['finishTime'] + 1

            # Color is set to black, as there are no other undiscovered vertices coming from this vertex.

            vertexInfo[str(currentSource)]['color'] = 'black'

            # Recursion is used to keep backtracking from ancestor to ancestor. It will eventually stop once the backtracking reaches the source.
            backTrack(originalSource, vertexInfo[str(currentSource)]['ancestor'])

    # vertexInfo is used to store information about each vertex. The information contained is the color, finishTime, ancestor, descendants, and discoveryTime.
    vertexInfo = {}

    # List vertexQueue is used to store the vertices connected to the source, and later will be used to store vertices recently discovered.
    vertexQueue = []

    # List discoveredVertices will contain vertices that have been discovered. It will be used to check if vertices have been discovered.
    discoveredVertices = [source]

    # Much like discoveredVertices, list discoveredEdges will contain edges that have been discovered. It will be used to check if edges have been discovered, this list is essential in the backtracking process.
    discoveredEdges = []

    # Loops through each vertex in the graph at key 'V'. Sets up each vertices dictionary. Can be used to tell if one vertex is seperate from the main vertices.
    for vertex in graph['V']:
        vertexInfo[str(vertex)] = {'color': 'white', 'discoveryTime': 0, 'finishTime': 0, 'ancestor': '', 'descendants': []}

    # Loops through each edge in the graph. This loop is used to find each vertice connected to the source. If the source is in the edge, then data is then updated. The sources discoveryTime is set to zero, as it will always be zero, and the discovered vertex is then appended to the list of descendants for the source key.
    for edge in graph["E"]: