Implement in a new file toposort.cc the function TopologicalSort() described in file toposort.h,
which uses the DirectedGraph class seen in Session 1 for directed graphs (a reference implementation is inside the test.tar.gz archive, so it should be
readily available in your working directory, but you can also decide to use your own
implementation as long as you respected the interface):
#ifndef __TOPOSORT_H
#define __TOPOSORT_H
#include "graph.h"
#include <vector>
using namespace std;
// Perform a topological sort of the given directed graph, and returns the
// indices of the nodes, sorted in that topological order: "leaves"
// (nodes that don't have any outgoing arcs) will be in the beginning.
// If the graph has a cycle (i.e. it's not a DAG, hence there is no
// topological order), this function must return the empty vector.
//
// HINTS/NOTES:
// - Often, several different topological orders exist and are valid.
// - Since the input graph gives you the list of children of a node, and
// you need the list of parents in the algorithm, you have 2 options:
// a) precompute that list of parents, for each node
// b) perform the 'inverse' topological sort, where one start with nodes
// that have no parent (instead of nodes with 0 children); then reverse
// the final order.
// - One may precompute the "residual degree" of each node (in-degree or out-
// degree, depending on the option you chose before), and initialise a simple
// queue (vector<int> for LIFO order, queue<int> for FIFO order)
// that'll contain all the node of residual degree 0, and dynamically updated.
// - The overall time complexity must be O(M+N) (number of arcs + number of nodes).
//
// Example:
//
// 2-->5-->6-->7 Several valid topological orders (non-exhaustive list):
// ^ | | - [4, 0, 7, 6, 5, 1, 2, 3]
// | v v - [0, 4, 7, 6, 5, 2, 1, 3]
// 3-->1 0 4 - [4, 7, 0, 6, 5, 1, 3, 2]
//
vector<int> TopologicalSort(const DirectedGraph& graph);
#endif // __TOPOSORT_H
Test: make toposort
TO SUBMIT: toposort.cc
Implement in a new file longest_path_dag.cc the function LongestPathInDag() described in file longest_path_dag.h:
#ifndef __LONGEST_PATH_DAG_H
#define __LONGEST_PATH_DAG_H
#include "graph.h"
#include <vector>
using namespace std;
// Input: a directed, weighted graph: each node has a positive weight
// given in the "weights" array.
//
// Output: if the graph is cyclic, returns -1. Else, returns the sum of the
// weights of the nodes on the 'heaviest' path, i.e. the path that maximizes
// the sum of the weights of its nodes.
//
// Hints: If you have implemented TopologicalSort(), you can use it in your
// function; it helps coding the simplest version.
// If not, think about memoization!
// In both cases, it might be useful to create an array that'll store, for
// each node i, the weight of the heaviest path that starts from i.
//
// Example (the node weights are in ())
//
// 2(4)-->5(5)-->6(1)-->7(2) The heaviest/longest path is
// ^ | ^ unique in this example: it's
// | v | 2->5->6->0, whose total weight is 14.
// 3(2)-->1(1) 0(4) 4(11)
//
int LongestPathInDag(const DirectedGraph& graph, vector<int>& weights);
#endif // __LONGEST_PATH_DAG_H
Test: make longest_path_dag
TO SUBMIT: longest_path_dag.cc