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...
