JGraphT  0.8.3
 

Released: January, 2012

Written by Barak Naveh (barak_naveh@users.sourceforge.net) and Contributors.

(C) Copyright 2003-2012, by Barak Naveh and Contributors. All rights reserved.

Please address all contributions, suggestions, and inquiries to the current project administrator, John Sichi.

Introduction

JGraphT is a free Java class library that provides mathematical graph-theory objects and algorithms. It runs on Java 2 Platform (requires JDK 1.6 or later).

JGraphT is licensed under the terms of the GNU Lesser General Public License (LGPL). A copy of the license is included in the download.

Please note that JGraphT is distributed WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. Please refer to the license for details.

Contents

Getting Started

The package org.jgrapht.demo includes small demo applications to help you get started. If you spawn your own demo app and think others can use it, please send it to us and we will add it to that package.

Upgrading Versions

To help upgrading, JGraphT maintains a one-version-backwards compatibility. While this compatibility is not a hard promise, it is generally respected. (This policy was not followed for the jump from 0.6.0 to 0.7.0 due to the pervasive changes required for generics.) You can upgrade via:

• The safe way : compile your app with the JGraphT version that immediately follows your existing version and follow the deprecation notes, if they exist, and modify your application accordingly. Then move to the next version, and on, until you're current.

• The fast way : go to the latest JGraphT right away - if it works, you're done.

Reading the change history is always recommended.

Documentation

A local copy of the Javadoc HTML files is included in this distribution. The latest version of these files is also available on-line at http://www.jgrapht.org/javadoc.

Dependencies

• JGraphT requires JDK 1.6 or later to build.
   
• JUnit is a unit testing framework. You need JUnit only if you want to run the unit tests. The junit.jar runtime file is included in this distribution. JUnit is licensed under the terms of the IBM Common Public License. You can find out more about JUnit and/or download the latest version from http://www.junit.org. The JUnit tests included with JGraphT have been created using JUnit 3.8.1.
   
• XMLUnit extends JUnit with XML capabilities. You need XMLUnit only if you want to run the unit tests. The xmlunit-1.0.jar runtime file is included in this distribution. XMLUnit is licensed under the terms of the BSD License. You can find out more about XMLUnit and/or download the latest version from http://xmlunit.sourceforge.net.
• JGraph is a graph visualization and editing component. You need JGraph only if you want to create graph visualizations using the JGraphT-to-JGraph adapter. The jgraph.jar runtime file of JGraph is included in this distribution (file lib/lib-readme.txt has version information). JGraph is licensed under the terms of the GNU Lesser General Public License (LGPL). You can find more about JGraph and/or download the latest version from http://www.sourceforge.net/projects/jgraph.
   
• Touchgraph is a graph visualization and layout component. You need Touchgraph only if you want to create graph visualizations using the JGraphT-to-Touchgraph converter. The TGGraphLayout.jar runtime file of Touchgraph is included in this distribution (file lib/lib-readme.txt has version information). Touchgraph is licensed under the terms of an Apache-style License. You can find more about Touchgraph and/or download the latest version from http://sourceforge.net/projects/touchgraph.

Online Resources

The JGraphT website is at: http://www.jgrapht.org. You can use this site to:

• Obtain the latest version : latest version and all previous versions of JGraphT are available online.
• Report bugs : if you have any comments, suggestions or bugs you want to report.
• Get support : if you have questions or need help with JGraphT.

There is also a wiki set up for everyone in the JGraphT community to share information about the project.

Your Improvements

If you add improvements to JGraphT please send them to us. We will add them to the next release so that everyone can enjoy them. You might also benefit from it: others may fix bugs in your source files or may continue to enhance them.

History

Changes to JGraphT in each version:

