top of page

GRAD

Graph Drawing and Analysis Library

for Java

What GRAD offers

GRAPH
ANALYSIS

  • Dijkstra's shortest path

  • Depth-first search and construction of DFS trees

Graph Traversal

  • Checking connectivity, biconnectivity and triconnectivity of graphs

  • Finding graph's cut vertices and blocks (biconnected components) of a graph

  • Hopcroft-Tarjan division of graph into triconnected components

  • Construction of BC (block-cut vertex) trees

  • Construction of SPQR trees

  • Planar augmentation  (turning a connected graph into a biconnected one)

Graph Connectivity

  • Johnson's algorithms for finding cycle basis of a directed graph

  • Paton's algorithm for finding cycle basis of an undirected graph

Cyclic Properties

  • Fraysseix-Mendez planarity testing

  • Boyer-Myrvold planarity testing, including calculation of the outside face

  • PQ-tree planarity testing (Booth and Lueker's algorithm), including finding the upwards embedding

  • Finding an embedding and planar faces of a graph given an upwards embedding

Planarity Testing

  • McKay's canonical graph labeling algorithm (nauty) for finding permutations

  • De Fraysseix's heuristic for graph symmetry detection

  • Analyzing permutations and finding permutation groups

  • Forming permutation cycles

Graph Symmetry

  • Checking if a graph is bipartite

  • Checking if a tree is binary

  • Finding topological ordering

  • Finding st-ordering

Other

Automatic Selection and Configuration of the Algorithm

GRAPH
DRAWING

  • Spring (ported from JUNG framework)

  • Kamada-Kawai (ported from JUNG framework)

  • Fruchterman-Reingold (ported from JUNG framework)

  • ISOM (ported from JUNG framework)

  • Organic and fast organic (ported from JGraphX)

Force-Directed Algorithms

  • Tutte straight-line drawing

  • Chiba's convex straight-line drawing

  • Orthogonal based on visibility representations (in development)

Straight-Line Drawing 

  • Horizontal-Vertical tree drawing (ported from JUNG framework)

  • Radial tree drawing (ported from prefuse)

  • Balloon tree drawing (ported from prefuse)

  • Node-Link tree drawing (ported from prefuse)

  • Compact tree drawing (ported from JGraphX)

  • Hierarchical algorithm (ported from JGraphX)

Tree and Hierarchical Drawing

  • Concentric symmetric drawing based on Car and Kocay's algorithm

Symmetric Drawing

  • Circular layout:

    • with minimization of the number of edge crossings

    • without minimization of the number of edge crossing (  faster but might not produce equally nice drawings)

  • Circular around a central specified vertex

Circular Drawing

  • Box Layout (places graph's vertices into a table-like structure)

Other

  • Based on graph's properties

  • Based on user's description

GRAD is an open-source library and it can be found on GitHub

 Using the library

//choose an algorithm by choosing an enumeration value

LayoutAlgorithms algorithm = LayoutAlgorithms.KAMADA_KAWAI;

//optionally, set layout properties

//default values are used for properties that weren't manually configured

GraphLayoutProperties layoutProperties = new GraphLayoutProperties();

//match the enumeration with the algorithm

//for example, if we want to call Kamada-Kawai, we need KamadaKawaiProperties

layoutProperties.setProperty(KamadaKawaiProperties.LENGTH_FACTOR, 5);

layoutProperties.setProperty(KamadaKawaiProperties.DISCONNECTED_DISTANCE_MULTIPLIER, 3);

//Layouter is the central class concerned with laying out graphs (diagrams)

//just like GRAD's graph and many other classes, it is parameterized

//it only necessary to pass lists of vertices and edges

//and instance of the graph class will automatically be created

Layouter<GraphVertex, GraphEdge> layouter = new Layouter<>(vertices, edges, 

                                                           algorithm, layoutProeprties);

//Execute the algorithm and retrieve the results

Drawing<GraphVertex, GraphEdge> drawing = layouter.layout();

Map<GraphVertex, Point2D> vertexPositions = drawing.getVertexMappings();

Map<GraphEdge, List<Point2D>> edgePositions = drawing.getEdgeMappings();

​

GRAD provides a large number of different graph analysis and drawing algorithms and any of them can be used if so is desired.  Documentation in the form of Javadoc can be found here. GRAD, however, puts emphasis on making it very easy to call any of its layout algorithms and retrieve the results - positions of the graph's elements (vertices and edges). Since any diagram which consists of elements which can be connected with each other can be seen as a graph (class, activity, ER , electrical schemas etc.), the library can be used by many different graphical editors.

​

A layout algorithm can be called using two methods:

  1. Manual invocation, like in code listing 1 shown below.

  2. Using a domain-specific language, which will later be described in more detail.

Regardless ​of which method is used, it is not necessary to create an instance of GRAD's graph class in order to call a layout algorithm. It is enough to provide lists of vertices and edges. All GRAD's algorithms are parameterized, so any two classes can represent the mentioned elements. However, they need to implement interfaces Vertex and Edge, which contain methods for defining properties such as size of a vertex and source and destination of an edge, since that information is required by the algorithms. If for any reason it is not possible to implement the two interfaces, GRAD provides classes GraphVertex and GraphEdge which already fulfill the said requirement. So, an instance of one of the two classes can be created for each of the diagram's elements before an algorithm is invoked.

The first method of laying out a diagram involves calling the layout method of the Layouter class. The method has 4 parameters, with the last one being optional:

  1. A list of vertices.

  2. A list of edges.

  3. A specification of which layout algorithm is used - a value of LayoutAlgorithms enumeration.

  4. Properties of the algorithm, defined by creating a GraphLayoutProperties object. For each algorithm with configurable parameters, a separate enumeration is defined, listing all such parameters. For example, if Kamada-Kawai algorithm is used, the appropriate enumeration is called KamadaKawaiProperties. To specify a value of a property, the setProperty(property, value)method of GraphLayoutProperties is to be called. It is not necessary to provide values of all parameters of an algorithm, in which case default values will be set to all omitted ones.

The ​layout method returns an instance of the Drawing object, which contains mappings of vertices to their calulated positions and edges to lists of positions of their nodes.

​

A class diagram showing the relevant classes  and enumerations, as well as relationships between them is shown in figure 1, while an example of how a layout algorithm is called is shown in code listing 1. ​

​

​

​

​

​

Figure 1 Classes involved in the layout process, showing only a small subset of Properties enumerations.

Code listing 1 Directly calling a layout algorithm and retrieving the results 

overview
examples
how to use
automatic layout
DSL

LAYOUT EXAMPLES

Balloon tree

Level-based tree

Radial tree

Symmetric

Circular

Hierarchical

Various force-directed

Circular around a vertex

Orthogonal (still in development)

Convex

Automatic Layout

Layouter<GraphVertex, GraphEdge> layouter = new Layouter<>(vertices, edges, 

                                                           LayoutAlgorithms.AUTOMATIC);

Drawing<GraphVertex, GraphEdge> drawing = layouter.layout();

For those not particularly familiar with graph drawing algorithms, GRAD provides a way of automatically picking an appropriate one. This can be done in two ways:

  • By instructing GRAD to analyze the graph and determine the layout algorithm based on its properties.

  • By specifying which properties the drawing should exhibit.

The first is simpler, but provides less control to the user. It focuses on the fact that some algorithms are meant to be used only if a graph has certain properties, while the others are very flexible and can be used to lay out any graph with satisfying results. Naturally, if a  graph does have the desired properties, using a specialized algorithm to lay it out is a better option compared to a more general one. So, this feature checks if the graph has any of these properties and picks the algorithm based on the results of the analysis. In order to use it, it is only needed to specify AUTOMATIC as the value of the  layout algorithm parameter, as shown in code listing 2:

​

​

​

 

 

 

Drawing algorithms tend to focus on certain aesthetic criteria, with their authors claiming that drawings which conform to those criteria are more readable and easy to understand. The following are the most popular criteria:

  • Minimization of the number of edge crosses,

  • Maximization of the minimal angle between edges extending from a node,

  • Minimization of the total number of bends in polyline edges,

  • Even distribution of edges within a bounding box,

  •  Appropriate lengths of edges, neither too short nor too long,

  •  Similar length of edges,

  • Same flow of edges in directed graphs (as much as possible),

  • Orthogonality – fixing nodes and edges to an orthogonal grid,

  • Symmetry – preference of a symmetrical view of the graph.

​​

The second way of laying out a diagram without directly specifying the layout algorithm allows defining how the drawing should look by naming one or more aesthetic criteria. This is done by passing a String to the layouter class instead of the enumeration value naming the algorithm, which is demonstrated in code listing 3. The String should conform to the domain-specific language, more on which later. Based on those instructions, an algorithm that focuses on all or almost all of the criteria is chosen. Naturally, some combinations cannot be satisfied in their entirety. For example, it might not be impossible to create a planar symmetric drawing, which is why some listed criteria might have to be ignored.

​

//very similar to the previous code sample, but the DSLLayouter class is used instead of

//Layouter

String instructions = "layout graph criteria distribute nodes evenly, minimize edge crossings";

DSLLayouter<GraphVertex, GraphEdge> layouter = new DSLLayouter<>(vertices, edges, instructions);

Drawing<GraphVertex, GraphEdge> drawing = layouter.layout();

Code listing 3 The second way of invoking the automated layout process

Code listing 2 The first way of invoking the automated layout process

Layout DSL

GRAD enables users to specify how a graph should be laid out using a domain specific language in several ways. From the one that requires the least knowledge about graph drawing theory to the one that requires the most, they are:

  • Naming the general style of the layout (hierarchy, circular, symmetric etc.), including the possibility of stating that the lay out process should be done automatically

  • Naming aesthetic criterion or criteria that the drawing should conform to (minimization of edge crossings, maximization of minimum angles, uniform flow etc.)

  • Directly naming the layout algorithm that should be applied and optionally setting its configurable parameters.

It is also possible to define if the whole graph should be laid out, or just some of its parts (subgrahs). 

​

The syntax of the language was defined the way it was with the intention of emulating the feeling of ordering someone to do something. Or in this case, to lay out a graph or its subgraphs according to your wishes.

 

The language was defined using textX and the complete specification can be found here:

Publications

2016:

Renata Vaderma, Igor Dejanović, Gordana Milosavljević, GRAD: A New Graph Drawing and Analysis Library, 4th Workshop on Model Driven Approaches in System Development (MDASD '16), Gdansk, Poland

Renata Vaderma, Gordana Milosavljević, Igor Dejanović, , 25th International Electrotechnical and Computer Science Conference (ERK '16), Portorož, Slovenia

2015:

Renata Vaderma, Gordana Milosavljević, Igor Dejanović, Graph Layout Algorithms and Libraries: Overview and Improvements, ICIST, Kopaonik

​

LINKS
CONTACT

vrenata@uns.ac.rs

Renata Vaerna

Faculty of Technical Sciences, University of Novi Sad

GRAD

bottom of page