Chapter 6 of Real World Algorithms.

Panos Louridas

Athens University of Economics and Business

Topological sort is based on depth-first search.

We want to visit the nodes in a graph so that we visit each node before any of the nodes that the node we are visiting points to.

To do that, we do a depth-first search and each time we arrive at a dead-end we add that node in the head of a list.

In this way we will fill a list from the back to the front.

When the depth-first search is over, the list will contain the nodes of the graph topologicallly sorted.

The following function is depth-first search, with that additional list.

So, apart from the graph `g`

, the starting node `node`

and an array `visited`

marking the nodes that we have visited, we pass to the function a list `position`

that we will be filling back-to-front.

This happens by calling `positions.insert(0, node)`

, which puts `node`

at the head of the list.

In [1]:

```
def dfs(g, node, positions, visited):
visited[node] = True
for v in g[node]:
if not visited[v]:
dfs(g, v, positions, visited)
positions.insert(0, node)
```

As, an example, let's see `dfs()`

in action on the following graph.

The graph is represented in Python as follows:

In [2]:

```
g = {
0: [1, 3],
1: [2],
2: [],
3: [4],
4: [2, 5],
5: [],
6: [3, 7],
7: [],
8: [6, 9],
9: [7],
10: []
}
```

`positions`

and `visited`

and running `dfs(g, node, positions, visited)`

from node 0.

In [3]:

```
positions = []
visited = [ False ] * len(g)
dfs(g, 0, positions, visited)
print(positions)
```

[0, 3, 4, 5, 1, 2]

We see that we have not visited all the nodes in the graph. That is because not all nodes are reachable from node 0.

So we call again `dfs(g, node, positions, visited)`

, this time starting from node 6.

In [4]:

```
dfs(g, 6, positions, visited)
print(positions)
```

[6, 7, 0, 3, 4, 5, 1, 2]

Again, we have not visited the whole graph, because nodes 8, 9, and 10 were not reachable.

So we finish by calling `dfs(g, node, positions, visited)`

from node 8.

In [5]:

```
dfs(g, 8, positions, visited)
print(positions)
```

[8, 9, 6, 7, 0, 3, 4, 5, 1, 2]

We still have not visited the whole graph, as node 10 is unreachable.

So we finish by calling `dfs(g, node, positions, visited)`

from node 10. Yes, this is trivial, but we should do it to complete the exploration.

When we finish, the `positions`

list contains the nodes in topological sort.

In [6]:

```
dfs(g, 10, positions, visited)
print(positions)
```

[10, 8, 9, 6, 7, 0, 3, 4, 5, 1, 2]

Note that we could have started from node 0, and then begin a new exploration from node 8, and then go to 10.

Indeed, let's see what happens.

We need to initialize `positions`

and `visited`

again before we start.

In [7]:

```
positions = []
visited = [ False ] * len(g)
dfs(g, 0, positions, visited)
print(positions)
```

[0, 3, 4, 5, 1, 2]

Then we continue from node 8:

In [8]:

```
dfs(g, 8, positions, visited)
print(positions)
```

[8, 9, 6, 7, 0, 3, 4, 5, 1, 2]

And we wrap up with node 10:

In [9]:

```
dfs(g, 10, positions, visited)
print(positions)
```

[10, 8, 9, 6, 7, 0, 3, 4, 5, 1, 2]

Our steps show us how topolotical sort should be implemented.

Just call `dfs()`

enough times to cover the whole graph.

That is what we do in the following function.

Starting from node 0, we perform as many depth-first searches as needed to make sure that no node is left unvisited.

In [10]:

```
def topological_sort(g):
positions = []
visited = [ False ] * len(g)
num_nodes = len(g)
for i in range(num_nodes):
if not visited[i]:
dfs(g, i, positions, visited)
return positions
```

We can test it directly on our graph:

In [11]:

```
topologically_sorted_nodes = topological_sort(g)
print(topologically_sorted_nodes)
```

[10, 8, 9, 6, 7, 0, 3, 4, 5, 1, 2]

Note that in Python, inserting at the front of a list is slower than appending at the end.

So if we wanted a more efficient implementation, we would add items at the end of `positions`

