# Using the Graph Data Structure

## Preliminaries

This document explains how the graph data structure of Gravisto can be used. For all examples it is necessary to have `Graffiti_Core` in your classpath.

## Getting Started

Suppose one wants to create a directed graph containing two nodes `n1` and `n2` and an edge from `n1` to `n2`.

```import org.graffiti.graph.AdjListGraph;
import org.graffiti.graph.Edge;
import org.graffiti.graph.Graph;
import org.graffiti.graph.Node;

public class UsingTheDataStructure
{
public static void main(String[] args)
{
}
}
```

Obviously this example can be extended to create any directed graph. But, of course, not all graphs are directed, hence it is possible to switch between directed and undirected, using

• `g.setDirected(true)`: Makes `g` directed
• `g.setDirected(false)`: Makes `g` undirected

To determine, whether a graph is directed `g.isDirected()` can be used which returns true if `g` is directed.
The third parameter of `g.addEdge` indicates whether the edge should be directed or not. Please not that with this mechanism the graph can have directed and undirected edges at the same time. If at least one edge has no direction the whole graph is per definition not directed.

## Nodes

Now that we are able to create nodes and edges the question arises what to do with them. As seen above two nodes `n1` and `n2` are needed to create a new edge `e`. It is important to keep in mind that there are not any restrictions, except that the two nodes are valid and that both are members of the same graph `g`, of course. This means that selfloops like

```g.addEdge(n, n, true);
```

as well as multi-edges, e.g.

```g.addEdge(n1, n2, true);
```

are supported.
The most common thing to do with some node in applications using graphs is to traverse its neighbors or perhaps the edges incident to it. Since Gravisto is based on Java, it uses the Java iterator concept. In detail the following iterators are provided:

• `Node::getDirectedInEdgesIterator()`: all incoming directed edges
• `Node::getDirectedOutEdgesIterator()`: all outgoing directed edges
• `Node::getUndirectedEdgesIterator()`: all incident undirected edges
• `Node::getEdgesIterator()`: all incident edges
• `Node::getInNeighborsIterator()`: all adjacent nodes connected by an incoming directed edge (bug: or an incident undirected edge)
• `Node::getOutNeighborsIterator()`: all adjacent nodes connected by an outgoing directed edge (bug: or an incident undirected edge)
• `Node::getNeighborsIterator()`: all adjacent nodes

Please note that there are not only these methods which return an iterator but there are corresponding ones which return a collection of the sought-after elements. Their names are canonical to the above, i.e. the phrase "`Iterator`" is missing in their respective name. Further, there are methods which return all in and out edges, where undirected edges count in both directions. They have an "`All`" in their name after the "`get`". See interface `Node` for further details.
Suppose having some graph `g` with some node `n` the following loop can be used to perform a certain action on all adjacent nodes of `n`:

```Iterator edgeIt = n.getEdgesIterator();
while(edgeIt.hasNext())
{
Edge e = (Edge) edgeIt.next();

//
// some action on e, which is the current edge in iteration
//
}
```

The usage of the other iterators is analogously.
Another concept commonly found in graph theory is the degree of a node. Thus given a node `n` calling `n.getInDegree()` or `n.getOutDegree()` returns the number of incoming or outgoing edges respectively. (At the moment there exists a Bug:) An incident undirected edge adds `1` to the incoming degree and `1` to the outgoing degree at the same time. (This should be the functionality of two non-existing methods `getAllInDegree()` and `getAllOutDegree()`)

## Edges

As mentioned above a new edge is created using

```g.addEdge(n1, n2, true);
```

for some graph `g` containing nodes `n1` and `n2`, where neither the two nodes need to be distinct nor is it required that this edge is the only one connecting these nodes. If the third parameter of `addEdge` always is set to `true`, every edge is directed. Though the graph can be made undirected, which means that it forgets about the direction. This shows that even for undirected graphs the notions source and target of an edge make sense. Given some edge `e` these can easily be obtained via `e.getSource()` and `e.getTarget()` respectively.
Suppose one wants to count all the edges having the same source and target as some edge `e` in a given graph `g`:

```int num = 0;
Iterator outEdgeIt = e.getSource().getDirectedOutEdgesIterator();
while (outEdgeIt.hasNext())
{
Edge f = (Edge) outEdgeIt.next();
if (f.getTarget() == e.getTarget())
{
//
// f and e have the same source and target.
//

++num;
}
}
```

## Graph

### Directed vs. Undirected

As already mentioned in the beginning graphs can be used directed or undirected, even though internally they always will be directed. Mostly we are talking about directed graphs here, because they are more common.
Anyway the introductory chapters gave a short overview of what is affected by toggling the direction-flag of a graph.

### Deletion

Probably as important as the creation of nodes and edges is their deletion. The following methods are provided:

• `g.deleteNode(n)`: deletes node `n` from graph `g`
• `g.deleteEdge(e)`: deletes edge `e` from graph `g`
• `g.clear()`: after this `g` is equally to a newly created graph

