Master repository for the JGraphT project

JGraphT

Last update: Dec 30, 2022

Overview

JGraphT

Released: June 14, 2020

Written by Barak Naveh and Contributors

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

GNU Lesser General Public License (LGPL) 2.1 http://www.gnu.org/licenses/lgpl-2.1.html

or the

Eclipse Public License (EPL) http://www.eclipse.org/org/documents/epl-v20.php

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

Comments

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

[x] I read and understood https://github.com/jgrapht/jgrapht/wiki/Become-a-Contributor

[x] I read and understood https://github.com/jgrapht/jgrapht/wiki/How-to-make-your-first-%28code%29-contribution

[x] I added unit tests

[x] I added documentation

[x] I followed the Coding and Style Conventions

[x] I have not modified HISTORY.md or CONTRIBUTORS.md

[x] I ensured that the git commit message is a good one
opened by d-michail 51
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!

[x] I read and understood https://github.com/jgrapht/jgrapht/wiki/Become-a-Contributor

[x] I read and understood https://github.com/jgrapht/jgrapht/wiki/How-to-make-your-first-%28code%29-contribution

[x] I added unit tests

[x] I added documentation

[x] I followed the Coding and Style Conventions

[x] I have not modified HISTORY.md or CONTRIBUTORS.md

[x] I ensured that the git commit message is a good one
opened by d-michail 40
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.

[x] I read and understood https://github.com/jgrapht/jgrapht/wiki/Become-a-Contributor

[x] I read and understood https://github.com/jgrapht/jgrapht/wiki/How-to-make-your-first-%28code%29-contribution

[x] I added unit tests

[x] I added documentation

[x] I followed the Coding and Style Conventions

[x] I have not modified HISTORY.md or CONTRIBUTORS.md

[x] I ensured that the git commit message is a good one
opened by SChudakov 34
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.

[x] I read and understood https://github.com/jgrapht/jgrapht/wiki/Become-a-Contributor

[x] I read and understood https://github.com/jgrapht/jgrapht/wiki/How-to-make-your-first-%28code%29-contribution

[x] I added unit tests

[x] I added documentation

[x] I followed the Coding and Style Conventions

[x] I have not modified HISTORY.md or CONTRIBUTORS.md

[x] I ensured that the git commit message is a good one
opened by d-michail 29
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
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
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
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
Chordality inspector added
Added chordality test. Main features are documented in Javadoc. In my implementation I used following paper:

"CS 762: Graph-theoretic algorithms. Lecture notes of a graduate course. The University of Waterloo. Fall 1999, Winter 2002, Winter 2004". Visit this link.
opened by Toptachamann 23

CapacityScalingMinimumCostFlow using the edge weight of the graph as arc costs instead of the getArcCosts() function of the MinimumCostFlowProblem

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

Issue I was just using the CapacityScalingMinimumCostFlow implementation to compute a minimum cost flow of a graph. Since the problem declaration interfaceMinimumCostFlowProblem supports a getArcCosts() function I assumed that this function is the one being used to calculate the cost of an arc. But as it turns out, the CapacityScalingMinimumCostFlow implementation uses the edge weight of the graph even if such a function is supplied. I think this might be undesirable.

Steps to reproduce (small coding example)

public class SampleCode {
    public static void main(String[] args) {
        Graph<Integer, DefaultWeightedEdge> graph = new DefaultDirectedWeightedGraph<>(DefaultWeightedEdge.class);

        // Create a simple graph 1 ----10----> 2
        graph.addVertex(1);
        graph.addVertex(2);

        DefaultWeightedEdge edge = graph.addEdge(1, 2);
        graph.setEdgeWeight(edge, 10);

        // Create a MinCostMaxFlow problem instance
        MinimumCostFlowProblem<Integer, DefaultWeightedEdge> flowProblem = new MinimumCostFlowProblem.MinimumCostFlowProblemImpl<>(
                graph,
                (Integer v) -> v == 1 ? 1 : -1,   // B-Values (send 1 unit from 1 to 2)
                (DefaultWeightedEdge e) -> 1,     // Arc capacity upper bound
                (DefaultWeightedEdge e) -> 0,     // Arc capacity lower bound
                (DefaultWeightedEdge e) -> 20.    // Arc cost override (not working)
        );

        CapacityScalingMinimumCostFlow<Integer, DefaultWeightedEdge> solver = new CapacityScalingMinimumCostFlow<>();
        MinimumCostFlowAlgorithm.MinimumCostFlow<DefaultWeightedEdge> minCostFlow = solver.getMinimumCostFlow(flowProblem);

        // The Min Cost Flow should have cost 20
        if (Math.abs(minCostFlow.getCost() - 20.0) > 0.000001d) {
            throw new RuntimeException("Expected min cost flow of 20.0 but got " + minCostFlow.getCost());
        }
    }
}

