# Lab: Graphs

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

## Task 0: Working with yEd

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

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.