Overview for Application Developers

This overview will help get you started with using the JGraphT library in your own applications. We’ll cover the following topics:

1. Development Setup
2. Hello JGraphT
3. Choosing Vertex and Edge Types
4. Graph Accessors
5. Graph Structures
6. Graph Modification
   1. Vertex and Edge Suppliers
   2. Modification Listeners
   3. Concurrency
7. Graph Generation
8. Graph Traversal
9. Graph Algorithms
10. Graph Serialization and Export/Import
11. Graph Cloning
12. Graph Comparisons
13. Graph Wrappers
14. Graph Adapters
    1. Guava Graph Adapter
    2. Adapters for Very Large Graphs
    3. JGraphX Adapter
15. Running Demos
16. Browsing Unit Tests

Development Setup

First, set up your development environment with JGraphT as a dependency.

Hello JGraphT

In JGraphT, a graph is defined as a set of vertices connected by a set of edges. Many possible variations on this fundamental definition are supported, as we’ll explain further on; but for now, let’s take a look at a simple example of creating a directed graph:

import org.jgrapht.*;
import org.jgrapht.graph.*;
import org.jgrapht.nio.*;
import org.jgrapht.nio.dot.*;
import org.jgrapht.traverse.*;

import java.io.*;
import java.net.*;
import java.util.*;


        Graph<URI, DefaultEdge> g = new DefaultDirectedGraph<>(DefaultEdge.class);

        URI google = new URI("http://www.google.com");
        URI wikipedia = new URI("http://www.wikipedia.org");
        URI jgrapht = new URI("http://www.jgrapht.org");

        // add the vertices
        g.addVertex(google);
        g.addVertex(wikipedia);
        g.addVertex(jgrapht);

        // add edges to create linking structure
        g.addEdge(jgrapht, wikipedia);
        g.addEdge(google, jgrapht);
        g.addEdge(google, wikipedia);
        g.addEdge(wikipedia, google);

Notice how the vertex objects are instances of the java.net.URI class. JGraphT does not supply a vertex class itself; instead, you’re free to choose your own based on whatever works best for your application, subject to certain restrictions mentioned below.

You are also free to choose your own edge class. If you don’t need to associate any application-specific information with your edges, you can just use the library-supplied DefaultEdge as in this example. The graph constructor takes the edge class as a parameter so that it can create new edge objects implicitly whenever addEdge is called to connect two vertices.

Choosing Vertex and Edge Types

There are a number of restrictions to be aware of when choosing custom vertex and edge types, mostly regarding override of the equals/hashCode methods; be sure to read through this overview.

Graph Accessors

Once a graph has been created, an application can access its vertices and edges directly via live set views:

        URI start = hrefGraph
            .vertexSet().stream().filter(uri -> uri.getHost().equals("www.jgrapht.org")).findAny()
            .get();

Here we iterate over all vertices of the graph via the vertexSet method, filtering for only those whose URL has www.jgrapht.org for its hostname; in our example, we can expect to find exactly one match, which we obtain via findAny().get().

Given a reference to a vertex or edge, we can find connections via Graph methods such as getEdgeSource, getEdgeTarget, edgesOf, incomingEdgesOf, and outgoingEdgesOf. Given a pair of vertices, we can find the edge(s) connecting them via getEdge and getAllEdges. Here, collection-returning methods should not to be assumed to be live views (although they may be for some graph implementations). In some cases, the returned collections may be unmodifiable, while in others they may consist of transient results. In no case should an application expect modifications to the returned collection to result in modifications to the underyling graph.

The Graphs utility class has additional convenience methods such as successorListOf and getOppositeVertex for easing common access patterns.

Note that the default graph implementations guarantee predictable ordering for the collections that they maintain; so, for example, if you add vertices in the order [B, A, C], you can expect to see them in that order when iterating over the vertex set. However, this is not a requirement of the Graph interface, so other graph implementations are not guaranteed to honor it.

Graph Structures

Besides choosing your vertex and edge classes, JGraphT also allows you to choose a graph structure. One way to do so is by instantiating a concrete class which implements the Graph interface, as with DefaultDirectedGraph in the example above. When doing so, you can make your selection from the table below (or from your own subclasses of any of these).

