CS230 Lab: Directed Graphs (DiGraphs)

Lab: Directed Graphs (DiGraphs)

Solutions

AdjListsGraph.java with only the read from and write to tgf

Goals

  • review and use java's Vector and LinkedList classes
  • get familiar with the yEd application
  • practice graph layout
  • start the DiGraph (Directed graph) interface implementation

Set up

Download the lab9 folder. Rename it to include the partners names. It contains:

  1. the DiGraph interface
  2. a starting version of the AdjListsDiGraph class, which eventually should implement the DiGraph interface.
  3. a folder tgf_graphs

[START PRELAB ] 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 AdjListsDiGraph class, as an implementation of the DiGraph (Directed Graph) Interface. We'll use yEd to create graphs and then save these graphs as .tgf files (tgf stands for "trivial graph format").

The AdjListsDiGraph class will interact with .tgf files. Below is a snapshot of yEd with a graph with 4 nodes and various arcs.

A .tgf file is a text file containing the list of vertices, one per line, followed by the # symbol in a single line, followed by a list of arcs, one per line. What do you think the TGF file for the graph above looks like? How about this?

1 brian
2 sohie
3 stella
4 takis
#
1 2
2 1
3 4
4 3
1 3

Actually, there is one more arc that is included in the TGF file. Can you guess which one?

Task 0A: Creating a graph in yEd

We have created a video to show you how to use yEd, feel free to look at it as you read the instructions below.

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 0B: Opening a file in yEd

In the lab9 folder you downloaded there is a subdirectory tgf_graphs. In there, you can see several files that you can open in yEd If you have installed yEd correctly, you should be able to double-click and open them.

When you open a TGF file, it seems that there is only one vertex. That's because yEd does not know how to lay out the vertices of the graph and has them all placed on top of each other, as if on a stack! You can click-and-drag one vertex at a time and pull them to a different location on the yEd panel, revealing the other vertices below. Doing so you can create your own layout to have the graph look the way you like it.

[PRELAB ] Task 1A: Review java Vector class

Please access the java API and review the Vector class. For the purposes of this work we will need the following methods from the Vector class:

  • constructor with no inputs
  • add() an object
  • size() of the Vector
  • get() the element at a certain index
  • indexOf() a certain Object
  • remove() the object at a certain index
  • elementAt() a certain index

[PRELAB ] Task 1B: Review java LinkedList class

Access the java API and remind yourself on how to use this class, and some of its basic methods, like:

  • size()
  • get()
  • add()
  • remove()

[END of PRELAB ]

Task: Writing the AdjListsDiGraph class

Once the AdjListsDiGraph class is defined, the user should be able to create an empty graph, add vertices, and remove vertices and connections between them. In addition, the use should be able to write a graph into a file in tgf format, as well as read a graph from a file in tgf format as well as create a graph from a tgf file.

Start by drawing a simple graph, like the one below. On your notebook, fill in the Data Structures to represent this graph.

Set up:

  1. the instance variables:

    • a Vector, named vertices to hold the vertices of the graph, and
    • a Vector of LinkedLists, named arcs. In the Adjacent Lists Directed Graph implementation, each such list corresponds to a vertex, and holds the adjacent vertices to that vertex.
  2. the constructor with no inputs, which creates an empty graph.
  3. the saveToTGF() method, which writes the AdjListsDiGraph instance into the files whose name is passed an an input parameter to the method.
  4. the static AdjListsGraphFromFile() method, which takes as an input the name of a file, in tgf format, and returns an instance of an AdjListsDiGraph.

As always, you should test your code incrementally, i.e every method as you write it, before you move on to the next one. For testing purposes, you can use the saveToTGF(). Alternatively, you can define the toString() early on in your implementation, and use this for verifying your results.

For the graph shown earlier, a reasonable String representation might be something like this:

Vertices:
[A, B, C, D]
Arcs:
from A: [B, C]
from B: []
from C: [B]
from D: []

We have found the above String representation to be quite convenient and easy to implement. Of course, it is up to you to decide on a "reasonable String representation".