Objectives

• to work with graphs
• to implement graph search algorithms

Assignment

Write a program called Paths that reads a directed graph and then finds and displays paths in that graph by various methods. The name of the file containing the graph data will be the first command-line argument. The file will contain a positive integer on the first line giving the number of vertices in the graph and then zero or more lines where each line contains the index of the from vertex and then the to vertex for an edge. Each edge will be listed at most once and the indices will be separated by any amount of whitespace. There may also be leading and trailing whitespace on each line.

Subsequent command-line arguments specify which vertices to find paths between and the method to use to find the paths. Command-line arguments "-breadth", "-depth", or "-degree" indicate that paths should be found using

• breadth-first search, where edges from each vertex are considered in the order they appeared in the input file;
• depth-first search, where edges from each vertex are considered in the order they appeared in the input file; and
• depth-first search where edges from each vertex are considered in order of decreasing outdegree of the destination vertex, with ties broken by considering lower destination vertex indices first.

The output of your program must be written to standard output with one line per path requested. That line should give the method used, the index of the from and to vertices, and the path in the format used in the example below (with "no path" in place of the path if there is no path from the from vertex to the to vertex). The output for the requested paths should appear in the order they were given on the command line.

Your program should run in time $O(a(n+m) + b(n^2 \log n) + p)$ where $a$ is the total number of times -breadth and -depth appear on the command line, $b$ is the number of times -degree appears, and $p$ is the total length of all the paths output.

If the input file or command-line arguments are not as specified then your program must behave gracefully: it must not crash or go into an infinite loop.

Your program and any program must not produce any error messages when run with valgrind --tool=memcheck --leak-check=yes -q.

We reserve the right to deduct points from submissions for violations of the following guidelines.

• All source code should be easily comprehended, with adequate and consistent spacing, concise but descriptive idenitifiers, comments before long sequences of code, and enumerations and constants favored over literals.
• Submissions should be modularized, with collections of related functions divided into separate files.
• Each function should be documented with a comment before its declaration. The comment should include 1) a description of the parameters including any limitations on the values allowed (preconditions), and 2) a description of what the function does and/or what it returns (postconditions).
• Header files should be written so that they can be #included regardless of what other files have been #included -- if a declaration is required by your header files, then #include the appropriate header file in your header file (or write a forward declaration in your header) rather than relying on your #includers to have already #included those header files before they #include yours.
• Things that make sense to be declared as const should be declared as const.
• There should be no warnings when your code is compiled with the -Wall and -pedantic options.

Example

4
0 1
0 3
1 3
1 2
2 0
2 3

-breadth 0->3: [0, 3]
-depth 0->3: [0, 1, 3]
-degree 0->3: [0, 1, 2, 3]

Files and Submissions

• ldigraph.h ldigraph.c (an implementation of a directed graph using adjacency lists)
• search.c (a hard-coded graph and searches in it)