<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Tasks in Order
Chapter 6 of Real World Algorithms.
Panos Louridas<br />
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.
Step1:  As, an example, let's see dfs() in action on the following graph.
<img width="400" src="topological_sort_graph.png"/>
The graph is represented in Python as follows
Step2:  We start by initializing positions and visited and running dfs(g, node, positions, visited) from node 0.
Step3:  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.
Step4:  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.
Step5:  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.
Step6:  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.
Step7:  Then we continue from node 8
Step8:  And we wrap up with node 10
Step9:  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.
Step10:  We can test it directly on our graph
Step11:  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.
Step12:  We can verify that we produce correct results.
Step13:  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
Step14:  We can test it on weighted_graph.txt to see what we get
Step15:  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.
Step16:  We can test this one too on weighted_graph.txt to see what we get
Step17:  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
Step18:  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
Step19:  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.
Step20:  After reading the graph from the file, g contains the adjacency lists
Step21:  The dictionary w contains the weights
Step22:  We can proceed with finding the critical path.
Step23:  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.
Step24:  Of course, it is not difficult to write a little function that we'll do that lookup up for us
Step25:  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
<ASSISTANT_TASK:>
Python Code:
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)
Explanation: Tasks in Order
Chapter 6 of Real World Algorithms.
Panos Louridas<br />
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.
End of explanation
g = {
    0: [1, 3],
    1: [2],
    2: [],
    3: [4],
    4: [2, 5],
    5: [],
    6: [3, 7],
    7: [],
    8: [6, 9],
    9: [7],
    10: []
}
Explanation: As, an example, let's see dfs() in action on the following graph.
<img width="400" src="topological_sort_graph.png"/>
The graph is represented in Python as follows:
End of explanation
positions = []
visited = [ False ] * len(g)
dfs(g, 0, positions, visited)
print(positions)
Explanation: We start by initializing positions and visited and running dfs(g, node, positions, visited) from node 0.
End of explanation
dfs(g, 6, positions, visited)
print(positions)
Explanation: 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.
End of explanation
dfs(g, 8, positions, visited)
print(positions)
Explanation: 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.
End of explanation
dfs(g, 10, positions, visited)
print(positions)
Explanation: 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.
End of explanation
positions = []
visited = [ False ] * len(g)
dfs(g, 0, positions, visited)
print(positions)
Explanation: 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.
End of explanation
dfs(g, 8, positions, visited)
print(positions)
Explanation: Then we continue from node 8:
End of explanation
dfs(g, 10, positions, visited)
print(positions)
Explanation: And we wrap up with node 10:
End of explanation
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
Explanation: 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.
End of explanation
topologically_sorted_nodes = topological_sort(g)
print(topologically_sorted_nodes)
Explanation: We can test it directly on our graph:
End of explanation
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
Explanation: 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.
End of explanation
topologically_sorted_nodes = topological_sort(g)
print(topologically_sorted_nodes)
Explanation: We can verify that we produce correct results.
End of explanation
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
Explanation: 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:
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:
<img width="400" src="weighted_graph.png"/>
End of explanation
import pprint
g = read_weighted_graph('weighted_graph.txt')
pprint.pprint(g)
Explanation: We can test it on weighted_graph.txt to see what we get:
End of explanation
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)
Explanation: 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.
End of explanation
g, w = read_weighted_graph_wm('weighted_graph.txt')
pprint.pprint(g)
pprint.pprint(w)
Explanation: We can test this one too on weighted_graph.txt to see what we get:
End of explanation
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)
Explanation: 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:
<img width="400" src="task_scheduling_graph.png"/>
We want to transform it to this one:
<img width="500" src="task_scheduling_graph_s_t.png"/>
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.
End of explanation
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)
Explanation: 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.
End of explanation
g, w = read_weighted_graph_wm('task_scheduling_graph.txt')
Explanation: 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.
End of explanation
pprint.pprint(g)
Explanation: After reading the graph from the file, g contains the adjacency lists:
End of explanation
pprint.pprint(w)
Explanation: The dictionary w contains the weights:
End of explanation
pred, dist = critical_path(g, w)
print('pred', pred)
print('dist', dist)
Explanation: We can proceed with finding the critical path.
End of explanation
print('Critical path length =', dist[-1])
Explanation: 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.
End of explanation
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))
Explanation: Of course, it is not difficult to write a little function that we'll do that lookup up for us:
End of explanation
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))
Explanation: 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:
End of explanation
<END_TASK>