Reference no: EM134301

Using a linked implementation of graph prepare a method "checkPath" that takes two nodes as input. The method must return:

True: If adding an edge between these two nodes form multiple paths to one of the input nodes within the graph.

False: Otherwise.

Use the subsequent implementation steps towards completion of your project:

Step 1: Create a graph (the input file format for graph is given in a section below)

Step 2: Give the two input nodes after the graph has been built from the command prompt.

Your program should print true or false based on the input provided at command prompt.

Use the subsequent assumptions:

1. Consider that no edge exists between the two input nodes given at command prompt.

2. Every node has no more than one incoming edge in sample input graph.

Hint: Add a parent field in node class. See if a general ancestor exists for input nodes given at command prompt. Note that your graph here is a directed graph.

Use the subsequent node and edge class definitions towards your implementation (make changes as needed, changes must not include deleting any members or classes):

Class Node {

Edge firstEdge;

Node nextNode;

int info;

}

Class Edge {

Node srcNode;

Edge nextEdge;

}

Sample graph input file:

5

1 2

1 3

1 4

The first line of the input shows the number of nodes in the graph.

After first line every other line represents an edge. Provide the source and destination nodes of the edge using two numbers.

For this sample graph, if the user inputs nodes 1 and 5, the "checkPath" function must print false.

In the same graph if the user inputs nodes 3 and 4 the "checkPath" function must print true. (If you add an edge from node 3 to node 4, two paths exists between node 1 and node 4)

Note that the "checkPath" function does not add an edge between input nodes provided at command prompt.