CS 2420-20 Homework 21

Due: Tuesday, April 10th, 2012 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 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 get_number_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 distance of all nodes from the first one (i.e., the maximum among the minimum distances for all nodes). For example, the number is 2 for the example from the slides.

Some extra test inputs: