CS230 Lab: Graphs

Lab: Graphs

Solutions not posted because we will continue to work on this problem outside lab

Goals

 

Task 0: Working with yEd

yEd is a tool for creating, importing, and sharing graphs.

Download yEd to your computer in lab, and on your own computer.

Today, we will start writing an AdjListsGraph class. We'll use yEd to create graphs and then save these graphs as .tgf files.
Your AdjListsGraph class will interact with .tgf files. Below is a snapshot of yEd with a graph with 4 nodes and various edges.

Follow these steps to get a feel for how yEd works. Start yEd. Click on the New Document icon.

  • Drag a node from the Shape Nodes palette to the main window.
  • Double-click on the node and type "A" in the Text field of the Properties View:

  • Repeat three more times, so you have four total nodes, labelling them B,C,D
  • Add an edge between two nodes by clicking inside a node and dragging your mouse until it is inside the other node. For example:
  • Save your graph as a TGF file.
    yEd allows you to save your graphs as .tgf (trivial graph format) files. To do this: File > Save As > TGF Format (*.tgf) from the drop down menu (see image below).
 

Task 1: Writing the AdjListsGraph class

Your AdjListsGraph class will interact with .tgf files in two ways:

  1. your program should be able to take a .tgf files as input to produce an AdjListsGraph object.
  2. it should also be able to create a .tgf file that represents the AdjListsGraph object.

Start by drawing a simple graph, like the one below, and filling in the Data Structures that are needed to represent it.

AdjListsGraph class

  1. Download the lab9 folder. It contains the Graph interface.
  2. Set up the AdjListsGraph class, to implement the Graph interface.
  3. Set up its instance variables:
    • a Vector of generic kind of objects, named vertices to hold the vertices, and
    • a Vector of LinkedLists of generic kind of objects, named arcs. Each LinkedList will hold the set of adjacent vertices to a certain vertex, according to the Adjacent Lists Graph implementation.
  4. Define a constructor with no inputs, to create an empty graph, and test it right away.
  5. Define the toString() method so that it returns a reasonable String representation of a graph. For the graph earlier, it should return something like this:
    Vertices:
    [A, B, C, D]
    Edges:
    from A: [B, C]
    from B: []
    from C: [B]
    from D: []
    
  6. Test the toString() method with an empty graph.
  7. Define the saveToTGF() method, to save the invoking graph to the input file, in the tgf format.

Adding more to your AdjListsGraph class

public boolean isEmpty() // returns true iff a graph is empty

public int getNumVertices() // returns the number of vertices in a graph

public int getNumArcs() // returns the number of arcs in a graph

Now work on adding and deleting a vertex . As always, make sure you test your code very often!

Continue with the rest of the methods in the Graph Interface, as time permits.