Tasks in Order

Panos Louridas
Athens University of Economics and Business

Topological Sort

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: []
}

We start by initializing 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]

Weighted Graphs

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:

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)









    



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

Critical Paths

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)

To check our implementation, we can use the task_scheduling_graph.txt file, which is the graph that we used as an example for adding a source and a sink.



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)









    



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

The dictionary w contains the weights:



In [22]:

    
pprint.pprint(w)









    



{(0, 1): 17,
 (1, 2): 13,
 (2, 3): 9,
 (3, 4): 11,
 (3, 8): 10,
 (5, 6): 11,
 (5, 9): 15,
 (6, 7): 18,
 (7, 3): 16,
 (7, 8): 13,
 (7, 11): 19,
 (9, 10): 14,
 (10, 11): 17}

We can proceed with finding the critical path.



In [23]:

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









    



pred [12, 0, 1, 7, 3, 12, 5, 6, 3, 5, 9, 7, -1, 4]
dist [0, 17, 30, 45, 56, 0, 11, 29, 55, 15, 29, 48, 0, 56]

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]

Remember that we named the source node $n$ and the sink node $n+1$, where $n$ is the number of nodes in the initial graph, so the sink node is at position 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]