Expected behaviour The CapacityScalingMinimumCostFlow algorithm should use the getArcCosts() function instead of the graph getEdgeWeight() function to obtain arc costs. Not supplying the getArcCost() function still defaults to the edge weight in the default implementation of the interface. So this should not be a breaking change.

Other information I am no JGraphT veteran. I just recently started using this library. So it could very well be that I am completely missing something here. I'm curious about your thoughts.

opened by MarcTM01 0

TransitNodeRoutingSP usage is severely limited

The contraction hierarchies, locality filter and more importantly access vertices are not accessible, thus severely limiting the usage of the algorithm. TransitNodeRoutingPreCmputation class is also not accessible, although the TNRSP test file makes use of it. Any chance, please, of making the above properties public?

opened by handcath 0
chore(deps): update antlr4 to 4.11.1
Bump antlr4 to the latest version

antlr4 mainly driven by antlr4 bump in Quarkus

Quarkus moved antlr4 from 4.9.2 to 4.10.1 and tests are now failing, antlr4 needs to updated to 4.10+ to overcome the trouble with antlr4 4.9.2 vs. 4.10+, for now I have added https://github.com/quarkiverse/quarkus-jgrapht/commit/922cde8435d6b08a566b484a700bdac2cb39d30e workaround
opened by rsvoboda 0

Delta Stepping Shortest Path performance issue

 * JGraphT version: 1.5.2-SNAPSHOT
 * Java version (java -version)/platform:  
      openjdk version "17.0.4.1" 2022-08-12 LTS
      OpenJDK Runtime Environment Zulu17.36+17-CA (build 17.0.4.1+1-LTS)
      OpenJDK 64-Bit Server VM Zulu17.36+17-CA (build 17.0.4.1+1-LTS, mixed mode, sharing)

Issue The performance of the Delta Stepping Shortest Path is worse than Shortest Path.


