JGraphT
JGraphT supports a very wide
range of graph theory data structures and algorithms. But the examples
here deliberately use only a small number of graph classes:
- For unweighted graphs, either SimpleGraph
(for undirected graphs) or DefaultDirectedGraph
(directed), limited to
the DefaultEdge class for the edges;
- For weighted graphs, either SimpleWeightedGraph (undirected)
or DefaultDirectedWeightedGraph (directed), limited to
my WeightedEdge class
for the edges, a subclass of DefaultWeightedEdge.
MakeGraphs.java contains brief examples
of these four graph types.
Another aim is to demonstrate the easy loading
and saving of graphs stored in text files, either as adjacency lists,
matrices, or in GraphML
format. This is implemented by various methods in
JGTUtils.java, and illustrated by
examples in LoadAdjList.java,
LoadAdjMatrix.java, and
LoadGraphML.java.
A third goal is to make it easy to visualize graphs, either
textually as adjacency lists
or matrices, or graphically by using
GraphViz or JGraphX
methods. The use of GraphViz requires a separate
download, but the
JGraphX libraries are included in JGraphT.
My Examples
- MakeGraphs.java:
create weighted/unweighted, directed/undirected graphs.
- LoadAdjList.java,
LoadAdjMatrix.java,
LoadGraphML.java: load
and save graphs as adjacency lists, adjacency matrices,
or as GraphML
files. They use adjlist1.txt,
adjlist2.txt,
mat1.txt,
mat2.txt,
g1.graphml, and
g2.graphml.
- Connectivity.java and
StrongConnectivity.java:
how to detect connected components in graphs.
- DetectCycles.java,
EulerCycle.java, and
HamCycle.java: general cycle detection
with topological ordering, and Euler and Hamiltonian cycles.
- DGTraversal.java and
DepthListener.java:
depth-first and breadth-first traversal over graphs.
- Spanning.java: the
discovery of minimal spanning trees using either Prim's or
Kruskal's algorithm.
- DGShortest.java:
the application of the Dijkstra, Bellman-Ford,
and Floyd-Warshall shortest path algorithms to directed graphs.
- Bipartite.java: the
separation of a bipartite graph into two sets.
- DGMaxFlow.java: the
utilization of the Edmonds-Karp algorithm to find the
maximum flow through a directed graph.
- Planarity.java:
planarity testing of a graph, and details on a possible
clockwise ordering of its vertices.
- WeightedEdge.java: my
subclass of DefaultWeightedEdge, used to represent
weighted edges in all of these examples.
- JGTUtils.java: utility methods,
mainly focused on reading/writing adjacency lists, adjacency
matrices, and GraphML files, and on graph drawing using
GraphViz and JGraphX.
- ImageViewer.java: for
displaying an image in a window.
Other Downloads and Links
- Batch files to easily compile and run my code:
compile.bat and
run.bat
- All the examples in one zipped file
(28 KB)
- My copies of some of the
JGraphT libraries (2.58 MB), restricted to those necessary to get
these examples to compile and run.
They are jgrapht-core-1.5.1.jar,
jgrapht-io-1.5.1.jar,
jgrapht-ext-1.5.1.jar,
jgraphx-4.1.0.jar,
jheaps-0.13.jar, and
antlr4-runtime-4.8-1.jar.
Unzip the file, and place the libs folder in the
same directory as the examples and batch files.
- The JGraphT
official libraries (v.1.5.1).
- Graph visualization using GraphViz requires its
downloading.
- The JGraphT User
Guide, its wiki,
and an introduction
by Baeldung.
- The JGraphT API documentation.
- JGraphX, the API used for graph visualization by JGraphT, has
its own
web site,
user manual, and
API
documentation.
Dr. Andrew Davison
E-mail: ad@coe.psu.ac.th
Back to the third-party libraries page