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

- Development Setup
- Hello JGraphT
- Choosing Vertex and Edge Types
- Graph Accessors
- Graph Structures
- Graph Modification
- Graph Generation
- Graph Traversal
- Graph Algorithms
- Graph Serialization and Export/Import
- Graph Cloning
- Graph Comparisons
- Graph Wrappers
- Graph Adapters
- Running Demos
- Browsing Unit Tests

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

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.

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.

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.

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.

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.

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.

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.

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.

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).

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`

.

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

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.

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.

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).

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.

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.

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).

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!...
}
}
```

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.

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.