Benchmark                                                             (edgeDegree)   (k)  (m)  (m0)  (numOfVertices)   (p)  Mode  Cnt     Score     Error  Units
DeltaSteppingShortestPathPerformance.testBellmanFordBarabasiAlbert             N/A   N/A   50  1000            10000   N/A  avgt    8   419.299 ±  20.034  ms/op
DeltaSteppingShortestPathPerformance.testBellmanFordBarabasiAlbert             N/A   N/A  500  1000            10000   N/A  avgt    8  2749.307 ± 223.533  ms/op
DeltaSteppingShortestPathPerformance.testBellmanFordComplete                   N/A   N/A  N/A   N/A             1000   N/A  avgt    8   137.602 ±   7.340  ms/op
DeltaSteppingShortestPathPerformance.testBellmanFordComplete                   N/A   N/A  N/A   N/A             2000   N/A  avgt    8   771.219 ±  12.629  ms/op
DeltaSteppingShortestPathPerformance.testBellmanFordComplete                   N/A   N/A  N/A   N/A             3000   N/A  avgt    8  1609.953 ±  36.519  ms/op
DeltaSteppingShortestPathPerformance.testBellmanFordGnm                         50   N/A  N/A   N/A            10000   N/A  avgt    8   326.287 ±  18.845  ms/op
DeltaSteppingShortestPathPerformance.testBellmanFordGnm                        500   N/A  N/A   N/A            10000   N/A  avgt    8  4004.422 ± 332.298  ms/op
DeltaSteppingShortestPathPerformance.testBellmanFordGnp                        N/A   N/A  N/A   N/A            10000  0.01  avgt    8   232.899 ±  12.116  ms/op
DeltaSteppingShortestPathPerformance.testBellmanFordGnp                        N/A   N/A  N/A   N/A            10000  0.05  avgt    8  1255.225 ±  82.109  ms/op
DeltaSteppingShortestPathPerformance.testBellmanFordWattsStogatz               N/A   100  N/A   N/A            10000  0.05  avgt    8   163.956 ±  22.031  ms/op
DeltaSteppingShortestPathPerformance.testBellmanFordWattsStogatz               N/A   100  N/A   N/A            10000   0.5  avgt    8   234.527 ±  11.475  ms/op
DeltaSteppingShortestPathPerformance.testBellmanFordWattsStogatz               N/A  1000  N/A   N/A            10000  0.05  avgt    8  2464.857 ±  95.188  ms/op
DeltaSteppingShortestPathPerformance.testBellmanFordWattsStogatz               N/A  1000  N/A   N/A            10000   0.5  avgt    8  2952.583 ± 124.745  ms/op
DeltaSteppingShortestPathPerformance.testDeltaSteppingBarabasiAlbert           N/A   N/A   50  1000            10000   N/A  avgt    8    57.409 ±   1.384  ms/op
DeltaSteppingShortestPathPerformance.testDeltaSteppingBarabasiAlbert           N/A   N/A  500  1000            10000   N/A  avgt    8   249.525 ±  35.653  ms/op
DeltaSteppingShortestPathPerformance.testDeltaSteppingComplete                 N/A   N/A  N/A   N/A             1000   N/A  avgt    8    26.905 ±   5.840  ms/op
DeltaSteppingShortestPathPerformance.testDeltaSteppingComplete                 N/A   N/A  N/A   N/A             2000   N/A  avgt    8    93.437 ±   4.513  ms/op
DeltaSteppingShortestPathPerformance.testDeltaSteppingComplete                 N/A   N/A  N/A   N/A             3000   N/A  avgt    8   194.314 ±  13.287  ms/op
DeltaSteppingShortestPathPerformance.testDeltaSteppingGnm                       50   N/A  N/A   N/A            10000   N/A  avgt    8    41.767 ±   2.564  ms/op
DeltaSteppingShortestPathPerformance.testDeltaSteppingGnm                      500   N/A  N/A   N/A            10000   N/A  avgt    8   307.943 ±  21.966  ms/op
DeltaSteppingShortestPathPerformance.testDeltaSteppingGnp                      N/A   N/A  N/A   N/A            10000  0.01  avgt    8    49.881 ±   2.702  ms/op
DeltaSteppingShortestPathPerformance.testDeltaSteppingGnp                      N/A   N/A  N/A   N/A            10000  0.05  avgt    8   141.187 ±  12.015  ms/op
DeltaSteppingShortestPathPerformance.testDeltaSteppingWattsStogatz             N/A   100  N/A   N/A            10000  0.05  avgt    8    95.720 ±   4.174  ms/op
DeltaSteppingShortestPathPerformance.testDeltaSteppingWattsStogatz             N/A   100  N/A   N/A            10000   0.5  avgt    8    47.080 ±   4.513  ms/op
DeltaSteppingShortestPathPerformance.testDeltaSteppingWattsStogatz             N/A  1000  N/A   N/A            10000  0.05  avgt    8   298.225 ±  44.198  ms/op
DeltaSteppingShortestPathPerformance.testDeltaSteppingWattsStogatz             N/A  1000  N/A   N/A            10000   0.5  avgt    8   265.392 ±  16.506  ms/op
DeltaSteppingShortestPathPerformance.testDijkstraBarabasiAlbert                N/A   N/A   50  1000            10000   N/A  avgt    8    96.186 ±   3.137  ms/op
DeltaSteppingShortestPathPerformance.testDijkstraBarabasiAlbert                N/A   N/A  500  1000            10000   N/A  avgt    8   546.831 ±  26.464  ms/op
DeltaSteppingShortestPathPerformance.testDijkstraComplete                      N/A   N/A  N/A   N/A             1000   N/A  avgt    8    32.639 ±   1.302  ms/op
DeltaSteppingShortestPathPerformance.testDijkstraComplete                      N/A   N/A  N/A   N/A             2000   N/A  avgt    8   374.593 ±  63.599  ms/op
DeltaSteppingShortestPathPerformance.testDijkstraComplete                      N/A   N/A  N/A   N/A             3000   N/A  avgt    8   425.900 ±  29.012  ms/op
DeltaSteppingShortestPathPerformance.testDijkstraGnm                            50   N/A  N/A   N/A            10000   N/A  avgt    8    66.214 ±   4.585  ms/op
DeltaSteppingShortestPathPerformance.testDijkstraGnm                           500   N/A  N/A   N/A            10000   N/A  avgt    8   757.004 ± 123.999  ms/op
DeltaSteppingShortestPathPerformance.testDijkstraGnp                           N/A   N/A  N/A   N/A            10000  0.01  avgt    8    59.838 ±   3.582  ms/op
DeltaSteppingShortestPathPerformance.testDijkstraGnp                           N/A   N/A  N/A   N/A            10000  0.05  avgt    8   300.436 ±  11.215  ms/op
DeltaSteppingShortestPathPerformance.testDijkstraWattsStogatz                  N/A   100  N/A   N/A            10000  0.05  avgt    8    40.212 ±   3.675  ms/op
DeltaSteppingShortestPathPerformance.testDijkstraWattsStogatz                  N/A   100  N/A   N/A            10000   0.5  avgt    8    62.146 ±   4.787  ms/op
DeltaSteppingShortestPathPerformance.testDijkstraWattsStogatz                  N/A  1000  N/A   N/A            10000  0.05  avgt    8   507.808 ±  38.985  ms/op
DeltaSteppingShortestPathPerformance.testDijkstraWattsStogatz                  N/A  1000  N/A   N/A            10000   0.5  avgt    8   689.996 ±  86.456  ms/op

