GRAD
Graph Drawing and Analysis Library
for Java
What GRAD offers
GRAPH
ANALYSIS

Dijkstra's shortest path

Depthfirst 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

HopcroftTarjan division of graph into triconnected components

Construction of BC (blockcut 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

FraysseixMendez planarity testing

BoyerMyrvold planarity testing, including calculation of the outside face

PQtree 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 stordering
Other
Automatic Selection and Configuration of the Algorithm
GRAPH
DRAWING

Spring (ported from JUNG framework)

KamadaKawai (ported from JUNG framework)

FruchtermanReingold (ported from JUNG framework)

ISOM (ported from JUNG framework)

Organic and fast organic (ported from JGraphX)
ForceDirected Algorithms

Tutte straightline drawing

Chiba's convex straightline drawing

Orthogonal based on visibility representations (in development)
StraightLine Drawing

HorizontalVertical tree drawing (ported from JUNG framework)

Radial tree drawing (ported from prefuse)

Balloon tree drawing (ported from prefuse)

NodeLink 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 tablelike structure)
Other

Based on graph's properties

Based on user's description
GRAD is an opensource 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 KamadaKawai, 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:

Manual invocation, like in code listing 1 shown below.

Using a domainspecific 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:

A list of vertices.

A list of edges.

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

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 KamadaKawai 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
LAYOUT EXAMPLES
Balloon tree
Levelbased tree
Radial tree
Symmetric
Circular
Hierarchical
Various forcedirected
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 domainspecific 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
â€‹