Basic Graphs

2 Basic Graphs

Although JAGAL has some visualization capabilities, we first consider underlying classes and interfaces.

All graph classes build upon the abstract class AbstractGraph<V,E,U>, where V is the vertex type, E the type of edges, and U the type of the element enclosed by the vertex. The class defines basic operations, which can be performed on graphs, like adding and removing vertices and edges, getting meta information about a graph and its components like the in- and out-degree of a vertex, its successors etc., and getting topological information about a graph and its components.

The basic classes for vertices and edges are called Vertex<U> and Edge<V>, which depend on the vertex type. Based on these classes, two graph types are predefined:

  1. A directed unweighted graph only allows directed edges, which aren’t weighted. Its main class is Graph<U>, where U defines the type of the vertex labels.
  2. A directed weighted graph complements the unweighted graph by edge weights, which are floating number values. The class WeightedGraph<U> therefore uses the class WeightedEdge<V> for the edges.

In the following sections some simple examples for the visualization of the graphs and use cases with graph algorithms using these classes are presented.

2.1 Creating a Directed Graph

As an example a simple directed graph is created. As type of the vertex elements we choose Integer.

// Graph<U> where U is the type of the vertex elements
Graph<Integer> g = new Graph<Integer>();
// Add some vertices
g.addVertex("A", 4);

g.addVertex("B", 3);
g.addVertex("C", 1);
g.addVertex("D");
g.getVertex("D").setElement(2);
g.addVertex("E", 8);

// Add some edges
g.addEdge("A", "B");
g.addEdge("B", "C");
g.addEdge("B", "D");
g.addEdge("C", "A");
g.addEdge("C", "D");
g.addEdge("D", "E");
g.addEdge("E", "B");
// Let’s take a look at the result
System.out.println(g);
System.out.println(g.getVertex("E").getElement());

Printing out the graph results in the following output:

Graph: V=[A, B, C, D, E]
       E=[(A -> B), (B -> C), (B -> D), (C -> A),

          (C -> D), (D -> E), (E -> B)]

Note that vertices are created with their name. When creating edges, they also refer to the vertex names instead of the vertex objects. If a vertex with a given name already exists, the addVertex()-method does not add a new vertex and returns false. If an unknown vertex name is referred to when creating an edge, the addEdge-method throws a VertexNotFoundException.

Now it is possible to request some meta information from the graph. For example the in-degree of the vertex D can be retrieved using g.inDegreeOf(“D”) (which would result in 2) and the method g.isDrain(“A”) returns false, since the vertex A has a successor.

2.2 Creating a Directed Weighted Graph

JAGAL already comes with a class for directed weighted graphs. In this section, we create a simple graph with weighted edges. Weights are floating number values. By default all edges have a weight of 1.0.

// WeightedGraph<U> where U is the vertex element type
WeightedGraph<Integer> gw = new WeightedGraph<Integer>();
// Add some vertices
gw.addVertex("A");
gw.addVertex("B");
gw.addVertex("C");
gw.addVertex("D");
gw.addVertex("E");
// Add some edges
gw.addEdge("A", "B");
gw.addEdge("B", "C");
gw.addEdge("B", "D", 2.0);
gw.addEdge("C", "A", 3.4);
gw.addEdge("C", "D");
gw.addEdge("D", "E");
gw.addEdge("E", "B");

// Let’s take a look at the result
System.out.println(gw);

The output of the weighted graph is the following:

Graph: V=[D, E, A, B, C]
       E=[(A-1.0->B), (B-1.0->C), (B-2.0->D), (C-3.4->A),

          (C-1.0->D), (D-1.0->E), (E-1.0->B)]

2.3 Visualizing Graphs

The JAGAL library also comes with visualization capabilities. With the following com- mand a new JFrame gets created, where the class DisplayFrame is part of the TOVAL library (see figure 1a):

new DisplayFrame(new GraphComponent(g), true);

For the visualization of weighted directed graphs, JAGAL comes with another compo- nent class named WeightedGraphComponent. It complements the standard graph repre- sentation by edge labels with the specified weights. The resulting graph visualization can be seen in figure 1b.

new DisplayFrame(new WeightedGraphComponent(gw), true);