This lab will have you and your lab partner implement an advanced game advisor for the game Ticket To Ride. Ticket to Ride is a popular, award winning game with many spin-off variations. It is particularly well known for having a simple set of rules (unlike one of my favorite games, Settlers of Catan) but several strategies for success. This makes it quite popular for families with a board-game geek amongst them.

Details will be provided in Part B, but you've seen in lab how to play the game. The basic premise of the game is to construct railroads across the United States, connecting cities up along the way. You score points for claiming routes (i.e., connecting two adjacent cities). Often, you are competing to claim a route before your opponents. In addition, you collect destination tickets along the way which specify two distant cities. If you connect those two cities by claiming routes in between (i.e., form a path between the destinations), you obtain bonus points. Otherwise, you are penalized for any unfinished connections.

Naturally, this sets up well for a graph problem. In this part of the lab, you will concentrate on understanding your graph representation and implementing key algorithms in a generic manner that will assist you with Part B.

• Ticket to Ride tutorial video
• Play Ticket To Ride
  • Login Name: player1450577
  • Password: hingla
  • or just create your own account ;)
• Ticket To Ride wikipedia entry.

As usual, you can get the initial files for this lab by running update35. The new files are listed here, and the files that you will need to edit are highlighted in blue:

• graph.h/-inl.h: Declares and defines a Graph class.
• edge.h/-inl.h: Declares and defines an Edge class.
• ugraph.h: Defines a UGraph class, which is a strictly undirected graph. UGraph inherits from Graph.
• ugraph-inl.h: Implements any methods inherited from Graph that need to be redefined
• graph-algorithms.h: Defines functions for several graph algorithms.
• graph-algorithms-inl.h: Implements the graph algorithms.
• testGraph.cpp: A program to test your implementation of the graph algorithms.

Note: We've provided you with binaryHeap and HashTable implementations, but you're free to use your own if you like. If you do use your own implementations, you will need to add your HashTable implementation from last week into your library. That is, you should copy hashtable-inl.h to cs35/labs/11/library/. You'll also need your BinaryHeap implementation to solve Dijkstra's Algorithm.

You are responsible for the following three deliverables in Part A:

1. Finish the implementation of UGraph
2. Implement graph algorithms (e.g., BFS, DFS, Dijkstras) in graph-algorithms-inl.h
3. Add several tests in testGraph to ensure that Graph, UGraph, and each graph algorithm works correctly

While the Graph class been defined for you, it is very important that you dedicate time for reviewing the implementation. It is much more complex than previous data structures, and understanding the interface is essential to successfully completing the rest of the lab. Seriously. Understand the Graph class.

Our Graph represents graphs that are weighted and directed. It uses an adjacency-list representation: for each vertex we store a list (an STL vector to be precise) of the outgoing edges from that vertex. An edge is described by the Edge class, which stores a label to identify the edge (e.g., the flight number of the edge represents airline routes), a source vertex, a destination vertex, and a weight (uniform for unweighted graphs).

In an adjacency-list representation, we could store a vertex as an object with a label and a vector of Edge objects. Instead of explicitly representing a vertex object, our implementation of the Graph class stores the set of vertices in two HashTables.

1. A hash table to store the vertices (i.e., their labels)
2. A hash table to store vertex -- edge-list pairs (i.e., the adjacency list). That is, vertices are the keys and their list of outgoing edges are the values.

You will not need to implement any Graph methods, but you will need to understand how to use them. Before moving on, create a Graph object in your testGraph.cpp file and test each method in the interface.

UGraph

As mentioned, the Graph class represents graphs as being weighted and directed. This is the most general representation of a graph: unweighted graphs can be simulated by simply ignoring the edge weights (i.e., assigning the same cost to each). Similarly, we can simulate an undirected graph by simply ensuring each inserted edge has a complement. That is, for every edge A-->B, there must be a B-->A with matching weight and label.

We could simply rely on a user of the Graph class to maintain this property, but that would violate many of the OOP properties we have seen throughout the course! Instead, we will utilize inheritance/interfaces to ensure a guaranteed properties of undirected graphs.

In ugraph.h, you will find the declaration for UGraph, an undirected graph class. This class inherits most of its features from the Graph class. In fact, most of the methods will remain unchanged since their behavior does not depend on whether the graph is directed or undirected. Only four methods need to be over-ridden - insertEdge, removeEdge, getEdges, and graphViz. You must implement removeEdge and getEdges. You are also responsible for understanding this fact: our use of inheritance and polymorphism (i.e., virtual) allows us to write graph methods (e.g., Dijkstras, breadth-first search) that work the same regardless of whether we are working with a directed or undirected graph.

Note: recall that you can call the parent class version of a method by using the scope operator (e.g., Graph<V,E,W>::). For example, in the provide insertEdge, we simply add two directed edges using the Graph implementation of insertEdge. If we omitted the scope operator, C++ would call the UGraph implementation, leading to infinite recursion. removeEdge will be as simple as insertEdge (i.e., simply call the parent method twice). getEdges will be slightly more complicated: you must call the parent method, but ensure that each edge appears only once in the vector (i.e., only one of A-->B or B-->A should be in the list since they are the same exact edge).

Please complete each function declared in graph-algorithms.h These standard graph search algorithms will help you implement your Ticket To Ride program in Part B, but also ensure that you understand three traversal algorithms we discussed in class - depth-first search, bread-first search, and Dijkstra's. You must test each function you implement using the testGraph program. I suggest starting with the graphs we drew in class (i.e., the unweighted campus map and the weighted map of towns around Swarthmore.)

