0
$\begingroup$

Problem: I need to implement a topological search using the following depth first search code.

Note: The original code comes from here, and this is a problem given in at the end of the chapter.

I'll be honest. On a coding level, I feel pretty lost. I've added line comments to help show what I think each line is doing. While I'm fairly new to the depth first search, I understand how they work on a functional level (as opposed to my limited knowledge of their implementation). I've attempted to add the start vertices and finish times to a list so that I could then sort them later on, but I've had trouble returning that list. So that I could then sort the vertices in decreasing order of finishing time.

Note that while some solutions seem to use a stack, this code does not state the use of a stack explicitly. Rather, the stack is implicit in the recursive call to dfsvisit.

from pythonds.graphs import Graph
# Definitions
# discovery time == iterations it took for the program to find the vertex and turn it gray
# finish time == iterations it took for the program to turn the vertex black
# pred == predecessor indicator

class DFSGraph(Graph):
    def __init__(self):
        super().__init__()
        self.time = 0                       # self has an attribute 'time' (counter) that initiates at 0

    def dfs(self):
        for aVertex in self:            
            aVertex.setColor('white')
            aVertex.setPred(-1)
        for aVertex in self:
            if aVertex.getColor() == 'white':
                self.dfsvisit(aVertex)

    def print_graph(self):
        for key in sorted(list(self.vertices.keys())):
            print(key + str(self.vertices[key].neighbors + " " + str(self.vertices[key].dis)))


    def dfsvisit(self,startVertex):                     # Initiate the visit vunction of the current object (self) at the starting vertex (startVertex)
        finish_times = []                                       # Instantiate the a list to keep finish times for each node
        startVertex.setColor('gray')                    # Set the color of the starting vertex to 'gray' (discovered)
        self.time += 1                                  # Increment the timer
        startVertex.setDiscovery(self.time)             # Assign the discovery time to the current vertex (startVertex)
        for nextVertex in startVertex.getConnections(): # Begin cycling through the connected vertices (nextVertex) of startVertex
            if nextVertex.getColor() == 'white':        # If a vertex (nextVertex) with the attribute color of white is found, then do the following:
                nextVertex.setPred(startVertex)         # Set the predecessor indicator of the next vertex as the current vertex (ie if B is white and connected to A, set B's predecessor as A)
                self.dfsvisit(nextVertex)               # Recursively calls itself with the next vertex until the color of the next vertex is no longer white (i.e. all have been explored)
        startVertex.setColor('black')                   # Set the current vertice's color to black (explored)
        self.time += 1                                  # Increment the timec counter
        startVertex.setFinish(self.time)                # Assign the finish time to the current vertex (startVertex)
        finish_time = [startVertex, startVertex.setFinish(self.time)]  # append vertex and finish times to finish_time list
        return finish_time                                             # return the finish_time list

Again, I'm hoping to understand how to implement the topological search either within this code.

$\endgroup$
3
  • $\begingroup$ Do you mean topological sort? $\endgroup$ Sep 2, 2019 at 22:12
  • $\begingroup$ "End of the chapter" of what? $\endgroup$ Sep 2, 2019 at 22:12
  • $\begingroup$ My apologies @BrianSpiering. Yes, topological sort, and the 'end of chapter' referred to this link that didn't copy over for me. $\endgroup$
    – alofgran
    Sep 2, 2019 at 22:38

1 Answer 1

1
$\begingroup$

It appears to me that you are doing too much with the code. For DFS, visit every node following adjacent nodes. As you do that, track the topological ordering.

Here is a straightforward implementation of recursive topological sorting a DAG in Python:

from collections import defaultdict 

class Graph: 

    def __init__(self): 
        self.graph = defaultdict(list) # Node: [adjacency nodes]
        self.nodes = set()

    def add_edge(self, u, v): 
        "Directed edge from vertex u to vertex v"
        self.graph[u].append(v) 
        self.nodes.add(u)
        self.nodes.add(v)

    def mark_as_visited(self, v, visited, topological_ordering): 
        visited[v] = True

        # Recur for all the vertices adjacent to this vertex 
        for current_vertex in self.graph[v]: 
            if visited[current_vertex] == False: 
                self.mark_as_visited(current_vertex, visited, topological_ordering) 

        topological_ordering.insert(0, v) 

    def topological_sort(self): 

        visited = [False]*len(self.nodes) # Mark all the vertices as not visited 
        topological_ordering = [] 

        # Sort starting from all vertices one by one 
        for i in range(len(self.nodes)): 
            if visited[i] == False: 
                self.mark_as_visited(i, visited, topological_ordering) 

        return topological_ordering
# Create a sample DAG
g = Graph() 
g.add_edge(5, 2) 
g.add_edge(5, 0) 
g.add_edge(4, 0) 
g.add_edge(4, 1) 
g.add_edge(2, 3) 
g.add_edge(3, 1) 

# Double check that the algorithm is correct for that DAG
assert g.topological_sort() == [5, 4, 2, 3, 1, 0]
$\endgroup$
1
  • $\begingroup$ thanks for the response - this is as close as I've come thus far. However, the code (which doesn't come from me) is what needs to be modified (as opposed to being recreated, as you did). I'll continue to attempt to adapt your solution to the code in my question. Thanks $\endgroup$
    – alofgran
    Sep 5, 2019 at 1:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.