1. Introduction

Topological ordering is a fundamental concept in graph theory and is particularly applied to Directed Acyclic Graphs (DAGs). The algorithm for obtaining a topological order was introduced by Robert Tarjan in 1976.

Topological ordering(topological sort) of a G(V,E) directed graph is a linear ordering of its vertices such that for every directed (u,v) edge, u comes before v in the ordering.

Topological ordering makes sense only with directed graphs. In an undirected graph, there are no directed edges to impose such constraints. As a result, there is no concept of “before” or “after” between vertices. In an undirected graph: A–B–C you can traverse in any order, as there are no directional constraints.

Topological ordering has many applications. The vertices of a graph can represent tasks that need to be completed, while the edges represent dependencies or constraints between these tasks. For instance, in project management, it’s common to encounter situations where certain tasks must be completed before others can begin. By representing such scenarios using a directed graph, we can model these dependencies effectively. A topological ordering of the graph provides a valid sequence in which the tasks can be performed, respecting all the constraints. This makes topological ordering an essential tool in project management for planning and organizing tasks systematically.

We can use topological ordering only if the G(V,E) graph (with V vertex and E edges) does not have any cycles. So it is a directed acyclic graph (DAG). Any directed acyclic graph has at least one topological order.

Note: Any directed cyclic graph has at least one toplogical order.

For example, following is an example of directed cyclic graph. In this case we can’t use topological ordering.

• Topological ordering has O(V+E) runtime complexity.
• Topological ordering is crucial in finding Hamiltonian paths. A Hamiltonian Path in a graph is a path that visits each vertex of the graph exactly once. Unlike a Hamiltonian Cycle, the path does not need to return to the starting vertex. If a Hamiltonian path exists then the topological sort order is unique.
• If the topological order does not form a Hamiltonian path then it means there are multiple topological order for a given graph.
• Finding a Hamiltonian Path is indeed NP-complete, meaning that no known polynomial-time algorithm can solve the problem for all graphs. However, in Directed Acyclic Graphs (DAGs), we can efficiently decide whether a Hamiltonian Path exists using topological ordering in O(V+E) time.

2. Steps to find topological ordering of a graph

We’ll now find the topological order of a graph.

• Step 1: This is our graph. We have to make sure that the given graph has directed edges. In this graph, every single edge has a direction and there are no cycles. In each iteration we have to find V vertices with no incoming edges in the G(V,E) graph. So we are going to make as many iterations as the number of vertices in the graph. In every single iteration we are going to choose the vertex with no incoming edges.

• Step 2: Since in this graph, vertex A has no incoming edges so this will be our first vertex. Once a vertex is considered, it must be removed from the current graph to ensure the next vertex can be identified in the subsequent iteration. It is possible that there may be multiple such vertex with no incoming edges. So there may be multiple solution of topological ordering.

• Step 3: Since in this graph, vertex B has no incoming edges so this will be our next vertex. We’ll remove vertex B and it’s edges.

• Step 4: Since in this graph, vertex E has no incoming edges so this will be our next vertex. We’ll remove vertex E and it’s edges.

• Step 5: Since in this graph, vertex C has no incoming edges so this will be our next vertex. We’ll remove vertex C and it’s edges.

• Step 6: Finally, we have vertex D.

This is how we can find the topological order of a given graph.

3. Applications of topological order

Topological order has several practical applications, particularly in scenarios involving directed acyclic graphs (DAGs). Here are some common applications:

• Dependency Resolution
  • Build Systems: Determine the order in which tasks or files should be processed, such as resolving dependencies in build tools like Make or Maven.
  • Package Installation: Resolve dependencies between software packages to ensure correct installation order.
• Task Scheduling
  • Used to schedule tasks with dependencies, such as project management or workflow systems, where certain tasks must be completed before others can start.
• Course Prerequisites
  • In academic course planning, topological order can be used to determine the sequence of courses a student must take based on prerequisite requirements.
• Compiler Design
  • In compiler construction, topological sorting helps with instruction scheduling and identifying execution order for intermediate code generation.
• Dependency Analysis in Graphs
  • Analyze dependencies in various systems like circuits, software, or networks to identify possible sequences of operations.
• Deadlock Prevention
  • Used in operating systems to avoid deadlocks by ordering resource allocation requests in a way that prevents circular waits.
• Data Pipelines
  • In workflows such as ETL (Extract, Transform, Load) processes, where certain steps depend on the completion of others, topological order helps determine the sequence of operations.
• Version Control Systems
  • Used in systems like Git to order commits or revisions based on their dependencies for operations like rebasing or merging.
• Knowledge Representation
  • In knowledge graphs or ontologies, topological order can represent prerequisite relationships among concepts.
• Game Development
  • To manage game logic where certain game elements depend on others, such as solving puzzles or updating game states.

4. Implementation

Now, we’ll see the implementation of topological ordering. We’ll find the topological order of the following graph:

Vertex.java