Class Name	Edges	Self-loops	Multiple edges	Weighted
SimpleGraph	undirected	no	no	no
Multigraph	undirected	no	yes	no
Pseudograph	undirected	yes	yes	no
DefaultUndirectedGraph	undirected	yes	no	no
SimpleWeightedGraph	undirected	no	no	yes
WeightedMultigraph	undirected	no	yes	yes
WeightedPseudograph	undirected	yes	yes	yes
DefaultUndirectedWeightedGraph	undirected	yes	no	yes
SimpleDirectedGraph	directed	no	no	no
DirectedMultigraph	directed	no	yes	no
DirectedPseudograph	directed	yes	yes	no
DefaultDirectedGraph	directed	yes	no	no
SimpleDirectedWeightedGraph	directed	no	no	yes
DirectedWeightedMultigraph	directed	no	yes	yes
DirectedWeightedPseudograph	directed	yes	yes	yes
DefaultDirectedWeightedGraph	directed	yes	no	yes

The structural properties are as follows:

• undirected edges: an edge simply connects a vertex pair, without imposing a direction
• directed edges: an edge has a source and a target
• self-loops: whether to allow edges which connect a vertex to itself
• multiple edges: whether to allow more than one edge between the same vertex pair (note that in a directed graph, two edges between the same vertex pair but with opposite direction do not count as multiple edges)
• weighted: whether a double weight is associated with each edge (for these graph types, you’ll usually want to use DefaultWeightedEdge as your edge class); unweighted graphs are treated as if they have a uniform edge weight of 1.0, which allows them to be used in algorithms such as finding a shortest path

The GraphType interface allows you to access this metadata for an existing graph instance (using the getType accessor).

You can also use GraphTypeBuilder to instantiate a new graph without directly constructing a concrete class:

    private static Graph<Integer, DefaultEdge> buildEmptySimpleGraph()
    {
        return GraphTypeBuilder
            .<Integer, DefaultEdge> undirected().allowingMultipleEdges(false)
            .allowingSelfLoops(false).edgeClass(DefaultEdge.class).weighted(false).buildGraph();
    }

GraphTypeBuilder uses the property values you supply in order to automatically choose the correct concrete class for you. This is generally a cleaner pattern to follow, but it’s not applicable if you end up needing to subclass one of the provided graph classes.

Graph Modification

Earlier, we saw how to add vertices and edges to a new graph by calling the addVertex and addEdge methods on the Graph interface. Likewise, there are corresponding methods for removing graph components. All of these methods are modeled on the java.util collections framework, so:

• adding a duplicate object to a set (e.g. when adding a vertex) is not an error, but the duplicate is discarded
• adding a duplicate object to a non-unique collection (e.g. when adding an edge to a multigraph) inserts the new instance
• attempting to remove an object which was not part of the graph is not an error
• but attempting to access attributes of an object which is not part of the graph is strictly forbidden, and results in an IllegalArgumentException (e.g. when you ask for the edges of a vertex, but the vertex is not currently part of the graph)

The strictness enforcement mentioned above is the default in order to help catch application errors. There are two convenience helpers available to assist with this when adding components to a graph; both of them take care of automatically adding vertices whenever edges are added:

• The Graphs utility class provides methods such as addEdgeWithVertices
• The GraphBuilder framework also allows you to use method chaining when populating data in a new graph.

Here’s an example using GraphBuilder to construct a kite graph:

    private static Graph<Integer, DefaultEdge> buildKiteGraph()
    {
        return new GraphBuilder<>(buildEmptySimpleGraph())
            .addEdgeChain(1, 2, 3, 4, 1).addEdge(2, 4).addEdge(3, 5).buildAsUnmodifiable();
    }

The integer vertex objects are added to the graph implicitly as the referencing edges are added. Note that building the graph proceeds in two phases; first buildEmptySimpleGraph builds an empty graph instance for the specified graph type, then GraphBuilder takes over for populating the vertices and edges.

Vertex and Edge Suppliers

JGraphT optionally allows you to provide a graph with vertex and edge suppliers. When these are available, the graph will automatically construct a new object instance whenever one is not explicitly supplied by the corresponding add method.

