Random Path on a Graph

[Aj163]

Description

Let's implement a class Graph which has the following private data members

• Number of nodes, |V(G)|
• Number of edges, |E(G)|
• Adjacency list to represent the edges E(G).

Also let this class have the following public member functions

• addEgde(u, v) : Add an edge from u to v. (Do check for invalid parameters).
• addVertex() : Adds a new vertex to the Graph G. (Vertices are numbered starting from 1).
• randomNeighbour(u) : Return a random neighbor of node u. If u has no neighbors, return -1.
• getNumberOfNodes() : Return the number of nodes in G.

And let the constructor of this class initialize a graph of 1 node and no edges.

Now let's use this class to implement our randomGraphPath() function. This function should print a simple random path in the Graph G, starting from any random node.

Write a menu driven program which asks the user for a choice from the following options.

• Add a new node.
• Add a new edge.
• Generate a random Path.

Details

• Use an Object Oriented Language (C++ / Java / Python)
• Type of issue: Multiple (Implementation in each of the above mentioned languages will be considered as a separate task).
• Time Limit: 4 days

Issue requirements

• [ ] C++
• [ ] Java
• [ ] Python

Resources

You can read up about simple paths from here.

Directory Structure

Add your files inside the following directory ~/algorithms/random_graph_path/<language>/, where <language> is either C++, Python, or Java. (Create required directories if they aren't currently existing). Create the following files

• graph.h which has the prototype of the Graph class.
• graph.cc which contains the definitions to the member functions of the Graph class. Include this file at the end of Graph.h
• random_graph_path.cpp which has the menu driven program. This file includes Graph.h.

Note

Please claim the issue first by commenting here before starting to work on it.