Assignment 8: Path Length

Objectives

to work with graphs
to implement graph search algorithms
to implement a dynamic programming algorithm

Introduction

Creating test cases is a necessary but costly part of software development. There are several approaches to generating test cases automatically, but currently no approach can consistently generate a complete test suite for arbitrary code. Preliminary research suggests that the length of paths in the dependence graphs of a program (shortest, longest, and average) may be correlated with the difficulty of generating test cases. It is therefore useful to have a tool that computes the path lengths in those graphs. Fortunately, breadth-first search can find shortest paths in $O(n+m)$ time, where $n$ is the number of vertices and $m$ is the number of edges. The problem of finding the longest path between two vertices is, however, thought to be a difficult problem with no solution significantly better than examining all paths, of which there may be more than $n!$. Finding longest paths in a directed, acyclic graph is a special case that can be done in $O(n+m)$ time.

Assignment

Complete the adjacency-list implementation of the Directed Graph ADT in the ldigraph.c file from /c/cs223/hw8/Optional/. You will have to complete the digraph_bfs function that is called by digraph_shortest_path and the digraph_longest_path function. The latter function should call modified versions of digraph_dfs in order to topologically sort the graph if possible. If the topological sort is possible, then the longest path between the two given vertices can be found in $O(n+m)$ time by dynamic programming. Otherwise, you should use another modified version of digraph_dfs to find the longest path by finding every possible path between the given vertices.

Your functions must execute in the following worst-case asymptotic time bounds.

ldigraph_shortest_path: $O(n + m)$
ldigraph_longest_path: $O(n + m)$ when the graph is acyclic, $O(n \cdot n!)$ otherwise.

Example

If the file graph_6.in contains

then running ./Paths graph_6.in -shortest 4 1 -longest 4 1 -shortest 0 1 -longest 0 1 should result in the following output:

[jrg94@tick ~]$ ./Paths graph_6.in -shortest 4 1 -longest 4 1 -shortest 0 1 -longest 0 1
-shortest:   4 ~>   1: 2
 -longest:   4 ~>   1: 5
-shortest:   0 ~>   1: 1
 -longest:   0 ~>   1: 3

Submissions

Submit your completed ldigraph.c and any other source code necessary to build the executable Paths using the provided makefile and paths.c. If you modified the makefile then submit yours as well (named makefile with a lower-case m); your makefile can assume that those supporting files have been copied into the current directory, but should not assume they are still in their original locations.