and then we would just reverse the result.

In [12]:

```
def dfs(g, node, positions, visited):
visited[node] = True
for v in g[node]:
if not visited[v]:
dfs(g, v, positions, visited)
positions.append(node)
def topological_sort(g):
positions = []
visited = [ False ] * len(g)
num_nodes = len(g.keys())
for i in range(num_nodes):
if not visited[i]:
dfs(g, i, positions, visited)
positions.reverse()
return positions
```

We can verify that we produce correct results.

In [13]:

```
topologically_sorted_nodes = topological_sort(g)
print(topologically_sorted_nodes)
```

[10, 8, 9, 6, 7, 0, 3, 4, 5, 1, 2]

In *weighted graphs* we associate a weight with each edge.

We can think of unweighted graphs as weighted graphs in which every edge has weight equal to one.

We can represented weighted graphs with adjacency matrices or with adjacency lists.

In adjacency matrices we store the weight of edge $(v, u)$ at the cell at position $(v, u)$ of the matrix.

In adjacency lists we store the weight along with each link.

The following function reads a directed weighted graph from a text file.

The text file contains an edge in each line and its weight.

An example file is weighted_graph.txt:

```
0 1 10
0 3 4
1 2 7
1 5 5
2 3 0
2 4 9
3 4 8
4 5 1
```

It corresponds to the following graph:

In [14]:

```
def read_weighted_graph(filename):
graph = {}
with open(filename) as input_file:
for line in input_file:
[n1, n2, w] = [ int (x) for x in line.split() ]
if n1 not in graph:
graph[n1] = []
if n2 not in graph:
graph[n2] = []
graph[n1].append((n2, w))
return graph
```

We can test it on weighted_graph.txt to see what we get:

In [15]:

```
import pprint
g = read_weighted_graph('weighted_graph.txt')
pprint.pprint(g)
```

{0: [(1, 10), (3, 4)], 1: [(2, 7), (5, 5)], 2: [(3, 0), (4, 9)], 3: [(4, 8)], 4: [(5, 1)], 5: []}

Adjancency lists now contain *tuples*.

The first element of each tuple is the node, the second is the weight of the corresponding link.

Note that we append to each list, so that the tuples in the list are in the reverse order than in Figure 6.7 in the book.

That does not matter. If we want, we can change `graph[n1].append((n2, w))`

to `graph[n1].insert(0, (n2, w))`

, but that would be less efficient as appending at the end of a list is faster in Python.

There is another way to represent weighted graphs.

We just keep the adjacency lists the same with unweighted graphs, and we use a map to hold the weight for each edge.

Let's write a function `read_weighted_graph_wm(filename)`