import java.util.ArrayList;
import java.util.List;

public class Vertex {
    private String name;
    private boolean visited;
    private List<Vertex> neighborList;

    public Vertex(String name){
        this.name = name;
        this.neighborList = new ArrayList<>();
    }

    public void addNeighbor(Vertex vertex){
        this.neighborList.add(vertex);
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public boolean isVisited() {
        return visited;
    }

    public void setVisited(boolean visited) {
        this.visited = visited;
    }

    public List<Vertex> getNeighborList() {
        return neighborList;
    }

    @Override
    public String toString() {
        return "Vertex{name='" + name + "'}";
    }
}

TopologicalOrdering.java

import java.util.Stack;

public class TopologicalOrdering {

    private Stack<Vertex> stack;

    public TopologicalOrdering(){
        this.stack = new Stack<>();
    }

    public void dfs(Vertex vertex){
        vertex.setVisited(true);

        //for all the neighbors of a vertex
        for(Vertex v: vertex.getNeighborList()){
            if(!v.isVisited()){
                dfs(v);
            }
        }
        stack.push(vertex);
    }

    public Stack<Vertex> getStack(){
        return this.stack;
    }
}

App.java

import java.util.List;
import java.util.ArrayList;
import java.util.Stack;

public class App {
    public static void main(String args[]){
        TopologicalOrdering topologicalOrdering = new TopologicalOrdering();

        List<Vertex> graph = new ArrayList<>();

        graph.add(new Vertex("0"));
        graph.add(new Vertex("1"));
        graph.add(new Vertex("2"));
        graph.add(new Vertex("3"));
        graph.add(new Vertex("4"));
        graph.add(new Vertex("5"));

        graph.get(2).addNeighbor(graph.get(3));
        graph.get(3).addNeighbor(graph.get(1));

        graph.get(4).addNeighbor(graph.get(0));
        graph.get(4).addNeighbor(graph.get(2));

        for(int i=0; i<graph.size();++i){
            if(!graph.get(i).isVisited()){
                topologicalOrdering.dfs(graph.get(i));
            }
        }
        Stack<Vertex> stack = topologicalOrdering.getStack();

        for(int i=0;i<graph.size();i++){
            System.out.println(stack.pop());
        }
    }
}

Output

Vertex{name='5'}
Vertex{name='4'}
Vertex{name='2'}
Vertex{name='3'}
Vertex{name='1'}
Vertex{name='0'}

Let us understand the output.

• Since ‘5’ has outgoing edges to ‘0’ and ‘2’, ‘5’ must precede ‘0’ and ‘2’.
• Since ‘4’ has outgoing edges to ‘1’ and ‘0’, ‘4’ mush precede ‘1’ and ‘0’.
• Since ‘2’ has outgoing edge to ‘3’, ‘2’ must precede ‘3’.
• Since ‘3’ has outgoing edge to ‘1’, ‘3’ must precede ‘1’.

And therefore, we have this topological order 5-4-2-3-1-0.

6. Dynamic programming with topological sort

Dynamic Programming (DP) is a technique for solving complex problems by breaking them down into simpler subproblems. It is particularly useful for optimization problems where the solution can be constructed from solutions to overlapping subproblems. The main idea is to store the results of solved subproblems to avoid redundant computations, which significantly improves efficiency.

It was introduced by Richard Bellman in 1953.

Dynamic programming uses memoization or tabulation to store the values so there is no need for recalculation.

We can use dynamic programming if the problem has an optimal substructure. Optimal Substructure is a property of a problem that allows an optimal solution to the overall problem to be constructed from the optimal solutions of its subproblems. In simpler terms, if solving smaller subproblems optimally guarantees the solution to the larger problem is also optimal, the problem exhibits optimal substructure. The Bellman Equation is a fundamental concept in dynamic programming and optimization, especially in problems involving sequential decision-making. It expresses the principle of optimality, which states that the optimal solution of a problem can be constructed using the optimal solutions of its subproblems.

There is a fascinating connection between dynamic programming problems and directed acyclic graphs (DAGs).

Many dynamic programming problems can be represented as graphs, and importantly, these graphs often take the form of DAGs. This structure is crucial because it allows us to solve the problem by computing the shortest or longest path on the graph.

By transforming dynamic programming problems into DAGs, we can leverage the graph’s acyclic nature to systematically compute solutions, making it easier to address the original problem efficiently.

5. Conclusion

Topological ordering is a powerful tool for solving problems in directed acyclic graphs (DAGs) where the sequence of tasks, events, or dependencies matters. By arranging the vertices in a linear order such that every directed edge u→vu \to vu→v implies uuu comes before vvv, we can effectively resolve dependencies and ensure proper execution of workflows.

This concept finds applications in diverse domains such as project scheduling, compiler design, dependency resolution, and more. Understanding how to compute and utilize topological ordering equips you with a fundamental technique to approach and solve real-world problems involving dependencies.