### Implementation of graph

Assignment Help Data Structure & Algorithms
##### 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.

#### Questions Cloud

 Critical view of national innovation system : Give your personal and critical view of National Innovation System (NIS) in US. Summarizes and organizes the literature : Summarizes and organizes the literature related to the chosen issue or problem. Using a linked implementation of graph write a method : 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. New product development : You are required to submit a written assignment relating to New Product Development. Implementation of graph : Give the two input nodes after the graph has been built from the command prompt. Econ 301 assignment : Econ 301 Assignment, Find at least three other variables that may affect the return of equity of your choice Find the purchase prices of these materials : Factory X produces a single product which is made from 10 kg of Material A as well as 5 kg of Material B. These quantities allow for waste The purchase prices of these materials The capital projects fund was terminated : The unjustified portion of the grant was refunded to the state the remaining cash was transferred to the General Fund, and the Capital Projects Fund was terminated Explain the type of lease this is to earth leasing : Determine as well as concisely but explicitly explain the type of lease this is to Earth Leasing

### Write a Review

#### Explain the fifo structure of the queue

Explain the FIFO structure of the queue Explain how you would implement the queue data structure in its simplest form. Illustrate your answer fully with the necessary sample code

#### Recursive tree algorithms

Write a recursive function to determine if a binary tree is a binary search tree.

#### Explain the sorting techniques selection sort

Explain the following sorting techniques using appropriate algorithms- (i) selection sort (ii) bubble sort

#### Write a c++ program to find the intersection

Write a C++ program to find the intersection, A set is a collection of distinct entities regarded as a unit, being either individually specified or (more usually) satisfying specified conditions.

#### Write down the algorithm to insert an item

Write down the sample code to create a Linked List and allocate storage space for a node Write down the algorithm to insert an item At the beginning of a linked list

#### Write the selection sort algorithm

Write the selection sort algorithm

#### Determine the branching factor

Expalin the search algorithm that results from each of the following special cases. How does it relate to other algorithms we have discussed.

#### Data structures and algorithm design

Data Structures and Algorithm Design

#### Recursive implementation of euclids algorithm

Write a recursive implementation of Euclid's algorithm for finding the greatest common divisor (GCD) of two integers

#### Use a search tree to find the solution

Explain how will use a search tree to find the solution.

#### Data structures and algorithms

Provides learners with an understanding of how data structures are used in algorithms and enables them to design and implement data structures

#### Describe sorting algorithms and how they work

Describe sorting algorithms and how they work