Modification Listeners

JGrapht provides a framework for reacting to graph modifications via the ListenableGraph interface. By default, graph instances are not listenable for efficiency; here’s how to use the framework:

• wrap your graph instance via DefaultListenableGraph
• perform all modifications on the wrapper (not the underlying graph instance)
• register one or more GraphListener to react to modification events

This can be a convenient way to keep other data structures or visualizations in sync with graph changes. For example, suppose your graph represents a CAD model being visualized; then every time the graph is edited, all affected views can be automatically refreshed from listener events.

Concurrency

The default graph implementations are not safe for concurrent reads and writes from different threads. If an application attempts to modify a graph in one thread while another thread is reading or writing the same graph, undefined behavior will result. However, concurrent reads against the same graph from different threads are safe. (Note that the Graph interface itself makes no such guarantee, so for non-default implementations, different rules may apply.)

If you need support for concurrent reads and writes, consider using the AsSynchronizedGraph wrapper.

Graph Generation

Besides constructing vertices and edges individually, applications can also generate graph instances according to predefined patterns. This is often useful for generating test cases or default topologies. JGraphT provides a number of different generators for this purpose in the org.jgrapht.generate package. Here’s an example of generating a complete graph:

import org.jgrapht.*;
import org.jgrapht.generate.*;
import org.jgrapht.graph.*;
import org.jgrapht.traverse.*;
import org.jgrapht.util.*;

import java.util.*;
import java.util.function.*;

public final class CompleteGraphDemo
{
    // number of vertices
    private static final int SIZE = 10;

    /**
     * Main demo entry point.
     * 
     * @param args command line arguments
     */
    public static void main(String[] args)
    {
        // Create the VertexFactory so the generator can create vertices
        Supplier<String> vSupplier = new Supplier<String>()
        {
            private int id = 0;

            @Override
            public String get()
            {
                return "v" + id++;
            }
        };

        // Create the graph object
        Graph<String, DefaultEdge> completeGraph =
            new SimpleGraph<>(vSupplier, SupplierUtil.createDefaultEdgeSupplier(), false);

        // Create the CompleteGraphGenerator object
        CompleteGraphGenerator<String, DefaultEdge> completeGenerator =
            new CompleteGraphGenerator<>(SIZE);

        // Use the CompleteGraphGenerator object to make completeGraph a
        // complete graph with [size] number of vertices
        completeGenerator.generateGraph(completeGraph);

        // Print out the graph to be sure it's really complete
        Iterator<String> iter = new DepthFirstIterator<>(completeGraph);
        while (iter.hasNext()) {
            String vertex = iter.next();
            System.out.println(
                "Vertex " + vertex + " is connected to: "
                    + completeGraph.edgesOf(vertex).toString());
        }
    }
}

The SIZE parameter controls the number of vertices added to the graph (which in turn dictates the number of edges added).

Graph Traversal

Once you’ve created a graph, you can traverse it using an ordering such as depth-first, breadth-first, or topological. JGraphT provides for this via package org.jgrapht.traverse. The common interface is GraphIterator, which specializes the generic Java Iterator interface with JGraphT specifics. A graph iterator produces vertices in the requested order; as the iteration proceeds, additional information (such as when a particular edge is traversed) can be obtained by registering a TraversalListener. (The specific meaning of traversal events varies with the iterator type.)

Here’s an example using depth-first ordering on our HelloJGraphT example:

        // create a graph based on URI objects
        Graph<URI, DefaultEdge> hrefGraph = createHrefGraph();

        // find the vertex corresponding to www.jgrapht.org
        URI start = hrefGraph
            .vertexSet().stream().filter(uri -> uri.getHost().equals("www.jgrapht.org")).findAny()
            .get();

        Iterator<URI> iterator = new DepthFirstIterator<>(hrefGraph, start);
        while (iterator.hasNext()) {
            URI uri = iterator.next();
            System.out.println(uri);
        }

with expected output

http://www.jgrapht.org
http://www.wikipedia.org
http://www.google.com

In this example, no extra information is required during the traversal, so it is treated as a standard Java Iterator.

