Conducting a topological sort on a graph

If a graph is directed, the topological sort is one of the natural orderings of the graph. In a network of dependencies, the topological sort will reveal a possible enumeration through all the vertices that satisfy such dependencies.

Haskell's built-in graph package comes with a very useful function, topSort, to conduct a topological sort over a graph. In this recipe, we will be creating a graph of dependencies and enumerating a topological sort through it.

Getting ready

We will be reading the data from the user input. Each pair of lines will represent a dependency.

Create a file input.txt with the following pairs of lines:

$ cat input.txt

understand Haskell
do Haskell data analysis
understand data analysis
do Haskell data analysis
do Haskell data analysis
find patterns in big data

This file describes a list of dependencies, which are as follows:

• One must understand Haskell in order to do Haskell data analysis

• One must understand data analysis to do Haskell...