Challenge 05: Graph paths

Problem overview

Given a directed graph, determine if there is a path between two nodes in the graph.

For instance, in Graph 4 above, there is a path from A to D, but no path from D to A.

You will be given a series of graphs specified by edge pairs, and then a series of paths to check for. For each path, you are to determine if the graph contains a route from the specified source to the specified destination.

Note:

You must represent the graph using either an adjacency list or adjacency matrix to receive credit for this challenge.

Inspiration

This problem was inspired by Problem 4.2 from Cracking the Code Interview.

Input / Output

You will be given a series of directed graphs from standard input in the following format:

NEDGES
SRC1 DST1
...
NPATHS
SRC1 DST1
...

The first line specifies the number of edges in the directed graph, followed by NEDGES pairs of nodes where the first string is the source and the second string is the destination, which indicates that there is an edge from source to destination. After this, you are given NPATHS which is the number of paths or routes to search for. The exact paths to verify follow this line as a series of source and destination pairs.

For each path for a particular directed graph, output a statement saying:

In Graph 1 there is a path from A to B if there is a path from A to B. Otherwise, output a statement saying:

In Graph 1 there is no path from A to B

Put an empty line between the output for each graph as shown below.

For example, given the following input:

1
A B
2
A B
B A
3
A B
A C
B C
4
A B
A C
B C
C B

Your program should output the following:


In Graph 1 there is a path from A to B
In Graph 1 there is no path from B to A

In Graph 2 there is a path from A to B
In Graph 2 there is a path from A to C
In Graph 2 there is a path from B to C
In Graph 2 there is no path from C to B

Hints

You should perform some sort of traversal such as DFS or BFS.
You are also allowed (but not required) to use a std::map or std::unorderered_map to represent the directed graph.

Rubric

We will grade your submission relative to the rubric below.

+1.5    Code is well formatted, commented (inc. name, assignment, and overview), with reasonable variable names
+5      Uses an adjacency list or adjacency matrix representation for directed graph
+28.5   Requested paths successfully solved (1.5 points each)

Testing your code prior to submission

To faciliate testing, you were previously asked to clone the course Github repository as follows:

git clone https://github.com/semrich/ds302_19.git cs302

For this assignment, update this clone by using the following:

git pull

We'll discuss this in class but note that your program must be named "solution.cpp" and compilable using make. To test your solution against ours, type:

make test

Submission

To submit your solution, you must submit a single archive (.zip, .tar, .gz, etc.) on Canvas prior to the deadline.

Note: Although submission will be faciliated by Canvas, we will compile and test on EECS lab machines!

If you develop your solution elsewhere please make sure it works on the lab computers prior to the deadline