(wm stands for weighs' map) that does that.

The function will return the adjacency list representation of a graph *and* a map associating edges with weights.

This representation has the advantage that we can use it directly with our depth-first search and topological sort implementations, which expect simple adjacency lists without weights.

In [16]:

```
def read_weighted_graph_wm(filename):
graph = {}
weights = {}
with open(filename) as input_file:
for line in input_file:
[n1, n2, w] = [ int (x) for x in line.split() ]
if n1 not in graph:
graph[n1] = []
if n2 not in graph:
graph[n2] = []
graph[n1].append(n2)
weights[(n1, n2)] = w
return (graph, weights)
```

We can test this one too on weighted_graph.txt to see what we get:

In [17]:

```
g, w = read_weighted_graph_wm('weighted_graph.txt')
pprint.pprint(g)
pprint.pprint(w)
```

Finding the critical path in a graph is an application of topological sorting.

But before we really start looking for the critical path, we need to adjust the graph so that it has a *source* and a *sink*.

The source is a node that precedes all other nodes. It is a node that we add with links pointing to any nodes that are not the destination of any existing edge.

The target is a node that follows all other nodes. It is a node that we add with links from any nodes that do not point to any other node.

That means that if we have the following graph:

We want to transform it to this one:

That is not difficult to do.

We'll start by finding the nodes that are pointed to by other nodes.

We'll use them to find the nodes that are *not* pointed to by any other nodes. We can do that by taking the set difference between the set of all nodes and the set of the nodes pointed to by other nodes.

Then we'll find the nodes that point nowhere; that's the nodes with an empty adjacency list.

And then we'll add the source and the sink nodes.

If $n$ is the number of nodes in the graph (from $0$ to $n - 1$), we'll call $n$ the source node and $n+1$ the sink node.

In [18]:

```
def add_source_sink(g):
# Find the nodes that no node points to them.
# To do that, we need first to find the nodes
# that are pointed to by other nodes.
to_nodes = { v for u in g.keys() for v in g[u] }
# Then we just take the difference with
# the full set of nodes.
no_previous = g.keys() - to_nodes
# Find the nodes that point nowhere.
# That is easy, we just need to find those with
# an empty adjacency list.
no_next = { u for u in g.keys() if len(g[u]) == 0 }
# Get the number of nodes in the graph.
num_nodes = len(g.keys())
# Add source node.
# As num_nodes is the number of nodes in the graph,
# we can use it as the name of the source node.
source = num_nodes
g[source] = [ u for u in no_previous ] # all zero weights
num_nodes += 1
# Add sink node.
# Again, we can use num_nodes (which we increased by one)
# as the name of the target node.
sink = num_nodes
g[sink] = [ ]
for node in no_next:
g[node].append(sink) # all zero weights
return (source, sink)
```

With `add_source_sink(g)`

at hand, we can proceed to implement the function that finds the critical path.

As a first step, it will call `add_source_sink(g)`

to our graph.

The function will return two lists:

- The first list will have at each position $i$ the predecessor of the node $i$ in the critical path.
- The second list will have at each position $i$ the distance of node $i$ from the source in the critical path.

We will initialize both to -1.

Then finding the critical path is only a matter of relaxation of the distances from -1 to larger values.

We will use the second representation of a weighted graph with two structures, one for the adjacency lists and one for the weights.

This allows us not to introduce explicit zero weights for the edges of the source and the sink nodes.

We use the `get(k, default)`

method of dictionaries, which returns the value associated with the key `k`

, if it exists, or the value that we supply as `default`

, otherwise.

In [19]:

```
def critical_path(g, w):
source, sink = add_source_sink(g)
n = len(g.keys())
pred = [ -1 ] * n # list of predecessors in critical path
dist = [ -1 ] * n # list of distances to nodes
dist[source] = 0 # correct distance to source to 0
tsorted = topological_sort(g)
for u in tsorted:
for v in g[u]:
if dist[v] < dist[u] + w.get((u, v), 0):
dist[v] = dist[u] + w.get((u, v), 0)
pred[v] = u
return (pred, dist)
```

In [20]:

```
g, w = read_weighted_graph_wm('task_scheduling_graph.txt')
```

After reading the graph from the file, `g`

contains the adjacency lists:

In [21]:

```
pprint.pprint(g)
```

The dictionary `w`

contains the weights:

In [22]:

```
pprint.pprint(w)
```

We can proceed with finding the critical path.

In [23]:

```
pred, dist = critical_path(g, w)
print('pred', pred)
print('dist', dist)
```

So we see that the predecessor of node 0 is node 12, which is the source node, which has no predecessor (-1).

Similarly, the predecessor of node 13, the sink node, is node 4, whose predecessor is node 3, whose predecessor is node 7, and so on.

The length of the critical path is the last element of `dist`

.

In [24]:

```
print('Critical path length =', dist[-1])
```

Critical path length = 56

Of course, it is not difficult to write a little function that we'll do that lookup up for us:

In [25]:

```
def get_critical_path(pred):
path = []
t = len(pred) - 1 # position of sink node
while t != -1:
path.insert(0, t)
t = pred[t]
return path
print(get_critical_path(pred))
```

[12, 5, 6, 7, 3, 4, 13]

`len(pred) - 1`

.

Recall also that in Python it is more efficient to append items at the end of the list rather than inserting in the beginning.

So we could rewrite `get_critical_path()`

as follows:

In [26]:

```
def get_critical_path(pred):
path = []
t = len(pred) - 1
while t != -1:
path.append(t)
t = pred[t]
path.reverse()
return path
print(get_critical_path(pred))
```

[12, 5, 6, 7, 3, 4, 13]