Master repository for the JGraphT project

Overview

Build Status Maven Central Snapshot License License Language

JGraphT

Released: June 14, 2020

Written by Barak Naveh and Contributors

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

Please address all contributions, suggestions, and inquiries to the user mailing list

Introduction

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

JGraphT may be used under the terms of either the

or the

As a recipient of JGraphT, you may choose which license to receive the code under.

For detailed information on the dual license approach, see https://github.com/jgrapht/jgrapht/wiki/Relicensing.

A copy of the EPL license and the LPGL 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.

SPDX-License-Identifier: LGPL-2.1-or-later OR EPL-2.0

Release Contents

The files below make up the table of contents for a release distribution archive (produced by mvn package):

  • README.md this file

  • CONTRIBUTORS.md list of contributors

  • HISTORY.md changelog

  • license-EPL.txt Eclipse Public License 2.0

  • license-LGPL.txt GNU Lesser General Public License 2.1

  • javadoc/ Javadoc documentation

  • lib/ JGraphT libraries and dependencies:

    • jgrapht-core-x.y.z.jar core library
    • jgrapht-demo-x.y.z.jar demo classes
    • jgrapht-opt-x.y.z.jar optimized graph implementations
    • jgrapht-ext-x.y.z.jar extensions
    • jgrapht-io-x.y.z.jar Importers/Exporters for various graph formats
    • jgrapht-guava-x.y.z.jar Adapter classes for the Guava library
    • jgrapht-unimi-dsi-x.y.z.jar Webgraph adapter and succinct graph implementations
    • jgraphx-a.b.c.jar JGraphX dependency library
    • jheaps-x.y.jar JHeaps library
    • antlr4-runtime-x.y.jar ANTLR parser runtime
    • commons-lang3-x.y.z.jar Apache Commons Lang library
    • commons-text-x.y.jar Apache Commons Text library
    • fastutil-x.y.z.jar Fastutil library
    • guava-x.y-jre.jar Guava library
    • jsap-x.y.jar Jsap library
    • logback-classic-x.y.z.jar Logger
    • logback-core-x.y.z.jar Logger
    • slf4j-api-x.y.z.jar Logger api
    • sux4j-x.y.z.jar Sux4j library
    • webgraph-x.y.z.jar Webgraph library
    • webgraph-big-z.y.z.jar Webgraph big library
  • source/ complete source tree used to build this release

Getting Started

The JGraphT wiki provides various helpful pages for new users, including a How to use JGraphT in your projects page. 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.

To run the graph visualization demo from the downloaded release, try executing this command in the lib directory:

java -jar jgrapht-demo-x.y.z.jar

More information can be found on the user pages of our wiki. Finally, all classes come with corresponding test classes. These test classes contain many examples.

To help us understand how you use JGraphT, and which features are important to you, tell us how you are using JGraphT, and cite the usage of JGraphT in your book, paper, website, or technical report.

Using via Maven

Starting from 0.9.0, every JGraphT release is published to the Maven Central Repository. You can add a dependency from your project as follows:

<groupId>org.jgrapht</groupId>
<artifactId>jgrapht-core</artifactId>
<version>1.5.0</version>

We have also started auto-publishing SNAPSHOT builds for every successful commit to master. To use the bleeding edge:

<groupId>org.jgrapht</groupId>
<artifactId>jgrapht-core</artifactId>
<version>1.5.1-SNAPSHOT</version>

and make sure the snapshot repository is enabled:

<repositories>
  <repository>
    <id>maven-snapshots</id>
    <url>http://oss.sonatype.org/content/repositories/snapshots</url>
    <layout>default</layout>
    <releases>
      <enabled>false</enabled>
    </releases>
    <snapshots>
      <enabled>true</enabled>
    </snapshots>
  </repository>
</repositories>

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 the distribution. The latest version of these files is also available on-line.