Graph Algorithms

Beyond basic traversals, you’ll often want to run more complex algorithms on a graph. JGraphT provides quite a few of these, so they are subcategorized under the org.jgrapht.alg parent package. For example, various shortest path algorithms are implemented in org.jgrapht.alg.shortestpath.

In cases where there are alternative algorithms available for the same problem, the commonality is abstracted via an interface in org.jgrapht.alg.interfaces. This makes it easier to write application code which selects an optimal algorithm implementation for a given graph instance.

Here’s an example of running strongly connected components and shortest path algorithms on a directed graph:

import org.jgrapht.*;
import org.jgrapht.alg.connectivity.*;
import org.jgrapht.alg.interfaces.ShortestPathAlgorithm.*;
import org.jgrapht.alg.interfaces.*;
import org.jgrapht.alg.shortestpath.*;
import org.jgrapht.graph.*;

import java.util.*;

        // constructs a directed graph with the specified vertices and edges
        Graph<String, DefaultEdge> directedGraph =
            new DefaultDirectedGraph<String, DefaultEdge>(DefaultEdge.class);
        directedGraph.addVertex("a");
        directedGraph.addVertex("b");
        directedGraph.addVertex("c");
        directedGraph.addVertex("d");
        directedGraph.addVertex("e");
        directedGraph.addVertex("f");
        directedGraph.addVertex("g");
        directedGraph.addVertex("h");
        directedGraph.addVertex("i");
        directedGraph.addEdge("a", "b");
        directedGraph.addEdge("b", "d");
        directedGraph.addEdge("d", "c");
        directedGraph.addEdge("c", "a");
        directedGraph.addEdge("e", "d");
        directedGraph.addEdge("e", "f");
        directedGraph.addEdge("f", "g");
        directedGraph.addEdge("g", "e");
        directedGraph.addEdge("h", "e");
        directedGraph.addEdge("i", "h");

        // computes all the strongly connected components of the directed graph
        StrongConnectivityAlgorithm<String, DefaultEdge> scAlg =
            new KosarajuStrongConnectivityInspector<>(directedGraph);
        List<Graph<String, DefaultEdge>> stronglyConnectedSubgraphs =
            scAlg.getStronglyConnectedComponents();

        // prints the strongly connected components
        System.out.println("Strongly connected components:");
        for (int i = 0; i < stronglyConnectedSubgraphs.size(); i++) {
            System.out.println(stronglyConnectedSubgraphs.get(i));
        }
        System.out.println();

        // Prints the shortest path from vertex i to vertex c. This certainly
        // exists for our particular directed graph.
        System.out.println("Shortest path from i to c:");
        DijkstraShortestPath<String, DefaultEdge> dijkstraAlg =
            new DijkstraShortestPath<>(directedGraph);
        SingleSourcePaths<String, DefaultEdge> iPaths = dijkstraAlg.getPaths("i");
        System.out.println(iPaths.getPath("c") + "\n");

        // Prints the shortest path from vertex c to vertex i. This path does
        // NOT exist for our particular directed graph. Hence the path is
        // empty and the result must be null.
        System.out.println("Shortest path from c to i:");
        SingleSourcePaths<String, DefaultEdge> cPaths = dijkstraAlg.getPaths("c");
        System.out.println(cPaths.getPath("i"));

with expected output

Strongly connected components:
([i], [])
([h], [])
([e, f, g], [(e,f), (f,g), (g,e)])
([a, b, c, d], [(a,b), (b,d), (d,c), (c,a)])

Shortest path from i to c:
[(i : h), (h : e), (e : d), (d : c)]

Shortest path from c to i:
null

Graph Serialization and Export/Import

The default graph implementations provided by JGraphT are serializable as long as you choose vertex and edge types which are themselves serializable.

Serialization is a convenient way to store a graph instance as binary data, but the format is not human-readable, and we don’t make any guarantee of serialization compatibility across JGraphT versions. (In other words, if you serialize a graph with version X, and then attempt to deserialize it with version X+1, an exception may be thrown.)

To address this, JGraphT provides module org.jgrapht.io for exporting and importing graphs in a variety of standard formats. These can also be used for data interchange with other applications.

