Reference no: EM134303

Using a linked implementation of graph write a method that takes two nodes as input and returns true if joining an edge between these two nodes, forms a duplicate path to one of the input nodes within the graph. Else the method must return false. Suppose that it is known that an edge does not exist between the input nodes. You may have to add an additional field to a graph node which holds the parent. Provide two input nodes trace the ancestors and compare them to see if there is a common ancestor. If a common ancestor is found then your method must return true.

The input must be read through a file. The first line of the input must indicate the number of nodes in the graph. If you have 5 nodes suppose that the nodes will be numbered I through 5 (Figure is an example). After first line every other line must have two integer values, the two values show the source and target of the node (it's a directed graph). Sample input for figure 3 graph is

Sample input:

5

1 2

1 3

1 4

1 5

3 5

4 2

In figure is an edge was being added between nodes 3 and 2 then there is a duplicate path to node 2 from node 1, so the function must return true.