Graph Representations

As we learned in both lecture and the textbook, there are multiple ways of representing the same Graph ADT. We typically have a collection of vertices, then also either:

• a collection of edges (i.e., an edge list),
• each vertex tracks its own edges in an adjacency list, or
• we save all possible connections between vertices in an adjacency matrix

In this warmup, we will compare all three representations. Later in the lab, you are free to choose whichever of the three you prefer to represent your Graph ADT.

Graph Example

Recall the Wolf-Goat-Cabbage puzzle from class:

*A farmer goes to the market and purchases a wolf, a goat, and a cabbage.

• On the way home, the farmer has to cross a river, but the boat can only carry the farmer and one other entity
• If left alone, the wolf will eat the goat, and the goat will eat the cabbage
• Goal: can the farmer transport all three purchases to the other side without any entity being eaten? If so, in what order?

This puzzle can be illustrated by the following graph:

where the vertices are the possible situations of the world (characters to the left of the | represent entities on the left side of the river, and characters to the right of the | represent entities on the right side of the river) and edges are the entities transported by the boat between two situations.

Vertex Collection

In your GitHub repository, create a new text file named representations.txt. In the first line, write out what the vertex collection would be for this graph. You can assume that each vertex can be written as a String (e.g., ”FWGC|”, “Failure”) and the order of the vertices does not matter.

Edge Lists

One line 3 of your text file representations.txt (so that line 2 is a blank line), document how we would write out the graph in an edge list representation. You can write an edge as a pair of vertices inside parentheses, such as (“FWGC|”, “WC|GF”).

Adjacency Lists

In lines 5-20 of your text file representations.txt (so that line 4 is blank), document the adjacency lists for each vertex (one vertex per line). Each line should start with the vertex, followed by a semi-colon :, followed by the edges connected to that vertex.

Adjacency Matrix

Finally, on lines 22-38 of your text file representations.txt (so that line 21 is blank), document the adjacency matrix representation for the graph. In particular, line 23 should list the different vertices (as columns of the matrix). Line 24 should start with the first vertex in your vertex collection (from line 1), then include a 1 for any vertex it is connected to with an edge (and 0 of other vertices).

Committing Your Progress

Don’t forget to add/commit/push your representations.txt file.