Continuing our HelloJGraphT example, here’s how to export a graph in GraphViz .dot format:

        DOTExporter<URI, DefaultEdge> exporter =
            new DOTExporter<>(v -> v.getHost().replace('.', '_'));
        exporter.setVertexAttributeProvider((v) -> {
            Map<String, Attribute> map = new LinkedHashMap<>();
            map.put("label", DefaultAttribute.createAttribute(v.toString()));
            return map;
        });
        Writer writer = new StringWriter();
        exporter.exportGraph(hrefGraph, writer);
        System.out.println(writer.toString());

with expected output

strict digraph G {
  www_google_com [ label="http://www.google.com" ];
  www_wikipedia_org [ label="http://www.wikipedia.org" ];
  www_jgrapht_org [ label="http://www.jgrapht.org" ];
  www_jgrapht_org -> www_wikipedia_org;
  www_google_com -> www_jgrapht_org;
  www_google_com -> www_wikipedia_org;
  www_wikipedia_org -> www_google_com;
}

which GraphViz renders as:

If you just want a quick dump of the structure of a small graph, you can also use the toString method; here’s another example from the HelloJGraphT demo:

        System.out.println(stringGraph.toString());

which produces

([v1, v2, v3, v4], [{v1,v2}, {v2,v3}, {v3,v4}, {v4,v1}])

First comes the vertex set, followed by the edge set. Directed edges are rendered with round brackets, whereas undirected edges are rendered with curly brackets. Custom edge attributes are not rendered. If you want a nicer rendering, you can override toStringFromSets in your graph implementation, but you’re probably better off using one of the exporters instead.

Graph Cloning

The Graph interface does not expose a public clone method, because we do not require all implementations to be cloneable. However, all subclasses of AbstractBaseGraph are cloneable. The clone semantics are shallow in that the same vertex and edge objects are shared between the original graph and the clone; however, the vertex and edge sets and all associated connectivity structures are copied, not shared, so that the two graphs are otherwise independent.

Graph Comparisons

The default JGraphT implementations of the Graph interface override equals/hashCode, so it’s possible to use them to compare two graph instances. However, it’s important to note that the definition of equality used may not be the one you are expecting. Here are the rules used:

• the two graph instances must be of identical concrete class (e.g. DefaultDirectedGraph)
• the vertex sets of the two graph instances must be equal (using the definition from java.util.Set, and taking into account the equals implementation of the vertex type you’ve chosen)
• the edges sets of the two graph instances must be equal (again using the java.util.Set definition, and taking into account the equals implementation of the edge type you’ve chosen)
• for a given edge, the source/target/weight must be equal in both graph instances (for undirected graphs, the source/target distinction is ignored)

In general, an exact copy of a graph object via Graphs.addGraph or clone will be equal to the original according to this definition (assuming the same concrete class is chosen for the copy). However, for copy via serialization followed by deserialization, this won’t hold unless both the vertex and edge classes override equals/hashCode.

If you were expecting a structural comparison instead, then you might want to investigate the isomorphism package. In the unrestricted case, isomorphism detection can take exponential time, but it can be speeded up significantly if you’re able to guide it with a labeling. For example, suppose you have two graphs with anonymous edges, but the vertex set is the same, and you want to decide whether the graphs are effectively equal. In that case, you can run an isomorphism inspector with a comparator specified for the vertices. Then JGraphT can tell you whether the two graphs are structurally equivalent (and if so, provide a mapping between the edge objects).

Graph Wrappers

Besides core graph data structures, JGraphT also provides a number of useful wrappers which allow you to define live transformed views into other graphs:

• AsGraphUnion: a union of two underlying graphs
• AsSubgraph: a subgraph (possibly induced) of an underlying graph
• AsUndirectedGraph: an undirected view of an underlying directed graph (with edge directions ignored)
• AsUnmodifiableGraph: an unmodifiable view of an underlying graph
• AsUnweightedGraph: an unweighted view of a underlying weighted graph (ignoring all edge weights and treating them as 1.0 instead)
• AsWeightedGraph: a weighted view of an underlying unweighted graph (with edge-specific weights imposed via a map)
• EdgeReversedGraph: an edge-reversed view of a directed graph