Feel free to add additional methods, although you will need to ensure you add their declaration in the header file. At a minimum, your functions are:

• reachableDFS: a function that takes in a Graph pointer, a source (or start) node, and a destination node. It returns a bool -- true if a path exists from src to dest. I strongly recommend implementing a recursive version, but you are free to utilize a Stack data structure or the vector class. Your solution must be depth-first search.
• shortestLengthPathBFS: returns the sequence of vertices in the shortest-length path from src to dest. The caller is responsible for first checking if a path exists (an error is thrown if no path exists). Your solution must be a breadth-first search algorithm.
• dijkstras: returns a Dictionary of distances (i.e., shortest-cost paths) from a src node to every other node in the graph. That is, the key is a destination node and the value is the shortest-cost path. From class, you will need to consider two important design choices a) how to represent "infinity" and b) how to update priorities.
  
  Note: we'll see Dijkstra's Algorithm on Tuesday. It computes the single-source-shortest-cost-path for weighted graphs: given a start vertex s, it finds, for each other vertex t, the minimum cost path according to the edge weights. See Some helpful hints below (including pseudocode).

Recursive DFS

We've talked about using a stack to implement DFS or implementing DFS using recursion, letting the function stack act as our stack. Below is pseudocode for one possible recursive DFS implementation.

reachableDFS(G, source, dest) :
  dictionary VISITED, each vertex is false

  toReturn = recursiveDFS(G,source, dest, VISITED)
  return toReturn
}

recursiveDFS(G, current, dest, VISITED)
  if current == dest
   return true
  mark current as visited
  for each neighbor w of current
    if w not visited
      if recursiveDFS(g, w, dest, visited)
       return true
  return false

Testing

As an example, you could construct a graph to represent our search problem of trying to get from Parrish Hall to The Ville (way back in week 5). If you do this correctly, your test may look like this:

$ ./testGraph 
Let's build a map of Swarthmore!

The graph: 
Softball: {Ville, Soccer, Tunnel, Train}
Bridge: {Tennis, Wharton}
Sharples: {Clothier, Tunnel}
Soccer: {Softball, Tennis}
Wharton: {Bridge, Clothier}
Magill: {Parrish, Train}
Tennis: {Soccer, Bridge, Tunnel}
Parrish: {Magill, Clothier}
Train: {Magill, Ville, Softball}
Ville: {Train, Softball}
Tunnel: {Softball, Sharples, Tennis}
Clothier: {Wharton, Parrish, Sharples}

Can I get from Parrish to the Ville?

DFS: yes!

How do I get from Parrish to the Ville?

Using BFS:
                Parrish
                Magill
                Train
                Ville

The shortest path length is: 3

You might find the following hints more or less helpful:

• To compute the path between two vertices in the graph, you should use auxiliary data much like computing the maze path in Lab 05.
• Templates can be very particular about using c-strings versus strings. For example, in your test file you will get an error if you try:

  Graph <string, string, int>* graph = new Graph <string, string, int>
  graph->insertVertex("Parrish");
  //do some more inserts, code is looking good!
  
  //now let's do something interest
  bfs("Parrish","Ville", graph); //Compiler error
  

  C++ interprets "Parrish" as a c-string and doesn't like that you are trying to send that in for a string. Simply modify your call by casting it as a string explicitly.

  bfs(string("Parrish"), string("Ville"), graph);
  

Representing infinite distances

It is up to you how to represent infinity. There are three general strategies:

• Using an approximation based on C++ libraries (i.e., the limits library.)
• Only insert elements into the Dictionary when their distance is discovered for the first time. Thus, if the statement in the inner-loop should be

  if (!distances.containsKey(v) || distances[v] > distances[u]+cost(u,v)):
  

• Similar to the above, but instead have a second dictionary (e.g., visited) that is false until a node has been seen for the first time. The if statement above then checks visited first.

You must add a comment in the header file for what the user should expect. That is, if a node v is unreachable, should the user expect a value of "infinity" in the dictionary? Or will it simply be absent?

Updating priorities

There is no updatePriority function for your BinaryHeap. Implementing one is feasible, but a little tricky. You can do this if you wish. On the other hand, you can employ the following strategy:

• Do not insert an item into the priority queue until it is visited for the first time
• In the inner-loop: if you have never seen a neighbor v (i.e., it's distance is infinity/visited is false), set its distance as usual and insert for the first time into the priority queue.
• If, on the other hand, it has been seen before and the distance is improved, insert into the priority queue again. This means there will be two values in the priority queue with the same destination, but the improved priority will be processed first. The second time a destination is processed, it will lead to no changes
Here is the pseudocode:

Dijkstras(source, G):
  empty priority queue PQ
  empty dictionary DIST
  dictionary COMPLETED, each vertex is false 

  PQ.insert(0, source)
  DIST[source] = 0

  while( !PQ.empty() ):
    u = PQ.removeMin()
    if( COMPLETED[u] ) // been there done that
      continue
    COMPLETED[u] = true
    for each (u,v) in E //for each neighbor of u
      if DIST does not contain v:  // new priority
        DIST[v] = DIST[u] + cost(u,v)
        PQ.insert(DIST[v], v)
      else if DIST[v] > DIST[u] + cost(u,v)  //updating priority
        DIST[v] = DIST[u] + cost(u,v) //update distance
        PQ.insert(DIST[v],v)
	
  return DIST