Dependencies

  • JGraphT requires JDK 11 or later to build starting with version 1.5.0.
  • JHeaps is a library with priority queues. JHeaps is licensed under the terms of the Apache License, Version 2.0.
  • JUnit is a unit testing framework. You need JUnit only if you want to run the unit tests. JUnit is licensed under the terms of the IBM Common Public License. The JUnit tests included with JGraphT have been created using JUnit 4.
  • XMLUnit extends JUnit with XML capabilities. You need XMLUnit only if you want to run the unit tests. XMLUnit is licensed under the terms of the BSD License.
  • JGraphX is a graph visualizations and editing component (the successor to the older JGraph library). You need JGraphX only if you want to use the JGraphXAdapter to visualize the JGraphT graph interactively via JGraphX. JGraphX is licensed under the terms of the BSD license.
  • ANTLR is a parser generator. It is used for reading text files containing graph representations, and is only required by the jgrapht-io module. ANTLR v4 is licensed under the terms of the BSD license.
  • Guava is Google's core libraries for Java. You need Guava only if you are already using Guava's graph data-structures and wish to use our adapter classes in order to execute JGraphT's algorithms. Only required by the jgrapht-guava module.
  • Apache Commons Proper is an Apache project containing reusable Java components. The packages commons-text and commons-lang3. which provide additional utilities for String manipulation are only required by the jgrapht-io module. The package commons-math is only required by the jgrapht-unimi-dsi module.
  • fastutil provides a collection of type-specific maps, sets, lists and queues with a small memory footprint and fast access and insertion. Fastutil is only required by the jgrapht-opt module.
  • webgraph provides a framework for graph compression enabling management of very large graphs. Webgraph is only required by the jgrapht-unimi-dsi module.
  • sux4j provides implementations of basic succinct data structures. Sux4j is only required by the jgrapht-unimi-dsi module.
  • jsap provides a simple argument parser. Jsap is only required by the jgrapht-unimi-dsi module.

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. For support, refer to our support page

Source code is hosted on github. You can send contributions as pull requests there.

Your Improvements

If you add improvements to JGraphT please send them to us as pull requests on github. 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.

Thanks

With regards from

Barak Naveh, JGraphT Project Creator

John Sichi, JGraphT Project Administrator

Joris Kinable, JGraphtT Project Reviewer/Committer and Release Manager

Dimitrios Michail, JGraphT Project Reviewer/Committer

