CPSC-131 Project 4:
The Game Collection

A graph G = (V,E) is simply a set of vertices V, and a set of edges E between those vertices. It may be more convenient to think about a graph as being a network.

We consider a maze in which the nodes represent checkpoints and the edges represent the pathways between the points.
Each checkpoint hides a value, that can be positive or negative. The value does not change and can be collected only once, irrespective of how many times you go through that checkpoint.
Let us say that you start with $100 in your wallet, and you go from one checkpoint to another. If the value is positive, it is added to your wallet. If it is negative, it is deducted from your wallet. You can keep going as long as you have a positive value left in your wallet. The goal is to visit as many checkpoints as you can during a DFS traversal. The only choice you have is where to start.

Consider the following example of a graph with 6 nodes and 6 edges, drawn below.

If we start at node 1 with $100 and follow the DFS traversal, then we visit all 6 checkpoints.

Starting budget / Node visited / Budget after
$100 / 0 / $90 ($100-10)
$90 / 1 / $105 ($90+15)
$105 / 2 / $55 ($105-50)
$55 / 4 / $125 ($55+70=125)
$125 / 3 / $65 ($125-60)
$65 / 5 / $35 ($65-30). STOP

However, starting at Node 2 allows you to visit only 4 nodes: 2, 1, 0, 3. You run out of money after visiting Node 3. Therefore, it is better to start at Node 0.

Game Collection

We consider an undirected graph. Let n represent the number of nodes. For simplicity, we label the nodes in increasing order from 0, 1, …, n-1.

Given an undirected graph, a value for each node, a starting point and a startup budget, find the node that maximizes the number of checkpoints visited during a DFS:

Input: n, starting_budget, values: an array of n values,and an array of edges.

Output: the node that maximizes the number of checkpoints visited during a DFS.

DFS Traversal

There are two approaches to implementing DFS. You need to pick only one. For this project, your DFS traversal should stop if the budget is negative.

1. Iterative approach. The steps for a DFS traversal starting from node v are listed below:

procedure DFS-iterative(v):
let S be a stack

All nodes are labeled not visited
S.push(v)
whileS is not empty
v = S.pop()
ifv is not visited:
label v as visited
for all nodes w adjacent to v in decreasing order of w do
S.push(w)

Note that the nodes are pushed into the stack in decreasing order - this ensures that when they are popped, they will be in increasing order.

2. Recursion approach. It is also possible to implement, DFS using recursion:

Initialization before recursion: All nodes are labeled not visited.

procedure DFS-recursive(v):
label v as visited
for all nodes w adjacent to v in increasing order of wdo
ifw is not visited then
call DFS-recursive(w)

Classes and Functions

The project files provide one class, Graph, with member functions that you must complete. Refer to graph.h for descriptions of the required functions.

Input File

The input file needs to have a specific format. Please follow this format:

-On the first line the number of nodes in the graph. Let’s call it n.

-On the second line the startup budget

-On the third line a number of n values separated by space

-Starting with the fourth line, until the last line, are edges: a pair of two values representing the endpoints, separated by space.

For the example graph above, the input file will look like:

6

100

-10 15 -50 -60 70 -30

0 1

1 2

1 3

2 4

3 4

4 5

Hints and simplifying assumptions

●There are multiple ways to represent a graph in C++. One easy approach is to use a 0-1 adjacency matrix. Recall that a 0-1 adjacency matrix is a square matrix of size n x n where n is the number of nodes, and each element is either 0 or 1:

A[i][j] = 1 if and only if there is an edge from node i to node j

●The maximum number of nodes will be 100

●You do not need to do error checking (e.g., assume all nodes are valid integers in range)

●Note that the data file contains only integers. To read an integer, just use:

myfilestream > myint;

●If there are multiple nodes with the same DFS run length, return the smallest node.

●You can visit a node as long as the budget is positive. The traversal stops after the budget becomes zero or negative.

Program Files

These files will be posted on GitHub for you to download, use or modify, and submit:

●graph.h: contains declarations of the Graph class. You may add other declarations as needed for your implementation. Do not add definitions (code) to this file; definitions of functions belong in graph.cpp. [TO BE COMPLETED]

●graph.cpp: contains skeletons for the required member functions. You may add other functions, member and nonmember, as needed for your implementation. [TO BE COMPLETED]

●main.cpp: contains a set of test functions that will call graph’s functions. You may modify this file for your own test purposes but use the original file to run your final test before you submit your project.

Test Files

Two test files are part of your GitHub repository: smallgraph.txt and biggraph.txt. smallgraph.txt is the same as the one shown above in the Input File section; biggraph.txt contains a graph with 50 nodes. Your final submission will be tested using different graphs.

References

To read more about graph representation, please visit

Obtaining and submitting code

We will again be usingGitHub Classroom to distribute the skeleton code and collect your submissions. Click the assignment link to fork your own copy of the skeleton code to your PC. One student from a group clicks on the link below and forms a new team.

IMPORTANT: The team name must begin with your single digit section number (1-6).

For example: 2-Brians-team. Note that the entire project URL will then be of the form:

(the prefix “project4-” is automatically created).

This student then invites his/her project partner as an “Outside collaborator” in the settings menu.

Do not fork your repository to your personal github account (instructors have admin access to private repositories). Your code should have a URL like NOT

Assignment link:

Please refer to previous project requirement documents on how to use github.

Automated Testing

You can check the results of automatic testing on Travis at (same login as your github account).

Grading Rubric

Your grade will be comprised of two parts, Form and Function.

Function refers to whether your code works properly as tested by the main function (80%).

Form refers to the design, organization, and presentation of your code. An instructor will read your code and evaluate these aspects of your submission (20%).

Deadline

The project will be submitted in two stages.

Stage 1 (Design):

Include the following information in a single PDF document and upload to Titanium.

●Names of all team members and their sections

●URL of github repository

●Which approach will you use for DFS - iterative or recursion?

●Describe your representation of the graph

The Stage 1 deadline is Tuesday, May 1, 11:59 pm. This will not be graded - the purpose is to ask for feedback on your design.

Stage 2 (C++ Implementation):

The project deadline is Friday, May 11, 11:59 pm.

Your code must compile/build for it to be tested and graded.

If you only complete part of the project, make sure that it compiles before submitting.