COMP 410 Fall 2015

Part 2: Topological Sort on a DAG


Summary

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.


Input format

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_source
There 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.


Output and Format

  1. First, print out a line with about 40 "#" characters in a row. This will help visually separate solutions if the input file contains multiple graphs.

  2. Next, print out the graph using the format from part 1.

  3. Next, print a blank line.

  4. Finally, print the topo sort you have computed, using both node numbers and node names (text) like this:
     Topological Sort
     (0)Chapel_hill, (3)Carrboro, (4)Graham, (5)Pittsboro, (7)Cary, (6)Sanford, 
     (9)Los_angeles, (2)Raleigh, (1)Durham, (8)Hillsborough
    
    Note that we have the node number in parens, then the node name, and commas separating them.
    Use multiple lines so it is readeable (not something like 2 dozen nodes all written out on a single line).

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


Miscellaneous Notes