Steps to reproduce (small coding example) We derived it by executing DeltaSteppingShortestPathPerformance

Expected behaviour Delta Stepping should be more performant than Dijkstra.

Other information Hardware:

      Model Name:	MacBook Pro
      Model Identifier:	MacBookPro18,1
      Chip:	Apple M1 Pro
      Total Number of Cores:	10 (8 performance and 2 efficiency)
      Memory:	32 GB

opened by conker84 0

Failed to import DOT graph
* JGraphT version: 1.5.2 * Java version (java -version)/platform: 1.11

Hi,

Issue I get a token recognition error when inside the label attribute there is a string containing \n

Steps to reproduce (small coding example)

This is my dot file: strict digraph DiskGraph { nodesep=0.35; subgraph cluster_graph { color="white"; 6578061168802162856 [label="/\\ recordedCallsInHalfOpen = <<>>\n/\\ NumberOfCallsInHalfOpen = 0",style = filled] } }

I was wondering if that is a bug or if is there a workaround for it.

Thank you
opened by AlirezaHakamian 0

DotExporter exports outdated version of the graph

 * JGraphT version:                                'org.jgrapht:jgrapht-io:1.5.1'
 * Java version (java -version)/platform:  java-11-openjdk (linux)

Issue When using Nodes that contain classes, the dotexporter seems to export a cached version of the graph instead of properly evaluating all classes toString. This causes wrong outputs.

Steps to reproduce (small coding example)

import org.jgrapht.graph.DefaultDirectedGraph
import org.jgrapht.graph.DefaultEdge
import org.jgrapht.nio.dot.DOTExporter
import java.io.File


class Node(val wrapper: StringWrap)
class StringWrap(var value: String)

fun main() {
    val graph = DefaultDirectedGraph<Node, DefaultEdge>(DefaultEdge::class.java)
    val node1 = Node(StringWrap("old"))
    graph.addVertex(node1)

    val exporter = DOTExporter<Node, DefaultEdge> { """"${it.wrapper.value}"""" }
    exporter.exportGraph(graph, File("old.dot").bufferedWriter()) // <- commenting out this line will eliviate the bug
    node1.wrapper.value = "new"
    exporter.exportGraph(graph, File("new.dot").bufferedWriter())
}

Than new.dot contains the old data

strict digraph G {
  "old";
}

Expected behaviour

new.dot containing the updated data

strict digraph G {
  "new";
}

Other information The problem is actually caused by the first export call. This somehow caches information inside the exporter. When commenting out the first export call the result is correct.

Also it is importaint that the data is contained inside a class. It seems that it checks if the class reference has changed. changing the updating code to node1.wrapper = new StringWrap("new") will work!.

opened by stheid 0

Master repository for the JGraphT project

Related tags

Overview

JGraphT

Introduction

Release Contents

Getting Started

Using via Maven

Upgrading Versions

Documentation

Dependencies

Online Resources

Your Improvements

Thanks

Comments

Owner

JGraphT

Master Selenium Framework BDD

Pandora - allowing to control different agents (Windows & Linux machine) from server(s) and master

This repository contains the IRPact agent-based modeling framework for innovation diffusion of sustainable product in private households. It has been developed within the SUSIC project at Leipzig University and the Institute for Applied Informatics by the project members.

A java api and command line tool for scanning, reporting and fixing a git repository's InnerSource Readiness based on a supplied specification which defines the files and file contents necessary for a repository to be considered ready for InnerSource contribution.

An assistance platform made using Spring framework that analyses your code, and helps you either to start a devops project, or to turn an existing project into a devops project using open source software (Git, Docker, Jenkins..)

JGit project repository (jgit)

The public release repository for SUSTech SQL (CS307) course project 2.

Repository with Backend code for InnoTutor project. It is written on Java/Spring.

This is the primary repository for the source code of the OpenJML project.

This repository contains the code for the Runescape private server project, and this repo is soley maintained by @Avanae and @ThePolyphia and @Xeveral

This repository is totally dedicated to Hacktoberfest 2021, feel free to add your project.

This repository contains my first project of Suven Internship.

JVM version of Pact. Enables consumer driven contract testing, providing a mock service and DSL for the consumer project, and interaction playback and verification for the service provider project.

This open source project allows you to easily integrate Camunda's External Task Clients into Micronaut projects: simply add a dependency in your Micronaut project

The project aim at easier to start a spring boot/cloud project.

Zero is a core test automation project that can be used as a basis for any kind of test automation project (API, Browser, Mobile)

This project is an Android Studio plugin version of BlackObfuscator, it supports obfuscating code automatically. More information about this project are in BlackObfuscator.

This project provides an advanced baseline to help you kick start a Spring project.