• version 0.8.3 (20-Jan-2012): fix regression in DOTExporter inadvertently introduced by 0.8.2 changes. Add GridGraphGenerator, contributed by Assaf Mizrachi. Return coloring from ChromaticNumber, contributed by Harshal Vora. Fix bugs in KSP, contributed by Guillaume Boulmier; note that these bugfixes worsen the running time. Fix an object identity bug in CycleDetector, contributed by Matt Sarjent. Add StoerWagnerMinimumCut, contributed by Robby McKilliam. Fix MANIFEST.MF, spotted by Olly. Make FloydWarshallShortestPaths.getShortestPaths unidirectional, contributed by Yuriy Nakonechnyy.
• version 0.8.2 (27-Nov-2010): Clean up FibonacciHeapNode constructor, as suggested by Johan Henriksson. Optimize and enhance FloydWarshallShortestPaths, contributed by Soren Davidsen. Optimize ChromaticNumber, pointed out by gpaschos@netscape.net. Add unit test for FloydWarshallShortestPaths for bug noticed by Andrea Pagani. Add vertex factory validation to RandomGraphGenerator to prevent a confusing problem encountered by Andrea Pagani. Add KruskalMinimumSpanningTree and UnionFind, contributed by Tom Conerly. Add attributes to DOTExporter, based on suggestion from Chris Lott. Fix inefficient assertion in TopologicalOrderIterator, spotted by Peter Lawrey. Fix induced subgraph bug with addition of edge to underlying graph, contributed by Michele Mancioppi. Make getEdgeWeight delegate to DefaultWeightedEdge.getWeight, spotted by Michael Lindig. Add maven support, contributed by Adrian Marte.
• version 0.8.1 (3-Jul-2009): Enhanced GmlExporter with customized labels and ID's, contributed by Trevor Harmon. Added new algorithms HamiltonianCycle, ChromaticNumber and EulerianCircuit, plus new generators HyperCubeGraphGenerator, StarGraphGenerator, and CompleteBipartiteGraphGenerator, all contributed by Andrew Newell. Fix bug with vertices which are equals but not identity-same in graphs allowing loops, spotted by Michael Michaud. Fix bug in EquivalenceIsomorphismInspector, reported by Tim Engler. Add toString for shortest paths wrapper, spotted by Achim Beutel. Add FloydWarshallShortestPaths, contributed by Tom Larkworthy. Enhance DijskstraShortestPath to support GraphPath interface. Add GraphUnion (with directed and undirected variants), contributed by Ilya Razenshteyn.
• version 0.8.0 (Sept-2008): Moved to JDK 1.6. Fixed problem with RandomGraphGenerator reported by Mario Rossi. Added CompleteGraphGenerator, contributed by Tim Shearouse. Fixed FibonacciHeap performance problem reported by Jason Lenderman. Made DotExporter reject illegal vertex ID's, contributed by Holger Brandl. Fixed bogus assertion for topological sort over empty graph, spotted by Harris Lin. Added scale-free graph generator and EdmondsKarpMaximumFlow, contributed by Ilya Razenshteyn. Added DirectedAcyclicGraph, contributed by Peter Giles. Added protected getWeight accessor to DefaultWeightedEdge, likewise getSource and getTarget on DefaultEdge. Optimized iterators to skip calling event firing routines when there are no listeners, and used ArrayDeque in a number of places, per suggestion from Ross Judson. Improvements to StrongConnectivityInspector and OSGi bundle support contributed by Christian Soltenborn.
• version 0.7.3 (Jan-2008): Patch to JGraphModelAdapter.removeVertex provided by Hookahey. Added ParanoidGraph. Removed obsolete ArrayUtil (spotted by Boente). Added GraphPath, and used it to fix mistake in 0.7.2 (k-shortest-paths was returning a private data structure, as discovered by numerous users). Fixed EdgeReversedGraph.getAllEdges (spotted by neumanns@users.sf.net). Fixed incorrect assertion in TopologicalOrderIterator constructor. Enabled assertions in JUnit tests. Fixed NPE in BellmanFordShortestPath.getCost. Fixed a few problems spotted by findbugs.
• version 0.7.2 (Sept-2007): Added TransitiveClosure, contributed by Vinayak Borkar. Added biconnectivity/cutpoint inspection, k-shortest-paths, and masked subgraphs, all contributed by Guillaume Boulmier. Made some Graphs helper methods even more generic, as suggested by JongSoo. Test and fixes for (Directed)NeighborIndex submitted by Andrew Berman. Added AsUnweighted(Directed)Graph and AsWeightedGraph, contributed by Lucas Scharenbroich. Dropped support for retroweaver.
• version 0.7.1 (March-2007): Fixed some bugs in CycleDetector reported by Khanh Vu, and added more testcases for it. Fixed bugs in DepthFirstIterator reported by Welson Sun, and added WHITE/GRAY/BLACK states and vertexFinished listener event. Exposed Subgraph.getBase(), and parameterized Subgraph on graph type (per suggestion from Aaron Harnly). Added EdgeReversedView. Added GmlExporter (contributed by Dimitrios Michail), plus DOTExporter and GraphMLExporter (both contributed by Trevor Harmon). Enhanced TopologicalOrderIterator to take an optional Queue parameter for tie-breaking (per suggestion from JongSoo Park). Fixed some documentation errors reported by Guillaume Boulmier.
• version 0.7.0 (July-2006) : Upgraded to JDK 1.5 (generics support added by Christian Hammer with help from Hartmut Benz and John Sichi). Added (Directed)NeighborIndex and MatrixExporter, contributed by Charles Fry. Added BellmanFord, contributed by Guillaume Boulmier of France Telecom. Removed never-used LabeledElement. Renamed package from org._3pq.jgrapht to org.jgrapht. Made various breaking change to interfaces; edge collections are now Sets, not Lists. Added Touchgraph converter, contributed by Carl Anderson
• version 0.6.0 (July-2005) : Upgraded to JDK 1.4, taking advantage of its new linked hash set/map containers to make edge/vertex set order-deterministic. Added support for custom edge lists. Fixed various serialization and Subgraph issues. Added to JGraphModelAdapter support for JGraph's "dangling" edges; its constructors have slightly changed and now forbid null values. Improved interface to DijskstraShortestPath, and added radius support to ClosestFirstIterator. Added new StrongConnectivityInspector algorithm (contributed by Christian Soltenborn) and TopologicalOrderIterator (contributed by Marden Neubert). Deleted deprecated TraverseUtils. Upgraded to JGraph 5.6.1.1.
• version 0.5.3 (June-2004) : Removed Subgraph verification of element's identity to base graph, upgraded to JGraph 4.0, Added the VisioExporter which was contributed by Avner Linder, minor bug fixes and improvements.
• version 0.5.2 (March-2004) : Serialization improvements, fixes to subgraphs and listenable graphs, added support for JGraph->JGraphT change propagation for JGraph adapter (contributed by Erik Postma), upgraded to JGraph 3.1, various bug fixes and improvements.
• version 0.5.1 (November-2003) : Semantics of Graph.clone() has changed, please check the documentation if you're using it. Added Dijkstra's shortest path, vertex cover approximations, new graph generation framework, upgraded to JGraph 3.0, various bug fixes and API improvements.
• version 0.5.0 (14-Aug-2003) : a new connectivity inspector added, edge API refactored to be simpler, an improved ant build, an improved event model, all known bugs were fixed, documentation clarifications, other small improvements. API of 0.5.0 is not 100% backward compatible with 0.4.1 but upgrade is simple and straightforward.
• version 0.4.1 (05-Aug-2003) : A new adapter to JGraph that provides graph visualizations, new depth-first and breadth-first iteration algorithms, various bug fixes and refactoring, moved unit-tests to a separate folder hierarchy and added more unit-tests.
• version 0.4.0 (July-2003) : Initial public release.

