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)
    {
        Graph g = new AdjListGraph();
        Node n1 = g.addNode();
        Node n2 = g.addNode();
        g.addEdge(n1, n2, true);
    }
}
      

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

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);
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:

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:

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();
Collection foundNodes = new LinkedList();
while(nodeIt.hasNext())
{
    Node n = (Node) nodeIt.next();
    if(/* some condition on n */)
    {
        foundNodes.add(n);
    }
}
      

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

Furthermore the following counting methods are provided:

Loading and Saving Graphs

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.AdjListGraph;
import org.graffiti.graph.Graph;
import org.graffiti.plugins.ios.exporters.gml.GMLWriter;
import org.graffiti.plugins.ios.importers.gml.GMLReader;

...

Graph g1 = new AdjListGraph();

...

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();
}

...

GMLReader gr = new GMLReader();
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
{
    g2 = gr.read(is);
}
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):

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
n.addAttribute(myAttr1, "");

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");
n.addAttribute(labelAttr, "");
      

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();
Node n1 = g1.addNode();
Node n2 = g1.addNode();
n1.setInteger("guideExample.weight", 3);
n2.setInteger("guideExample.weight", 5);
g1.addEdge(n1, n2, true);
        
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:

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();
g.getListenerManager().addNonstrictGraphListener(mgl);
System.out.println("before node addition");
g.addNode();
System.out.println("after node addition");
      

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.
For all listener interfaces abstract classes that provide empty method definitions are available. This is useful because in most applications the "pre" methods will not be needed.