CS 341, Spring 2024

Individual Programming Project - 4

Due: midnight – Sunday 4/28/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 connected 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 <I, J> indicates an edge from I to J.

The algorithm for Topological Sort is as follows:

Repeat 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.

Bonus:

Identify and output if the graph is disconnected and has distinct components!