Issues
  • Kolmogorov's Blossom V implementation

    Kolmogorov's Blossom V implementation

    The implementation of the core features of the Kolmogorov's Blossom V algorithm. The documentation covers features essential for the code review (will be extended further if needed). Full documentation is in the todo list.


    TODO list:

    • [x] Numeric stability (have ideas how to fix, but requires careful analysis)
    • [x] Correct handling of the cases when the perfect matching doesn't exist at all
    • [x] Write performance tests
    • [x] Full documentation about the algorithms itself
    • [x] Code optimizations
    • [x] Measure code coverage
    opened by Toptachamann 70
  • JDK 9 Modularization

    JDK 9 Modularization

    I've opened this ticket to try to keep a running list of the tasks needed to get to full JDK 9 modularization. This continues the work started in https://github.com/jgrapht/jgrapht/pull/458.

    • [x] Update plugins to latest versions
    • [x] Update JMH to latest version to correct @Generated annotation issues
    • [x] Get Antlr4 to publish a module name (https://github.com/antlr/antlr4/pull/2223)
      • [x] Wait for new release
    • [x] Fix failing unit tests
      • [x] The GraphXML exporter was asking for indentation but apparently never actually got it. The tests are written to expect no indentation. On JDK 9, the exporter now actually gets indentation in the resulting XML, so the tests must be updated so that the resulting XML texts match.
    • [x] Write module descriptors (almost complete, just need the last couple of module names for jgraphx and ANTLR)
    • [x] Get jgraphx to publish a module name (https://github.com/jgraph/jgraphx/pull/93)
      • [x] Wait for new release
    • [x] Get jgraph to publish a module name (https://github.com/jgraph/legacy-jgraph5) (cancelled, removing the dependency instead)

    Work is taking place here: https://github.com/io7m/jgrapht/tree/jdk9

    enhancement 
    opened by io7m 53
  • Webgraph adapter

    Webgraph adapter

    This is a pull-request containing work done by @vigna on adapter classes for WebGraph. Together with our recent changes on the Graph interface, it allows several JGraphT algorithms (with possibly some modifications) to be executed on very large graphs.


    opened by d-michail 51
  • Modules support

    Modules support

    A first attempt in adding modules. Two main problems:

    • We have some test-jar dependencies, which complicate things considerably. I solved this by duplicating the two test utility classes. If someone has more time to invest on this, please fix this.
    • The bundle package, complicates things, I had to also add a module there, but it is currently empty which means that it might not work correctly.

    I would be in favor of completely removing the uberjar, no point keeping it together with modules.

    @io7m would be great to get feedback from you on this!


    opened by d-michail 40
  • Delta stepping

    Delta stepping

    Implemented delta-stepping algorithm discussed in #663

    [1] U. Meyer, P. Sanders, Δ-stepping: a parallelizable shortest path algorithm, Journal of Algorithms, Volume 49, Issue 1, 2003, Pages 114-152, ISSN 0196-6774, https://doi.org/10.1016/S0196-6774(03)00076-2.


    opened by SChudakov 34
  • Sparse graphs, importers and improved algorithms

    Sparse graphs, importers and improved algorithms

    This is a rather large PR with several performance related improvements. The code is highly tested.

    Algorithmic Changes:

    • Improved performance of PageRank by indexing the graph using integer vertices and using arrays for the computation.
    • Replaced Edmonds Maximum Cardinality Matching with the LEDA book implementation, which is performing much better.
    • Added a custom Dijkstra implementation for graphs with integer vertices, which stores distances and predecessors into arrays (either directly or by mapping to 0..n-1 using a closed addressing hash table). This also improves the performance significantly.

    Graph representation changes:

    • Created sparse package in jgrapht-opt which contains graph implementations using the Compressed-Sparse-Rows (CSR) format. This is classic representation for sparse matrices. Two implementations are provided:
      • Storing the incidence matrix (rows are vertices and columns are edges) and its transpose using CSR.
      • The representation used by igraph library which stores the edgelist, two indices of the edge list (one sorted by source,target and the other by target, source) and two prefix sums of the vertices degrees.
      • Both representations assume vertices and edges are numbered from 0 to n-1 and 0 to m-1.
      • These representations are static but much smaller and much faster than our default backend, thus making them useful in write-once read-many scenarios.

    Importer changes:

    • The graphs in the sparse package are immutable and can be loaded using edge lists from the constructor. For this reason, we also created the notion of an edge list importer which reads a graph from a file and returns an edge list which is simply a list of tuples or a list of triples in case of weighted graphs.
    • Added implementations of edge list importers for DIMACS and GraphML.

    opened by d-michail 29
  • The Berge Graph Checker for the Graph class

    The Berge Graph Checker for the Graph class

    Sorry, it took me so long. But now the BergeGraphChecker should be compliant.

    I wasn't sure, whether to add a new interface for the Checker. Please, let me know and I will add it immediately.

    opened by PhilippKaesgen 27
  • Support hashCode() and equals() methods for graphs

    Support hashCode() and equals() methods for graphs

    Hi All!

    I've just implemented support of hashCode() and equals() methods for AbstractGraph. I've also created two simple unit tests for implemented methods (see EqualsTest.java and HashCodeTest.java). The main idea is to use paring function for edges in hash code computation.

    I hope you'll find my contribution useful and accept it.

    opened by vkostyukov 27
  • Guava adapter

    Guava adapter

    A Guava adapter module which allows users to use all algorithms of the JGraphT library using the Guava 'Network` implementations.

    Guava contains 3 graph interfaces (a) Graph, (b) ValueGraph, and (c) Network. The Network class is the more general one and corresponds almost 1-to-1 with our Graph interface.

    Kept on-purpose separate from the ext module since Guava is somewhat known for its incompatibilities between versions.

    opened by d-michail 27
  • FastLookupDirectedSpecifics does not use edgeSetFactory consistently, and blows memory

    FastLookupDirectedSpecifics does not use edgeSetFactory consistently, and blows memory

    ArrayUnenforcedSetEdgeSetFactory contains an optimization forcing the default size of the ArrayUnenforcedSet to be 1, or 64 bytes.

    https://github.com/jgrapht/jgrapht/blob/master/jgrapht-core/src/main/java/org/jgrapht/graph/specifics/FastLookupDirectedSpecifics.java#L131 does not use the factory or replicate the optimization, but creates a new ArrayUnenforcedSet with the default ArrayList size (10 in JDK8), which takes 136 bytes.

    This more than doubles the memory usage of jgrapht on graphs with low edge cardinality, and is currently blowing out my RAM (I only have 144Gb).

    The Undirected version presumably contains a similar bug, but I'm lazy and all my graphs are directed, so I haven't checked.

    Numbers above are from visualvm's memory profiler, and me figuring out why I have so many nulls in memory.

    bug 
    opened by shevek 25
  • TSPLIbImporter support row-tours and fix distance function for EDGE_WEIGHT_TYPE GEO

    TSPLIbImporter support row-tours and fix distance function for EDGE_WEIGHT_TYPE GEO

    This PR provides a fix for issue #1064 and adds supports for TSPLIB files that contain a tour whose node list is a row. Until know only tours with a node list as column were supported. The latter is one task of the umbrella issue #1067.

    Additionally the corresponding tests are adjusted and extended.


    opened by HannesWell 0
  • Checkstyle: enforce TypeParameter-name conventions

    Checkstyle: enforce TypeParameter-name conventions

    This fourth PR regarding issue #1052 adds the TypeParameterName rules to jgrapht's checkstyle rule-set and fixes the only violation in AbstractGraphIterator.

    Besides that the class type parameters of the package private nested static classes are cleaned up.


    opened by HannesWell 0
  • Minor changes for predictable ordering

    Minor changes for predictable ordering

    opened by d-michail 0
  • JGraphT in native mode - GraalVM / Mandrel

    JGraphT in native mode - GraalVM / Mandrel

    Hi, I have created Quarkus JGraphT extension which handles native mode support for this library. Platform native binaries can be created using GraalVM or Mandrel.

    Details about the extension: https://github.com/quarkiverse/quarkus-jgrapht Announce to quarkus-dev list: https://groups.google.com/g/quarkus-dev/c/auIxVNHt9w0 Feel free to take a look and experiment with it, integration-tests module is a good starting point.

    I would like to mention this extension in the readme of this repository. Before submitting PR I want to discuss the right place and form.

    opened by rsvoboda 3
  • .editorconfig file says to remove trailing whitespace

    .editorconfig file says to remove trailing whitespace

    Your .editorconfig file says to trim trailing whitespace:

    trim_trailing_whitespace = true
    

    Some IDEs (like IntelliJ) will honor that and introduce whitespace changes to your files where you have an extra space after an empty line in javadoc (you have asterisk plus space instead of only asterisk).

    My first PR introduced those whitespace changes and you asked me to fix them. I see other PRs that also introduce changed lines where they trimmed the whitespace, for example: https://github.com/jgrapht/jgrapht/pull/1021/files

    opened by tomnelson 6
  • Delta stepping with custom vertices fails

    Delta stepping with custom vertices fails

     * JGraphT version: 1.5.1
     * Java version (java -version)/platform:  11
    

    Issue

    I was trying to execute DeltaSteppingShortestPath with a custom vertex which does not implement comparable. I am getting a CustomVertex cannot be cast to java.lang.Comparable. The use of ConcurrentSkipListSet in the buckets forces the user to use comparable vertices.

    My first guess is that this can be avoided. If not, we should at least allow the user to provide an external comparator.

    Steps to reproduce (small coding example)

    Add the following code in DeltaSteppingShortestPathTest:

        public class MyVertex  { 
            public MyVertex() { 
            }
        }
        
        @Test
        public void testCustomVertex()
        {
            Graph<MyVertex, DefaultEdge> graph =
                new DirectedWeightedPseudograph<>(DefaultEdge.class);
            
            MyVertex v0 = new MyVertex();
            MyVertex v1 = new MyVertex();
            graph.addVertex(v0);
            graph.addVertex(v1);
            graph.addEdge(v0, v1);
    
            new DeltaSteppingShortestPath<>(graph, executor).getPaths(v0);
        }
    

    Expected behaviour

    No exception.

    Other information

    opened by d-michail 1
  • AISS L7 G02 - University work

    AISS L7 G02 - University work

    This is a very small group contribution made to this project based on minor bugs found by using SonarCloud. The changes in the pom.xml file were exclusive for the project to work on the forementioned website.

    We do not intend to get accepted unless the bugs fixed (listed in all commits) are actually valuable.

    opened by gonmarfer2 0
  • JSONImporter does not support files with 'links' key instead of 'edges' key

    JSONImporter does not support files with 'links' key instead of 'edges' key

     * JGraphT version:
     * Java version (java -version)/platform:  
    

    Issue JSONImporter will not read edges for json file (i.e. D3 format) with edges called 'links' instead of 'edges'

    Steps to reproduce (small coding example)

    Expected behaviour

    Other information

    opened by tomnelson 0
  • DOTImporter.setVertexWithAttributesFactory gets called with an empty string

    DOTImporter.setVertexWithAttributesFactory gets called with an empty string

     * JGraphT version: 1.5.1
     * Java version (java -version)/platform:  11
    

    I apologize if this issue has been raised before but I didn't find anything similar from Google search or by searching the issues in this repo.

    Issue Given the following graph:

    strict digraph G {
      root="commons/master";
      "auth/master" [ comments="{\"ancestors\":[\"commons/master\",\"subscription/master\"]}" ];
      "commons/master" [ comments="{\"ancestors\":[]}" ];
      "subscription/master" [ comments="{\"ancestors\":[\"commons/master\"]}" ];
      "gateway/master" [ comments="{\"ancestors\":[\"auth/master\",\"commons/master\",\"subscription/master\"]}" ];
      "datetime/master" [ comments="{\"ancestors\":[\"commons/master\",\"subscription/master\"]}" ];
      "browse/master" [ comments="{\"ancestors\":[\"commons/master\"]}" ];
      "subscription/master" -> "auth/master";
      "commons/master" -> "subscription/master";
      "auth/master" -> "gateway/master";
      "subscription/master" -> "datetime/master";
      "commons/master" -> "browse/master";
    }
    

    DOTImporter.setVertexWithAttributesFactory gets called with an empty string for vertex, and no attributes. There is no way for the client to create a vertex from an empty string and returning null causes an NPE.

    Expected behaviour DOTImporter.setVertexWithAttributesFactory should not get called with an empty string for vertex.

    Other information FWIW, client code is in Kotlin.

    opened by asarkar 1
A scientific charting library focused on performance optimised real-time data visualisation at 25 Hz update rates for data sets with a few 10 thousand up to 5 million data points.

ChartFx ChartFx is a scientific charting library developed at GSI for FAIR with focus on performance optimised real-time data visualisation at 25 Hz u

GSI CS-CO/ACO 225 Mar 10, 2021
The Mines Java Toolkit

The Mines Java Toolkit The Mines Java Toolkit (Mines JTK) is a set of Java packages and native (non-Java) software libraries for science and engineeri

Mines Java Toolkit 40 Oct 8, 2020
The Next Generation Logic Library

Introduction LogicNG is a Java Library for creating, manipulating and solving Boolean and Pseudo-Boolean formulas. It includes 100% Java implementatio

LogicNG 66 Feb 26, 2021
XChart is a light-weight Java library for plotting data.

XChart XChart is a light weight Java library for plotting data. Description XChart is a light-weight and convenient library for plotting data designed

Knowm 1.1k Mar 9, 2021
Java dataframe and visualization library

Tablesaw Overview Tablesaw is Java for data science. It includes a dataframe and a visualization library, as well as utilities for loading, transformi

Tablesaw 2.5k Mar 13, 2021
A 3D chart library for Java applications (JavaFX, Swing or server-side).

Orson Charts (C)opyright 2013-2020, by Object Refinery Limited. All rights reserved. Version 2.0, 15 March 2020. Overview Orson Charts is a 3D chart l

David Gilbert 74 Mar 1, 2021
modular and modern graph-theory algorithms framework in Java

Erdos is a very light, modular and super easy to use modern Graph theoretic algorithms framework for Java. It contains graph algorithms that you can a

Erdos 104 Feb 16, 2021
The foundational library of the Morpheus data science framework

Introduction The Morpheus library is designed to facilitate the development of high performance analytical software involving large datasets for both

Zavtech Systems 202 Mar 2, 2021
JGraphX - Library for visualizing (mainly Swing) and interacting with node-edge graphs.

JGraphX This project is end of life. We don't properly support Maven or publish to Maven Central. If that's an issue, use https://github.com/vlsi/jgra

JGraph 613 Mar 8, 2021