1 Adjacency Lists

This will be covered in more detail in the notes for Unit 9, but here is an overview of how we store a graph with an adjacency list data structure:

• Every vertex is identified by some label. (Usually, these labels are just strings.)
• Every vertex is associated with a list that contains the labels of its neighbors, i.e. the other vertices which are connected to that vertex by some edge.
• There is a map that associates each vertex's label to its list of neighbors.

So the main representation is a map of strings to lists of strings. For example, the adjacency list of the following graph:

would be the following map of strings to lists of strings:

{'A': ['B', 'C'],
 'B': ['A', 'C', 'D'],
 'C': ['A', 'B'],
 'D': ['B'] }

2 DOT Files

A common file format for encoding graph information is called a DOT file. We're going to write a class to read in a .dot file of an undirected, unweighted graph, store the information in an adjacency list, and then run some common operations on that graph.

Here's an example dot file. The first line names the graph. Following that is a list of all edges in the graph. You may assume the vertices are "named" using a single word, but they may not be single letters like this. You can also assume the graph is undirected and unweighted, and that there is one edge specified per line, like in the example file.

3 Assignment: Write a Graph class

In a file called graph.py, you need to write a class Graph with the following methods:

• A constuctor which accepts a file name, stores the graph name, and builds the adjacency list. You can assume a competent user is calling this, and the file is, indeed, a .dot file. (Ex: g=Graph('example.dot') )
• isEdge(self, vertexA, vertexB): Returns True if the two vertices are adjacent, and False if they are not. (Ex: Given our example.dot, g.isEdge('B','A') would return True, while g.isEdge('D','A') would return False.) Because the graph is undirected, the order of the arguments shouldn't matter.
• neighbors(self, vertex): Returns a list of all vertices adjacent to vertex.
• __str__(self): Returns a string which re-creates the .dot file from the adjacency list. It doesn't need to be in the same order as it was when it came in, but it should contain the same information. You may not just store all the text and regurgitate it for this method. Take note, the description should be returned as a single string, not printed.

This lab will be the basis of our next project and lab, so understanding it carries some extra importance. If you have questions or run into trouble, just ask for help!

Note: if you're stuck on how to read in the dot file, have a look at the built-in methods of file objects and, more importantly, the built-in methods of strings.

4 Visualizing .dot files

If you have a .dot file, you can use some built-in Linux tools to visualize it. For example, given your example.dot, run fdp -Tpng example.dot > example.png. You can then look at example.png to see your graph. Run man dot for the full specifications.

5 Directed Graphs

The rest of this lab is optional for your enrichment and enjoyment. Be sure to work on this only after getting everything else perfect. You should still submit this work, but make sure it doesn't break any of the parts you already had working correctly!

.dot files can also handle directed graphs, though right now, your program probably can't. Fix that! If A -> B;, then isEdge('A','B') should return True, but isEdge('B','A') should return False.

Arrows always point right.

Directed graphs are labelled as such: in the first line, instead of "graph graphName {" it would say "digraph graphName {". In digraphs, ALL edges are directed (A -- B; is not allowed). In regular graphs, NO edges are directed.