Overview for Application Developers

This overview will help get you started with using the JGraphT library inyour 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 setof edges. Many possible variations on this fundamental definition aresupported, as we’ll explain further on; but for now, let’s take a lookat a simple example of creating a directed graph:

importorg.jgrapht.*;importorg.jgrapht.graph.*;importorg.jgrapht.nio.*;importorg.jgrapht.nio.dot.*;importorg.jgrapht.traverse.*;importjava.io.*;importjava.net.*;importjava.util.*;Graph<URI,DefaultEdge>g=newDefaultDirectedGraph<>(DefaultEdge.class);URIgoogle=newURI("http://www.google.com");URIwikipedia=newURI("http://www.wikipedia.org");URIjgrapht=newURI("http://www.jgrapht.org");// add the verticesg.addVertex(google);g.addVertex(wikipedia);g.addVertex(jgrapht);// add edges to create linking structureg.addEdge(jgrapht,wikipedia);g.addEdge(google,jgrapht);g.addEdge(google,wikipedia);g.addEdge(wikipedia,google);

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

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

Choosing Vertex and Edge Types

There are a number of restrictions to be aware of when choosing customvertex and edge types, mostly regarding override of theequals/hashCode methods; be sure to read throughthis overview.

Graph Accessors

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

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

Here we iterate over all vertices of the graph via thevertexSet method, filtering for only thosewhose URL haswww.jgrapht.org for its hostname; in our example, we canexpect to find exactly one match, which we obtain viafindAny().get().

Given a reference to a vertex or edge, we can find connections viaGraph methods such asgetEdgeSource,getEdgeTarget,edgesOf,incomingEdgesOf, andoutgoingEdgesOf. Given a pair of vertices,we can find the edge(s) connecting them viagetEdge andgetAllEdges. Here, collection-returning methods should not to beassumed to be live views (although they may be for some graphimplementations). In some cases, the returned collections may beunmodifiable, while in others they may consist of transient results.In no case should an application expect modifications to the returnedcollection to result in modifications to the underyling graph.

TheGraphsutility class has additional convenience methods such assuccessorListOfandgetOppositeVertexfor easing common access patterns.

Note that the default graph implementations guarantee predictableordering for the collections that they maintain; so, for example, ifyou add vertices in the order[B, A, C], you can expect to see them inthat order when iterating over the vertex set. However, this is not arequirement of theGraph interface, so other graph implementationsare not guaranteed to honor it.

Graph Structures

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

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 useDefaultWeightedEdge 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

TheGraphTypeinterface allows you to access this metadata for an existing graphinstance (using thegetTypeaccessor).

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

privatestaticGraph<Integer,DefaultEdge>buildEmptySimpleGraph(){returnGraphTypeBuilder.<Integer,DefaultEdge>undirected().allowingMultipleEdges(false).allowingSelfLoops(false).edgeClass(DefaultEdge.class).weighted(false).buildGraph();}

