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

In class this week, we will work on the Wolf-Goat-Cabbage puzzle:

*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”).

Hint

Since the graph is undirected, you only have to include each edge once in the edge list. You do not need to include the same edge twice by flipping the order of its vertices.

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 colon :, followed by the edges connected to that vertex.

Hint

Since the graph is undirected, each edge will be included in two different adjacency lists – one for each of its vertices.

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).

Hint

Since the names of the vertices are several characters long, you might want to replace your column names (on line 22) and row names (at the start of rows 23-38) with numbers, where the first vertex in your vertex collection is 1, the second vertex is 2, etc.

Committing Your Progress

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