Contributors

JGraphT wouldn't be the library it is today without the source contributions and suggestions made by the authors:

• Barak Naveh (project founder)
• John V Sichi (current project administrator)
• Liviu Rau
• Nathan Fiedler
• Michael Behrisch
• Linda Buisman
• Erik Postma
• Mikael Hansen
• Avner Linder
• Marden Neubert
• Christian Soltenborn
• Christian Hammer
• Ewgenij Proschak
• Hartmut Benz
• Charles Fry
• Guillaume Boulmier
• Carl Anderson
• Khanh Vu
• Aaron Harnly
• Dimitrios Michail
• Welson Sun
• Trevor Harmon
• David Black-Schaffer
• Vinayak Borkar
• Andrew Berman
• Lucas Scharenbroich
• Hookahey
• Tim Shearouse
• Holger Brandl
• Ilya Razenshteyn
• Peter Giles
• Andrew Newell
• Tim Engler
• Tom Larkworthy
• Soren Davidsen
• Andrea Pagani
• Tom Conerly
• Michele Mancioppi
• Adrian Marte
• Assaf Mizrachi
• Harshal Vora
• Matt Sarjent
• Robby McKilliam
• Yuriy Nakonechnyy

(if we have missed your name on this list, please email us to get it fixed).

Other people have also helped in different ways: reporting bugs, requesting features, commenting, and by merely asking very good questions. Many thanks to all of you.

Regards,
Barak Naveh
JGraphT Project Creator

John Sichi
JGraphT Project Administrator