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.
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
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.
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:
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()
)
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; } }
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.
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.
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:
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.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).
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 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, "");
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"); }
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(); 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.