In this second part you will use your basic graph data structure from part 1 to solve a graph problem. Write a Java program that will compute a topological sort on a directed acyclic graph.
A topological sort is special an ordering of the nodes in a DAG: if a node N appears before a node M in the sort order, then there is a path in the DAG from N to M.
Your Java program will read the graph information from a text file named "p2graphData.txt". Please make sure that is the file your program opens and reads from, as that is the name of the file we will use when grading.
The format is this:
s1 d1 w1 s2 d2 w2 s3 d3 w3 ... sm dm wm -1 single_source //==================== s1 d1 w1 s2 d2 w2 s3 d3 w3 ... sm dm wm -1 single_source //==================== s1 d1 w1 s2 d2 w2 s3 d3 w3 ... sm dm wm -1 single_sourceThere is one edge per line. Each edge (line) has a source node name (si), a destination node name (di), and an edge weight (wi, which will be a positive integer). The line that is "-1" signals the end of the graph structure input. The line after that will contain a single source node name, which will be used as the source node for shortest path problems (part 3). For the topo sort, the single source node is not needed, as your algorithm will dedide which node(s) in the graph belong at the beginning of the sort(s).
Note that we allow more than one graph to be defined in the input file. Each graph will have the same format, and they will simple follow one another with the "//====================" line tossed in between them for visual separation as you edit test text files.
Here is an example:
Raleigh Durham 14 Durham Hillsborough 9 Chapel_hill Graham 25 Chapel_hill Carrboro 1 Carrboro Cary 32 Cary Raleigh 3 Pittsboro Cary 17 Pittsboro Sanford 15 Sanford Los_angeles 3012 -1 Pittsboro //==================== N1 N2 1 N2 N3 1 N3 N1 1 -1 N1
This file contains two graphs. This means your program will compute and print a topological sort for each one, one at a time.
Each node name will be a single string with no blanks in it, and the three items on a line will be separated by one or more blanks. Each line will have zero or more blanks before the first node name.
We will work with connected graphs, so the only nodes in the graph are the nodes named in the edges. You may wish to read the input file twice... once to collect all node names (and make those parts of your graph data structure) and then a second pass to create the edges.
Topological Sort (0)Chapel_hill, (3)Carrboro, (4)Graham, (5)Pittsboro, (7)Cary, (6)Sanford, (9)Los_angeles, (2)Raleigh, (1)Durham, (8)HillsboroughNote that we have the node number in parens, then the node name, and commas separating them.
For the second graph in the input above, there is a cycle. The (part 4) output for this graph will look like this:
Topological Sort Cycle found... no sort possible