CS 2420-20 Homework 19

Due: Monday, April 4th, 2011 9:10am

Part 1 – Read a Graph

Read a directed graph from standard input, where the graph is encoded as lines of numbers. Each line represents a node, where the first number is the “name” of the node, and each subsequent represent an edge from the node to a different node (i.e., the one named by the number).

For example,

  1 2 3
  2 3 4
  3 4
  4 1

represents the main graph example from the slides, where 1 is “A”, 2 is “B”, etc.

You can assume that each line before an EOF in the input has at least one number, that at least one line is provided, that the numbers are all positive and fit into a C int type, that the numbers on one line are space-separated, and that the nodes are numbered consecutively starting from 1.

You can use readnums.h and readnums.c to handle all of the parsing. You can either use the array-of-arrays result of read_num_lines() directly as the representation of a graph, or you can convert it into a different representation of the graph.

Part 2 – Check Reachability

After reading in a representation of a graph, have your program print two results:

1. Print "yes\n" if all nodes in the graph are reachable by following edges from the node represented by the first line of the input, "no\n" if not.
2. Print "yes\n" if all nodes in the graph are reachable by following edges from the node represented by the last line of the input, "no\n" if not.

You can use any data structure that we have developed during the semester, but note that all nodes are given consecutive numbers as names, which makes “hashing” on the name particularly easy.

Some extra test inputs:

Part 3 – Maximum Path

Have your program print a third result: a number indicating the maximum required to reach any node from the first one. For example, the number is 2 for the example from the slides.

Some extra test inputs: