The main goals for this lab are to understand graphs and graph algorithms, and to gain experience with more open-ended development. To that end, you will:

1. Implement an undirected graph using adjacency lists.
2. Implement three graph algorihms using your graph classes.
3. Design an implementation of a simple train game called Railway.
4. Carry out your design by implementing the Railway game.

Note: This lab is a 1.5 week assignment due the last day of the semester (Friday April 28).

As with most assignments this semester, you will be working with a partner. Both partners should be present and working on the code together. You will both be responsible for understanding all concepts, so dividing and conquering is not an option. The academic integrity policy applies to the entire pair; you cannot work or share code with anyone outside your partner.

You and your lab partner will share the same git repository, which is named lab09-<user1>-<user2>.git. Please access your lab by cloning the appropriate git repository, e.g.:

	$ git clone git@github.swarthmore.edu:CS35-s17/lab09-jbrody1-adanner1.git

Railway is a two-player route-building train game designed by Zach Palmer, inspired by the board game Ticket To Ride. Two players are given a map of possible train routes and take turns laying tracks between them. Players attempt to complete route goals while trying to connect as many cities as possible.

The GUI (graphical user interface) of Railway has been provided for you. When you launch the GUI, it will display something like:

Your job will be to use this GUI to write the game. Along the way, you wil need to implement some of the graph algorithms that we're discussing in class and apply them to the game.

Railway Game Rules

Setup. Railway is played on a map represented by a graph.The vertices of the graph are cities; the edges on the graph are potential railway routes. Routes have a cost in “tracks”, the resource used to build railway routes. Routes may also have an owner but, at the start of the game, neither player owns any route. Players take turns acquiring routes in order to complete goals while simultaneously connecting as many cities as possible.

Each player has a number of “tracks”, the resource used to build railway routes. Routes cost varying numbers of tracks to build. Player 1 starts with 35 tracks. Player 2 starts with 50 tracks (to compensate for the disadvantage of making the second move).

Each player also starts with three randomly-chosen goals. Each goal instructs the player to connect two cities on the map; these cities are always at least three routes apart.

Playing the game. Players alternate taking turns. Each turn, a player must do one of the following two actions:

1. Claim a route. A player claims a route by selecting that edge on the game map. In order to claim a route, the following requirements must be met:
   • The route must be unowned.
   • All routes owned by a player must be connected.
   • The player must pay a number of tracks equal to the route's cost.
2. Pass. A player passes by clicking on the pass button. When a player passes, she gains one track for each city connected by her rail network.

Scoring. The winner of the game is the player with the highest score. A player receives one point for each connected city. The value of each goal equals the length of the shortest path between the two cities, dividing by four, and rounding down.

Example. Consider the following image of a game in progress:

Observe the following:

• Player 1 (green) is out of tracks and must pass. This will give player 1 six more tracks (one each for (AMS, FRK, BRN, FLC, ROM, and CAT).
• Player 2 (purple) could acquire the route from MAD to SEV next turn (8 tracks) but cannot afford the route from MAD to LIS.
• Player 2 cannot acquire the route from WAR to MIN next turn, since that route is not next to a city that Player 2 has already connected.
• Player 1 has completed the goal “AMS to CAT” using the cheapest possible path (in terms of edge weight). This is worth ⌊5+7+11+5+124⌋=10 points. Player 1 has also connected six cities, for a total score of 16 points.
• Player 2 cannot complete the goal “BRN to CAT” because Player 1 owns the only route that connects CAT to the rest of the map.

Your starting repository includes a large amount of code this lab.

The Graph Classes

As usual, the adts directory contains the ADT declarations and implementations for you to use in this assignment. This directory contains a graph.h ADT, as well as an edge.h declaration of an Edge class.

The stl directory contains the collection of STL-based data structure implementations that you've seen this semester. A new stlHashTable.h class has been provided.

adjacencyListGraph.h contains a directed graph implementation using an adjacencyList. You are responsible for understanding this code but should not need to change it.

adjacencyListUndirectedGraph.h contains a partial implementation of an undirected graph. This class is a subclass of adjacencyListGraph.h and uses the parent class for most of the implementation, by treating each undirected (u,v) edge as two directed edges (u,v) and (v,u). You will complete the removeEdge and getEdges methods.

Graph Algorithms

As part of this lab, you will write implementations of the following graph algorithms:

• Breadth-First Search (BFS)
• Depth-First Search (DFS)
• Dijkstra's Algorithm.

These algorithms are declared in graphAlgorithms.h. Implement them in graphAlgorithms-inl.h.

Railway Code

The RailwayGUI class (railwayGUI.h, railwayGUI.cpp) will, when created, produce a window containing whatever information you provide. The resulting object allows you to update the graph on the map, change the message displayed at the bottom of the window, update each player's score, and so on. You can also ask the RailwayGUI class for the next command that the user has sent: pass, place a route, or close the window. Look at main.cpp for some code to get you started, and make sure to read the comments in both main.cpp and railwayGUI.h.

The RailwayGame class (railwayGame.h, railwayGame.cpp) is essentially empty. You should use this class to manage all of the game state in Railway. It should contain information about whose turn it is, what the map looks like (e.g. as a Graph*), information about each player, and so on. We've also given you a Goal class (goal.h,goal.cpp); you'r ewelcome to modify this class in any way you like.

The starting code for railwayGame.h/railwayGame.cpp is intentially sparse. It is up to you to effectively design this class to facilitate the game play. Spend some time on design before doing any coding of this class. Then implement this incrementally, making sure each piece of code works before moving onto the next. Use the Top-down design skills you learned in CS21.

By the time you are finished, you should have a game that implements the rules of Railway as described above. To earn full credit, your program should function (no crashes or freezes) and play the game correctly (e.g. don't let players take multiple turns in a row, score the goals correctly, etc.) Your UI must also provide the following features:

• If a goal has not yet completed but is still possible, you must show its value
• You must indicate when a goal has been completed or when a goal is now impossible to complete
• If a player makes an incorrect move, you must use the message bar at the bottom of the GUI to explain the problem. (e.g. Player 1: that route has already been taken)

Running the Game

Part of the main function (the part that reads graph data from a file and creates the GUI) has already been written for you. You can run your code by runnint make and then

	$ ./railway test_data/Europe_graphData.txt test_data/Europe_vertexPositions.txt test_data/Europe_background.png

The game can take diffent graphs than Europe. We've included another map for a mystical land called Testaria, the mystiacal mythical island of tests. Use this map with the command:

	$ ./railway test_data/Testaria_graphData.txt test_data/Testaria_vertexPositions.txt test_data/Testaria_background.png

This lab is, by design, more open-ended than in previous labs---you are responsible for part of the design of your railway game code, as well as the actual code itself. Here are some suggestions to get you started.

1. Workout how you're going to solve this problem before you write any code!. It may help for you to write your plan down or discuss it before you start implementation. Make a list of the information you need to maintain (e.g. player scores, graph,...) and where you plan on keeping it (e.g. the graph class can be a data member of RailwayGame) Do not start coding before you have a design plan
2. You may wish to create a Player class. If you do, either add its declaration and definition alongside the RailwayGame class, or create new files player.h, player.cpp. If you choose to create new files, make sure to add player.o to the OFILES variable in the Makefile, or you will get some compilation errors.
3. When writing Dijkstra's algorithm, you will need a minimum priority queue. The priority queue implementation you've seen this semester has been a maximum priority queue. One way to get a minimum-priority queue is to use a maximum-priority queue and invert the priorities. For example, if you have elements with priorities 6, 10, 15, then add them with priorities -6, -10, and -15. That way, when you call removeMax, you'll get the "maximum" priority of -6.
4. You can select a random number using the rand function from stdlib.h. For instance, rand()%10 will give you a random number between 0 and 9. You will need randomness when picking goals at the start of the game.

We strongly recommend getting the graph and graph algorithms implemented and tested before coding the Railway Game. However, it might be helpful to work on the game design while or even before you implement the graph class and algorithms.

Your program is required to run without memory errors; run valgrind to eliminate them. For this lab, memory leaks are not a priority. Small memory leaks are acceptable and will not significantly affect your grade. While "lost" memory should not occur in large amounts (e.g. millions of bytes), we encourage you to not spend hours and hours tracking down every last memory leak.

Graders will assign minor penalties for poor commenting and coding style.
Please review the CS35 Coding Style for good C++ style. When you have completed your lab, answer a few short survey questions in the file README.md.

When you have completed your lab, you should have

• A working undirected graph implementation using adjacency lists.
• Implementations of BFS, DFS, and Dijkstra's algorithm.
• A working Railway game!
• No memory errors
• Code which conforms to the style guide above.
• A completed survey in README.md

Once you are satisfied with your code, hand it in using git. Remember the add, commit, push development cycle. You can push as many times as you like, but only the most recent submission will be graded. You may want to run git status to confirm all modifications have been pushed.