Wrappers add some access cost, so if you don’t need a live view, and you will be accessing the transformed results heavily, then you can copy the view to a snapshot using Graphs.addGraph.

Graph Adapters

Guava Graph Adapter

If you are already using com.google.common.graph for representing graphs, it’s easy to interoperate with JGraphT by using our adapter package. Simply instantiate the correct adapter on top of your Guava graph, and you’ll have an implementation of JGraphT’s Graph interface which stays in sync with the Guava graph automatically, at no extra memory cost. Now you can run JGraphT algorithms on top of your Guava graph, or run our importers or exporters against it.

Adapters for Very Large Graphs

If you are trying to run algorithms over very large graphs, the default JGraphT representations may eat up too much of your main memory. Instead, you can use the adapters provided for WebGraph or succinct graphs (via Sux4J).

JGraphX Adapter

JGraphT also provides an adapter that lets you use a JGraphT graph instance as the data model for a JGraphX visualization. All you need to do is wrap your JGraphT graph with org.jgrapht.ext.JGraphXAdapter as in the following example:

import com.mxgraph.layout.*;
import com.mxgraph.swing.*;
import org.jgrapht.*;
import org.jgrapht.ext.*;
import org.jgrapht.graph.*;

import javax.swing.*;
import java.awt.*;

/**
 * A demo applet that shows how to use JGraphX to visualize JGraphT graphs. Applet based on
 * JGraphAdapterDemo.
 *
 */
public class JGraphXAdapterDemo
    extends JApplet
{
    private static final long serialVersionUID = 2202072534703043194L;

    private static final Dimension DEFAULT_SIZE = new Dimension(530, 320);

    private JGraphXAdapter<String, DefaultEdge> jgxAdapter;

    /**
     * An alternative starting point for this demo, to also allow running this applet as an
     * application.
     *
     * @param args command line arguments
     */
    public static void main(String[] args)
    {
        JGraphXAdapterDemo applet = new JGraphXAdapterDemo();
        applet.init();

        JFrame frame = new JFrame();
        frame.getContentPane().add(applet);
        frame.setTitle("JGraphT Adapter to JGraphX Demo");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.pack();
        frame.setVisible(true);
    }

    @Override
    public void init()
    {
        // create a JGraphT graph
        ListenableGraph<String, DefaultEdge> g =
            new DefaultListenableGraph<>(new DefaultDirectedGraph<>(DefaultEdge.class));

        // create a visualization using JGraph, via an adapter
        jgxAdapter = new JGraphXAdapter<>(g);

        setPreferredSize(DEFAULT_SIZE);
        mxGraphComponent component = new mxGraphComponent(jgxAdapter);
        component.setConnectable(false);
        component.getGraph().setAllowDanglingEdges(false);
        getContentPane().add(component);
        resize(DEFAULT_SIZE);

        String v1 = "v1";
        String v2 = "v2";
        String v3 = "v3";
        String v4 = "v4";

        // add some sample data (graph manipulated via JGraphX)
        g.addVertex(v1);
        g.addVertex(v2);
        g.addVertex(v3);
        g.addVertex(v4);

        g.addEdge(v1, v2);
        g.addEdge(v2, v3);
        g.addEdge(v3, v1);
        g.addEdge(v4, v3);

        // positioning via jgraphx layouts
        mxCircleLayout layout = new mxCircleLayout(jgxAdapter);

        // center the circle
        int radius = 100;
        layout.setX0((DEFAULT_SIZE.width / 2.0) - radius);
        layout.setY0((DEFAULT_SIZE.height / 2.0) - radius);
        layout.setRadius(radius);
        layout.setMoveCircle(true);

        layout.execute(jgxAdapter.getDefaultParent());
        // that's all there is to it!...
    }
}

Running Demos

If you want to run the demo programs excerpted throughout this overview, see these instructions. You can also find the full source code in github.

Browsing Unit Tests

Another good way to learn how to use the various classes provided by JGraphT is to study their usage in unit tests. Here’s the source code of tests for the core classes.