Assignment 6: Path Length

Objectives

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

Introduction

In general, there can be many simple paths (paths with no repeated vertices) in a graph between any pair of vertices. In many applications, we are interested in the extremes, for example the simple paths with the most or fewest edges. For example, we can represent the states of a puzzle as vertices in a graph, with a directed edge if it is possible to move from one state to another in a single step; the path with the fewest edges from the vertex representing the initial state of the puzzle to the vertex representing the goal state then represents the solution with the fewest steps. And in a graph representing a combinational circuit with vertices representing inputs, outputs, and logic gates, and edges representing connections between those inputs, outputs, and gates, the longest simple path plays a large role in determining how fast the circuit can produce its output.

Overview

Complete a program called Paths that will read the number of vertices and a list of the edges in a directed graph from a file and will compute and display the lengths of the shortest or longest simple paths between pairs of vertices. The name of the file to read and which paths to compute will be given as command-line arguments. For example, if the file graph_6.in contains

6
0 1
0 2
0 3
2 1
3 2
3 1
4 0
4 5
5 0
5 4

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

The Paths executable

The paths.c from /c/cs223/hw6/Optional contains a main that handles input and output, relying on an implementation of a directed graph ADT in the ldigraph module to compute the lengths of shortest and longest simple paths. You should not need to modify this file. There is also a makefile in that directory that you may use to build the executable.

Implementing the ADT

In order for the code in paths.c to work, you must complete the adjacency-list implementation of the directed graph ADT in the ldigraph.c file from /c/cs223/hw6/Optional/. You will have to complete the digraph_bfs function that is called by digraph_shortest_path and also complete 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 simple path by finding every possible simple 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.

As usual, the time bounds assume that malloc and free run in $O(1)$ time.

Your implementation of the search functions may assume that there is enough heap space available to allocate a constant amount of space per node in the graph for a reasonable constant.

Details

User input is handled by the provided paths.c, so you needn't worry about these details except to create your own test cases.

Graph specification

• the first line of the file contains a non-negative integer in a format readable by atoi giving the number of vertices in the graph
• the rest of the file contains one line per edge
• each edge is given as the index of the source vertex and the index of the destination vertex, separated by a single space
• there are no duplicate edges
• each vertex index is between 0 (inlcusive) and the number of vertices in the graph given on the first line (exclusive)
• there are no self-loops (edges from a vertex to itself)

Command-line arguments

• The first command-line argument is always present and gives the name of the file containing the graph specification or is the string -timing. If the name of a file, that file will be readable and in the format specified above.
• If the first command-line argument is -timing then the last two command-line arguments give a graph size as a positive integer readable by atoi and either 0 or 1 indicating whether to process the remaining command line arguments or not (0 means don't process).
• The remaining command-line arguments occur in groups of three. Each group of three arguments starts with either -shortest or -longest to indicate whether to compute the length of the shortest or longest simple path, and then contains the indices of two valid vertices in the graph in a format readable by atoi.

Output

• There is one line of output per group of path specification arguments.
• Each line starts with -shortest or -longest as specified by the corresponding argument, then gives the indices of the starting and ending vertices, separated by ~>, then has a colon and the number of edges in the computed path. Spacing is as in the above example.
• Path length is reported as -1 if there is no path.

Submissions

Submit your completed ldigraph.c and any other source code you created or modified that is necessary to build the Paths executable. If you did not modify the files from /c/cs223/hw6/Optional then you need not submit them. 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.