CS 341, Fall 2024

Individual Programming Project - 4

Due: midnight – Sunday 12/8/24

Topological Sort:

For directed graphs the nodes can be sorted to understand and detect the flow of info from source node(s) – only sending information - to sink nodes - only receiving information. If a directed graph can be sorted topographically, it indicates that there are no cycles (which is a very valuable information in systems to avoid deadlock).

Given a directed graph in an input file called digraph.txt, with edges (pairs of nodes) representing directed edges, create an adjacency matrix representation to process. The rows indicate From nodes and columns indicate the To nodes – thus an entry in <IAH, JXL> indicates an edge from node IAH to JXI.

The algorithm for Topological Sort is as follows:

Repeat the following steps until all nodes are output:

1. Identify and output node(s) that have no edges coming to them in one line (level)

2. For each of these nodes – remove all the edges going from them.