Please note that the deletion of some node always implies, that all edges connected to it will be deleted, too.

### Traversing Nodes or Edges

One of the most common thing to do with graphs is to iterate through all its nodes or edges and to perform some action on each of them. Clearly the Java iterator concept is used for this task, like the following example shows:

```Iterator nodeIt = g.getNodesIterator();
while(nodeIt.hasNext())
{
Node n = (Node) nodeIt.next();
if(/* some condition on n */)
{
}
}
```

Collections of graph elements (like here `foundNodes`) can also be obtained by the following methods:

• `g.getNodes()`: all nodes
• `g.getEdges()`: all edges

Furthermore the following counting methods are provided:

• `g.getNumberOfNodes()`: number of nodes
• `g.getNumberOfDirectedEdges()`: number of directed edges
• `g.getNumberOfUndirectedEdges()`: number of undirected edges
• `g.getNumberOfEdges()`: number of all edges

GTL currently supports GML (Graph Modeling Language), GraphML, and the DOT Language (from the Graphviz project) as file-formats. The following code snippets save a graph `g1` and load a graph `g2`, each in GML format:

```import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;

import org.graffiti.graph.Graph;
import org.graffiti.plugins.ios.exporters.gml.GMLWriter;

...

...

GMLWriter gw = new GMLWriter();
File file1 = new File("/some/path/graph_1.gml");
OutputStream os = null;

try
{
os = new FileOutputStream(file1);
}
catch(FileNotFoundException exp)
{
exp.printStackTrace();
}

try
{
gw.write(os, g1);
}
catch(IOException exp)
{
exp.printStackTrace();
}

...

File file2 = new File("/some/other/path/graph_2.gml");
InputStream is = null;
Graph g2 = null;

try
{
is = new FileInputStream(file);
}
catch (FileNotFoundException exp)
{
exp.printStackTrace();
}

try
{
}
catch (IOException exp)
{
exp.printStackTrace();
}

...
```

The I/O routines for loading and saving graphs are realized as plug-ins for Gravisto. Therefore the `Graffiti_Plugins` module must be in your classpath!
The load function opens the file, parses it, and if no error occurs assigns the graph described in it to the graph given as parameter. If an error occurred the an exception `java.io.IOException` is raised.
A file in GML-format is a list of key-value pairs, storing arbitrary information. First the read function scans the file for the key `graph` having a list of key-value pairs as value. This list is scanned for the keys `directed`, `node`, and `edge`, where directed is expected to have an integer as value. The value of `node` has to be a list containing at least a key `id`, which gives this node a unique integer id. The value of `edge` must be a list containing at least the keys `source` and `target` both with a node id as value. The following example is a valid graph description:

```# graph in GML-format

graph [
directed 1
node [ id 0 ]
node [ id 1 ]
node [ id 2 ]
node [ id 3 ]
edge [ source 0 target 1 ]
edge [ source 2 target 3 ]
edge [ source 3 target 0 ]
]
```

Keys not mentioned above are simply ignored. There is no restriction on the order of the `node` and `edge` keys (though the order in the example is the most common). The write function writes exactly the format presented above to a file (or any `OutputStream` given).

## Assigning Data to Graph Elements

Obviously there is a necessity to assign some data, e.g. coordinates for drawing, to nodes and/or edges. Of course for a node `n` this could be done using:

```import java.util.HashMap;
import java.util.Map;

...

Map m = new HashMap();
m.put(n, new Integer(354));
```

But there is a more comfortable and more efficient solution for this task. The graph element objects are able to store data inside. The following could be used to assign an integer `5` to every node and edge of a given graph `g`:

```Iterator nodeIt = g.getNodesIterator();
while(nodeIt.hasNext())
{
Node n = (Node) nodeIt.next();
n.setInteger("guideExample.myIntAttr", 5);
}

Iterator edgeIt = g.getEdgesIterator();
while(edgeIt.hasNext())
{
Edge e = (Edge) edgeIt.next();
e.setInteger("guideExample.myIntAttr", 5);
}
```

Because an element of a graph, e.g. a node `n` can have more than one integer attribute, the first parameter of `setInteger` is a string which defines a unique identifier, the so called path. With this path an arbitrary number of integer attributes can be stored, as long as each has a unique path.
For efficiency reasons each attribute is contained in a hierarchical structure of an attributable element in the graph. To ensure that attributes can be found, they have the unique identifier within their attributable: the path from the root element of the attribute hierarchy to this attribute. This path is not unique outside the concerned attributable. For the definition of the paths we have applied a convention similar to those of the GML-format. A typical path of an attribute can look like "`label.position.alignment`" or "`graphics.coordinate.x`". The root and all internal nodes of the attribute hierarchy are collection attributes, on the other hand the leafs of this hierarchy only consist of either base attributes for primitive types or user-defined attributes. Each attribute in the hierarchy contains a reference to its parent with the exception of the root element.
To obtain an integer attribute stored at a graph element under a given path, e.g. at a node `n` under the path `guideExample.myIntAttr`, one can use `n.getInteger("guideExample.myIntAttr")`. The call of `n.changeInteger("guideExample.myIntAttr", 3)` changes the integer value which is stored under `guideExample.myIntAttr` to `3`. This attribute can be removed from `n` with `n.removeAttribute("guideExample.myIntAttr")`.
Of course there are not only set, change, or get methods for integers. Many other methods for saving attributes are available. Let `a` be an arbitrary attributable element, i.e., a `graph`, a `node`, or an `edge`. Then the following list shows for example all set methods (the names of the respective get and change methods are named canonically):

