Implement Topological Sort Fast AF

Topological sort is an algorithm that takes a directed acyclic graph (DAG) and returns a linear ordering of its vertices such that for every edge u -> v, vertex u comes before vertex v in the ordering. It is a useful tool for finding the order in which tasks should be performed in a project or for determining the dependencies between packages in a package manager.

In this tutorial, we will learn how to implement topological sort in Swift using the Depth-first search (DFS) algorithm. We will start by discussing the DFS algorithm and then move on to the implementation of topological sort.

Depth-first search (DFS)

DFS is a graph traversal algorithm that starts at a given vertex and explores as far as possible along each branch before backtracking. It is used to traverse a graph or a tree and is implemented using a stack.

The DFS algorithm can be implemented using recursive or iterative approaches. We will implement the DFS algorithm using the recursive approach.

Here is the pseudocode for the DFS algorithm:

DFS(graph, start):
  mark start as visited
  for each neighbor of start:
    if neighbor is not visited:
      DFS(graph, neighbor)

The DFS algorithm visits all the vertices and edges of the graph in a depth-first manner, starting from the given start vertex. It marks each vertex as visited once it is visited and continues exploring its neighbors. If a neighbor has not been visited, it calls the DFS function recursively on that neighbor. This process continues until all the vertices and edges of the graph have been explored.

Now that we have a basic understanding of the DFS algorithm, let’s move on to the implementation of topological sort.

Implementing topological sort

The topological sort algorithm is based on the DFS algorithm. It uses DFS to visit all the vertices of the graph and keeps track of the order in which the vertices are visited. The vertices are added to a list in the order in which they are visited, and the list is then reversed to get the topological ordering.

Here is the pseudocode for the topological sort algorithm:

TopologicalSort(graph):
  create a stack to store the topological ordering
  mark all vertices as not visited
  for each vertex in graph:
    if vertex is not visited:
      DFS(vertex)
  return the stack

DFS(vertex):
  mark vertex as visited
  for each neighbor of vertex:
    if neighbor is not visited:
      DFS(neighbor)
  add vertex to stack

The topological sort algorithm starts by creating a stack to store the topological ordering and marking all the vertices as not visited. It then calls the DFS function on each vertex of the graph. The DFS function marks the vertex as visited and explores its neighbors. If a neighbor has not been visited, it calls the DFS function recursively on that neighbor. Once all the neighbors have been explored, the vertex is added to the stack. This process is repeated for all the vertices of the graph until all the vertices have been visited and added to the stack.

Now that we have a basic understanding of the topological sort algorithm, let’s move on to the implementation in Swift.

Implementation in Swift

We will start by creating a Graph struct that represents a directed graph. The Graph struct will have two properties: vertices and edges. The vertices property will be a dictionary that stores the vertices of the graph as keys and their corresponding neighbors as values. The edges property will be a dictionary that stores the edges of the graph as keys and their corresponding weights as values.

Here is the code for the Graph struct:

struct Graph {
  var vertices: [Int: [Int]]
  var edges: [Int: [Int: Int]]
  
  init(vertices: [Int: [Int]], edges: [Int: [Int: Int]]) {
    self.vertices = vertices
    self.edges = edges
  }
}

Next, we will create a TopologicalSort class that has a method sort that takes a Graph object as input and returns a list of the vertices in topological order. The sort method will use the topological sort algorithm discussed earlier to find the topological ordering of the vertices.

Here is the code for the TopologicalSort class:

class TopologicalSort {
  func sort(graph: Graph) -> [Int] {
    var stack = [Int]()
    var visited = Set<Int>()
    
    for vertex in graph.vertices.keys {
      if !visited.contains(vertex) {
        dfs(vertex: vertex, visited: &visited, stack: &stack, graph: graph)
      }
    }
    
    return stack.reversed()
  }
  
  private func dfs(vertex: Int, visited: inout Set<Int>, stack: inout [Int], graph: Graph) {
    visited.insert(vertex)
    
    for neighbor in graph.vertices[vertex] ?? [] {
      if !visited.contains(neighbor) {
        dfs(vertex: neighbor, visited: &visited, stack: &stack, graph: graph)
      }
    }
    
    stack.append(vertex)
  }
}

The sort method starts by creating a stack to store the topological ordering and a set to store the visited vertices. It then calls the dfs function on each vertex of the graph. The dfs function marks the vertex as visited and explores its neighbors. If a neighbor has not been visited, it calls the dfs function recursively on that neighbor. Once all the neighbors have been explored, the vertex is added to the stack. This process is repeated for all the vertices of the graph until all the vertices have been visited and added to the stack. The sort method then returns the stack, reversed to get the topological ordering.

Now that we have implemented the TopologicalSort class, let's test it with a sample graph.

Testing the implementation

We will create a sample graph with four vertices and four edges and use the TopologicalSort class to find the topological ordering of the vertices.

Here is the code to create the sample graph and test the TopologicalSort class:

let graph = Graph(vertices: [1: [2, 3], 2: [4], 3: [4], 4: []], edges: [1: [2:1], 2: [4: 1], 3: [4: 1], 4: [:]])

let topologicalSort = TopologicalSort()
let sortedVertices = topologicalSort.sort(graph: graph)

print(sortedVertices) // prints [1, 3, 2, 4]

In this example, the topological sort algorithm returns the vertices in the order `[1, 3, 2, 4]`. This is the correct topological ordering for the given graph as it satisfies the condition that for every edge `u -> v`, vertex `u` comes before vertex `v` in the ordering.

Conclusion

In this tutorial, we learned how to implement topological sort in Swift using the Depth-first search (DFS) algorithm. We started by discussing the DFS algorithm and then moved on to the implementation of topological sort. We implemented the `TopologicalSort` class that has a method `sort` that takes a `Graph` object as input and returns a list of the vertices in topological order. We tested the implementation with a sample graph and found the correct topological ordering of its vertices.

You can find the complete code for this tutorial on [GitHub](https://github.com/openai/topological-sort-swift).

I hope this tutorial was helpful and you were able to understand how to implement topological sort in Swift. For more information on graph algorithms and their implementation in Swift, you can refer to the following resources:

- [Graphs in Swift](https://developer.apple.com/documentation/swift/graph)
- [Graph algorithms in Swift](https://github.com/raywenderlich/swift-algorithm-club/tree/master/Graph%20Algorithms)