GraphTypeBuilder uses the property values you supply in order toautomatically choose the correct concrete class for you. This isgenerally a cleaner pattern to follow, but it’s not applicable if youend 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 bycalling theaddVertexandaddEdgemethods on theGraph interface. Likewise, there are correspondingmethods for removing graph components. All of these methods aremodeled on thejava.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
• butattempting to access attributes of an object which is not part of the graph is strictly forbidden, and results in anIllegalArgumentException (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 tohelp catch application errors. There are two convenience helpersavailable to assist with this when adding components to a graph; bothof them take care of automatically adding vertices whenever edges areadded:

• TheGraphs utility class provides methods such asaddEdgeWithVertices
• TheGraphBuilder framework also allows you to usemethod chaining when populating data in a new graph.

Here’s an example usingGraphBuilder to construct akite graph:

privatestaticGraph<Integer,DefaultEdge>buildKiteGraph(){returnnewGraphBuilder<>(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 thereferencing edges are added. Note that building the graph proceeds intwo phases; firstbuildEmptySimpleGraph builds an empty graphinstance for the specified graph type, thenGraphBuilder takes overfor populating the vertices and edges.

Vertex and Edge Suppliers

JGraphT optionally allows you to provide a graph with vertex and edgesuppliers. When these are available, the graph will automaticallyconstruct a new object instance whenever one is not explicitlysupplied by the correspondingadd method.

Modification Listeners

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

• wrap your graph instance viaDefaultListenableGraph
• perform all modifications on the wrapper (not the underlying graph instance)
• register one or moreGraphListener to react to modification events

This can be a convenient way to keep other data structures orvisualizations in sync with graph changes. For example, suppose yourgraph represents a CAD model being visualized; then every time thegraph is edited, all affected views can be automatically refreshedfrom listener events.

Concurrency

The default graph implementations are not safe for concurrent readsand writes from different threads. If an application attempts tomodify a graph in one thread while another thread is reading orwriting the same graph, undefined behavior will result. However,concurrent reads against the same graph from different threads aresafe. (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 usingtheAsSynchronizedGraph wrapper.

Graph Generation

Besides constructing vertices and edges individually, applications canalso generate graph instances according to predefined patterns. Thisis often useful for generating test cases or default topologies.JGraphT provides a number of different generators for this purpose intheorg.jgrapht.generatepackage. Here’s an example of generating acomplete graph:

importorg.jgrapht.*;importorg.jgrapht.generate.*;importorg.jgrapht.graph.*;importorg.jgrapht.traverse.*;importorg.jgrapht.util.*;importjava.util.*;importjava.util.function.*;publicfinalclassCompleteGraphDemo{// number of verticesprivatestaticfinalintSIZE=10;/**     * Main demo entry point.     *      * @param args command line arguments     */publicstaticvoidmain(String[]args){// Create the VertexFactory so the generator can create verticesSupplier<String>vSupplier=newSupplier<String>(){privateintid=0;@OverridepublicStringget(){return"v"+id++;}};// Create the graph objectGraph<String,DefaultEdge>completeGraph=newSimpleGraph<>(vSupplier,SupplierUtil.createDefaultEdgeSupplier(),false);// Create the CompleteGraphGenerator objectCompleteGraphGenerator<String,DefaultEdge>completeGenerator=newCompleteGraphGenerator<>(SIZE);// Use the CompleteGraphGenerator object to make completeGraph a// complete graph with [size] number of verticescompleteGenerator.generateGraph(completeGraph);// Print out the graph to be sure it's really completeIterator<String>iter=newDepthFirstIterator<>(completeGraph);while(iter.hasNext()){Stringvertex=iter.next();System.out.println("Vertex "+vertex+" is connected to: "+completeGraph.edgesOf(vertex).toString());}}}

TheSIZE parameter controls the number of vertices added to thegraph (which in turn dictates the number of edges added).

Graph Traversal

Once you’ve created a graph, you can traverse it using an orderingsuch as depth-first, breadth-first, or topological. JGraphT providesfor this via packageorg.jgrapht.traverse.The common interface isGraphIterator,which specializes the generic JavaIterator interface with JGraphTspecifics. A graph iterator produces vertices in the requested order;as the iteration proceeds, additional information (such as when aparticular edge is traversed) can be obtained by registering aTraversalListener.(The specific meaning of traversal events varies with the iteratortype.)

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

// create a graph based on URI objectsGraph<URI,DefaultEdge>hrefGraph=createHrefGraph();// find the vertex corresponding to www.jgrapht.orgURIstart=hrefGraph.vertexSet().stream().filter(uri->uri.getHost().equals("www.jgrapht.org")).findAny().get();Iterator<URI>iterator=newDepthFirstIterator<>(hrefGraph,start);while(iterator.hasNext()){URIuri=iterator.next();System.out.println(uri);}

with expected output

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

In this example, no extra information is required during thetraversal, so it is treated as a standard JavaIterator.

Graph Algorithms

Beyond basic traversals, you’ll often want to run more complex algorithms ona graph. JGraphT provides quite a few of these, so they are subcategorizedunder theorg.jgrapht.alg parent package.For example, various shortest path algorithms are implemented inorg.jgrapht.alg.shortestpath.

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

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

importorg.jgrapht.*;importorg.jgrapht.alg.connectivity.*;importorg.jgrapht.alg.interfaces.ShortestPathAlgorithm.*;importorg.jgrapht.alg.interfaces.*;importorg.jgrapht.alg.shortestpath.*;importorg.jgrapht.graph.*;importjava.util.*;// constructs a directed graph with the specified vertices and edgesGraph<String,DefaultEdge>directedGraph=newDefaultDirectedGraph<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 graphStrongConnectivityAlgorithm<String,DefaultEdge>scAlg=newKosarajuStrongConnectivityInspector<>(directedGraph);List<Graph<String,DefaultEdge>>stronglyConnectedSubgraphs=scAlg.getStronglyConnectedComponents();// prints the strongly connected componentsSystem.out.println("Strongly connected components:");for(inti=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=newDijkstraShortestPath<>(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 areserializableas long as you choose vertex and edge types which are themselvesserializable.

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

To address this, JGraphT provides moduleorg.jgrapht.iofor 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 inGraphViz .dot format:

DOTExporter<URI,DefaultEdge>exporter=newDOTExporter<>(v->v.getHost().replace('.','_'));exporter.setVertexAttributeProvider((v)->{Map<String,Attribute>map=newLinkedHashMap<>();map.put("label",DefaultAttribute.createAttribute(v.toString()));returnmap;});Writerwriter=newStringWriter();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, youcan also use thetoString 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 edgesare rendered with round brackets, whereas undirected edges arerendered with curly brackets. Custom edge attributes are notrendered. If you want a nicer rendering, you can overridetoStringFromSetsin your graph implementation, but you’re probably better off using oneof the exporters instead.

Graph Cloning

TheGraph interface does not expose a publicclone method, becausewe do not require all implementations to be cloneable. However, allsubclasses ofAbstractBaseGraphare cloneable. The clone semantics are shallow in that the same vertexand edge objects are shared between the original graph and the clone;however, the vertex and edge sets and all associated connectivitystructures are copied, not shared, so that the two graphs are otherwiseindependent.

Graph Comparisons

The default JGraphT implementations of theGraph interface overrideequals/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 fromjava.util.Set, and taking into account theequals implementation of the vertex type you’ve chosen)
• the edges sets of the two graph instances must be equal (again using thejava.util.Set definition, and taking into account theequals 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 viaGraphs.addGraph orclone 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’thold unless both the vertex and edge classes overrideequals/hashCode.

If you were expecting a structural comparison instead, then you mightwant to investigate theisomorphismpackage. In the unrestricted case, isomorphism detection can takeexponential time, but it can be speeded up significantly if you’reable to guide it with a labeling. For example, suppose you have twographs with anonymous edges, but the vertex set is the same, and youwant to decide whether the graphs are effectively equal. In that case, you can run anisomorphism inspector with a comparator specified for the vertices.Then JGraphT can tell you whether the two graphs are structurallyequivalent (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 livetransformed 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 usingGraphs.addGraph.

Graph Adapters

Guava Graph Adapter

If you are already usingcom.google.common.graphfor representing graphs, it’s easy to interoperate with JGraphT byusing ouradapter package.Simply instantiate the correct adapter on top of your Guava graph, andyou’ll have an implementation of JGraphT’sGraph interface whichstays in sync with the Guava graph automatically, at no extra memorycost. Now you canrun 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, thedefault JGraphT representations may eat up too much of your mainmemory. Instead, you can use the adapters provided forWebGraph orsuccinct graphs (via Sux4J).

JGraphX Adapter

JGraphT also provides an adapter that lets you use a JGraphT graphinstance as the data model for aJGraphXvisualization. All you need to do is wrap your JGraphT graph withorg.jgrapht.ext.JGraphXAdapter as in the following example:

importcom.mxgraph.layout.*;importcom.mxgraph.swing.*;importorg.jgrapht.*;importorg.jgrapht.ext.*;importorg.jgrapht.graph.*;importjavax.swing.*;importjava.awt.*;/** * A demo applet that shows how to use JGraphX to visualize JGraphT graphs. Applet based on * JGraphAdapterDemo. * */publicclassJGraphXAdapterDemoextendsJApplet{privatestaticfinallongserialVersionUID=2202072534703043194L;privatestaticfinalDimensionDEFAULT_SIZE=newDimension(530,320);privateJGraphXAdapter<String,DefaultEdge>jgxAdapter;/**     * An alternative starting point for this demo, to also allow running this applet as an     * application.     *     * @param args command line arguments     */publicstaticvoidmain(String[]args){JGraphXAdapterDemoapplet=newJGraphXAdapterDemo();applet.init();JFrameframe=newJFrame();frame.getContentPane().add(applet);frame.setTitle("JGraphT Adapter to JGraphX Demo");frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);frame.pack();frame.setVisible(true);}@Overridepublicvoidinit(){// create a JGraphT graphListenableGraph<String,DefaultEdge>g=newDefaultListenableGraph<>(newDefaultDirectedGraph<>(DefaultEdge.class));// create a visualization using JGraph, via an adapterjgxAdapter=newJGraphXAdapter<>(g);setPreferredSize(DEFAULT_SIZE);mxGraphComponentcomponent=newmxGraphComponent(jgxAdapter);component.setConnectable(false);component.getGraph().setAllowDanglingEdges(false);getContentPane().add(component);resize(DEFAULT_SIZE);Stringv1="v1";Stringv2="v2";Stringv3="v3";Stringv4="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 layoutsmxCircleLayoutlayout=newmxCircleLayout(jgxAdapter);// center the circleintradius=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 thisoverview, seethese instructions.You can also find the full source code ingithub.

Browsing Unit Tests

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