• `a.setBoolean(String path, boolean value)`: stores a boolean `value` under `path`
• `a.setByte(String path, byte value)`: stores a byte `value` under `path`
• `a.setDouble(String path, double value)`: stores a double `value` under `path`
• ```a.setFloat(String path, float value)```: stores a float `value` under `path`
• ```a.setInteger(String path, int value)```: stores a integer `value` under `path`
• ```a.setLong(String path, long value)```: stores a long integer `value` under `path`
• `a.setShort(String path, short value)`: stores a short integer `value` under `path`
• ```a.setString(String path, String value)```: stores a string `value` under `path`

Further there are methods for storing user defined attributes like `myAttr` (defined in MyAttr.java) in an attributable element, cf. the following example for a node `n`:

```Attribute myAttr1 = new MyAttr("myUserDefAttr");
myAttr1.setValue(new Integer(34));
// add myAttr1 to the attributable n as root attribute

Attribute myAttr2 = n1.getAttribute("myUserDefAttr");

if (myAttr1 == myAttr2)
{
System.out.println("myAttr1 and myAttr2 are equal");
}
else
{
System.out.println("myAttr1 and myAttr2 are not equal");
}
```

The second parameter of `addAttribute` specifies the location of the attribute with the id `"myUserDefAttr"`. In this case this is the empty string because the location is the root element of the hierarchy. User defined attributes currently are not stored in a GML-file.
There is the possibility of labeling nodes or edges such that Graphlet or Gravisto shows this when displaying the graph. For this an attribute with a special path "`label`" exists. The following example shows labeling a node `n` with the string `"a"`:

```LabelAttribute labelAttr = new NodeLabelAttribute("label");
labelAttr.setLabel("a");
```

## Copying Graphs

Graphs can be physically copied, inclusively their graph, node, and edge attributes. For this the method `Graph::copy()` allocates new memory for the copy. That means the copy and the original are semantically the same but physically different, i.e. graph `g2` in the following example is physically different to graph `g1`.

```Graph g1 = new AdjListGraph();
n1.setInteger("guideExample.weight", 3);
n2.setInteger("guideExample.weight", 5);

Graph g2 = (Graph) g1.copy();

int weight = 0;
Iterator it = g2.getNodesIterator();
while (it.hasNext())
{
Node n = (Node) it.next();
weight += n.getInteger("guideExample.weight");
}
```

## Listener Concept

Sometimes some objects may be interested in changes in the data structure. An important example for this are views on the graph. Whenever a change is made then there may be a listener which gets informed about that special event. The `ListenerManager` maintains lists of such listeners. There are many different types of listeners:

• `GraphListener`: gets informed when edges and nodes are added or removed (this includes when the graph is completely cleared)
• `NodeListener`: gets informed about ingoing, outgoing, and undirected adjacent edges that are added or removed to or from this node
• `EdgeListener`: gets informed when a direction is imposed on an edge or the existing direction is altered, as well as when source or target nodes are changed
• `AttributeListener`: gets informed when an attribute has been added, removed, or changed
• `TransactionListener`: gets informed when a transaction is started or finished

A transaction groups a certain sequence of events as one event. Because of the existence of transactions we need two types of listeners, strict and non-strict ones. Strict means that a listener wants to be informed about each single event, even when this event is part of a transaction. As a trade-off on efficiency the listener object is not informed directly on every inner transaction event but the `ListenerManager` stores a list of changed objects during a transaction. Non-strict means that a listener only wants to be informed about events, that means it is informed only once per transaction. The following example registers `mgl` (defined in MyGraphListener.java) as listener on the graph in `ListenerManager` which can be obtained via `Graph::getListenerManager`:

```MyGraphListener mgl = new MyGraphListener();
Another thing to note is that each of this events is split into a "pre" and a "post" event. To catch both of this events `MyGraphListener` in the above example overwrites both methods of `AbstractGraphListener`, `preNodeAdded` and `postNodeAdded`.
The events themselves are small classes that encapsulate the objects that are (probably) modified. `AttributeEvent` holds an attribute, `EdgeEvent` an edge as expected, and `NodeEvent` provides an edge element as well, since these events are all invoked by edge changes and it is easy to access the node via the edge. `GraphEvent` is rather general. Therefore it encapsulates two nodes and an edge.