Due: Monday, April 4th, 2011 9:10am
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.
After reading in a representation of a graph, have your program print two results:
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:
all reachable from first? | all reachable from last? | |
list | yes | no |
cycle | yes | yes |
wide | yes | no |
triple | yes | yes |
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:
max depth | |
list | 99999 |
cycle | 99999 |
wide | 1 |
triple | 14289 |
Last update: Thursday, April 7th, 2011mflatt@cs.utah.edu |