jgrapht / jgrapht

Master repository for the JGraphT project

JGraphT

Released: May 2, 2023

Written by Barak Naveh and Contributors

(C) Copyright 2003-2023, 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

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

or the

• Eclipse Public License (EPL) https://www.eclipse.org/legal/epl-2.0/

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/Users:-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
  • apfloat-x.x.x.jar Apfloat 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.2</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.3-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 Eclipse Public License - v 2.0. The JUnit tests included with JGraphT have been created using JUnit 5.
• 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.
• apfloat provides support for high performance arbitrary precision arithmetic. Apfloat is licensed under the terms of the MIT license.

Online Resources

The JGraphT website is at https://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

jgrapht's Issues

Compute the condensation of a graph

Wikipedia defines the condensation of a graph G as follows:

If each strongly connected component is contracted to a single vertex, the resulting graph is a directed acyclic graph, the condensation of G.

Method StrongConnectivityInspector.stronglyConnectedSets already computes the set of strongly connected components of a given graph. But, it doesn't provide an efficient way to find out the relationship between the strongly connected components. I suggest that jgrapht provides a way to get the condensation graph. For example, a method called StrongConnectivityInspector.stronglyConnectedComponents could return an object of type like DirectedGraph<DirectedGraph<V, E>, DefaultEdge>. Such a return value makes each component and the relationship between the components accessible to the user.

toString() for StrongConnectivityInspector.VertexData

I think it will be useful to have a toString() here especially while debugging cycles in large graphs.

Why would a graph of 16000 nodes take half an hour to be created in JGraphT?

I am asking this question because my program takes half an hour to create a graph of 16000 nodes (3x 16000 to get edge no). I don't know why it takes so long. I use my own Vertex and Edge class. So I figured perhaps I can precompute the graph (for half an hour!) and then import a ready populated version for visualizationa and further processing. I override both the equal and teh hashcode method in my vertex class, but even if I don't do that it takes the same amount of time.

Could I perhaps import a pre-made graph so that I can use it in instantly in a different program without having to wait for it to be created for half an hour.

publish to oss maven repo

Hi JGraphT.

Is it possible you can publish your binaries to Maven Central ? (Sonatype's OSS Nexus)

Thanks!

OutOfMemoryError in TransitiveClosure.closeSimpleDirectedGraph()

I have a graph with 100k edges, and I get a OutOfMemoryError
when executing TransitiveClosure.closeSimpleDirectedGraph()

is there a solution for this?

Bundle ClassPath causes path warnings when using -Xlint:path

± lein uberjar
Compiling 2 source files to /home/mal/code/storm-app/target/classes
warning: [path] bad path element "/home/mal/.m2/repository/storm/jgrapht/0.8.3/lib/jgraph.jar": no such file or directory
1 warning
Created /home/mal/code/storm-app/target/test-v0.0.1.jar
Created /home/mal/code/storm-app/target/test-v0.0.1-standalone.jar

± ll /home/mal/.m2/repository/storm/jgrapht/0.8.3/
total 256
-rw-rw-r-- 1 mal mal 245255 Feb 13 20:55 jgrapht-0.8.3.jar
-rw-rw-r-- 1 mal mal     40 Feb 13 20:55 jgrapht-0.8.3.jar.sha1
-rw-rw-r-- 1 mal mal   1247 Feb 13 20:55 jgrapht-0.8.3.pom
-rw-rw-r-- 1 mal mal     40 Feb 13 20:55 jgrapht-0.8.3.pom.sha1
-rw-rw-r-- 1 mal mal    180 Feb 13 20:55 _maven.repositories

I'm guessing this problem is a result of the way jar files are stored in .m2 perhaps. I also realise that this example is using storm/jgrapht/0.8.3 however the same issue is suffered by:

Retrieving org/jgrapht/jgrapht-core/0.9.0/jgrapht-core-0.9.0.pom from central

AbstractGraph.removeAllEdges with nonexistent vertex

The documentation for the removeAllEdges(V, V) method in Graph specifies that it returns null if any of the vertices aren't in the graph. But the implementation in AbstractGraph throws a NullPointerException instead.

Example code snippet:

Graph<String, String> graph = new SimpleGraph<String, String>(String.class);
System.out.println(graph.removeAllEdges("Foo", "Bar")));

This should print "null", but instead throws a NullPointerException.

lowest common ancestors?

Thanks for the great library. It's a bit of a long-shot but I was looking for a lowest common ancestors implementation. Is there one that I've missed, or any prospects of one being added?

Bug in TopologicalOrderIterator

The TopologicalOrderIterator or one of its superclasses appears to be incorrect in version 0.8.3.

The following script throws a NoSuchElementException in the fourth iteration of the while loop.

// create a simple DAG with an edge from each source node to the target node
DefaultDirectedGraph<String, DefaultEdge> dag = new DefaultDirectedGraph<String, DefaultEdge>(DefaultEdge.class);

String source1 = "source1";
String source2 = "source2";
String target = "target";

dag.addVertex(source1);
dag.addVertex(source2);
dag.addVertex(target);

dag.addEdge(source1, target);
dag.addEdge(source2, target);

// traverse the DAG in topological order
TopologicalOrderIterator<String, DefaultEdge> iterator = new TopologicalOrderIterator<String, DefaultEdge>(dag);
iterator.setCrossComponentTraversal(true);

// bug: iterator.hasNext() returns true 4 times, even though the DAG has only 3 nodes
while (iterator.hasNext()) {
    // the 4th iterator.next() call throws the exception
    iterator.next();
}

ListenableDirectedWeightedGraph doesn't seem to set edge weights

Hello,

method setEdgeWeight() of class ListenableDirectedWeightedGraph doesn't seem to work.
After a value is assigned to an edge, the getEdgeWeight() method still returns 1.0

Changing the ListenableDirectedWeightedGraph to SimpleDirectedWeightedGraph is kinda workaround, edge weights are correctly set, but I lose the listenable feature.

Is there a method to update the JGraph manually?

CSV import/export

It would be useful to have automated way to import/export graphs as adjacency list in CSV format. Class could be added to org.jgrapht.ext package.

DefaultDirectedGraph: problems with modification of an object inside a graph.

I have the following problem.

Let's say I have written the following class:

public class MyObj {

public boolean some_attr;

...

// IMPORTANT: equals() and hashCode() are redefined to take into account the value of some_attr. Such that equality can't hold if two objects have different some_attr values.

}

When I create a graph with instances of MyObj and change the status of the objects in the graph (i.e java my_obj_instance.some_attr = true;) the graph seems to lose the object, as it is no longer contained in java graph.vertexSet().

I was able to reproduce the bug with this piece of code:

@Test
public void test2() {

DirectedGraph<MyObj, DefaultEdge> graph = new DefaultDirectedGraph<MyObj, DefaultEdge>(DefaultEdge.class); 

MyObj node1 = new MyObj();
graph.addVertex(node1);
node1.some_attr = true;
assertTrue(graph.vertexSet().contains(node1));
// The previous line makes the test fail.
}

It seems reasonable that, when storing reference values, changes in those objects would not affect whether or not the object belongs to the graph.

I hope I made myself clear.

Thanks in advance!

addEdge method stores a second instance of a vertex

I have experienced an issue that took me a while to figure out what was going on. I confess that it was caused by my code, but possibly you guys may consider that it could be handled internally by JGraphT.

Given:

obj1
obj2
obj3

obj2.equals(obj3) => true
obj2 == obj3 => false

If I add the first two to a DirectedAcyclicGraph:

graph.addVertex(obj1)
graph.addVertex(obj2)

And create an edge between obj1 and obj3 (which is not the same reference to the object in the graph, but is equal):

graph.addEdge(obj1, obj3)

When I want to find obj2...

• by getting the elements in the graph calling graph.vertexSet() or traversing the graph using an iterator (TopologicalOrderIterator) ; and
• by getting the edges of obj1:

Set<DefaultEdge> edges = graph.outgoingEdgesOf(obj1)
[for...]
graph.getEdgeTarget(edge)

I get two different instances (obj2 and obj3), as the graph stores the object passed in to the addEdge method in a secondary data structure (it only ensures that the informed object is in the graph, but does not create the edge using the existing instance).

Is this behaviour something expected in JGraphT or something that could be avoided if the edge was created using the objects stored in the graph, not the ones passed in the method addEdge?

Thanks,

Marcelo

Create downloads

Today I tried creating a script to download jgrapht from sourceforge via wget and failed... It always downloaded the HTML page instead of the redirect.

Would you be willing to create/upload the appropriate versions to github. (Click on Downloads > Upload a new file)?

Merge Graphs

Hi,

I had a problem of merging 2 acyclic graphs such that there are no duplicates and also the merged graph needs to retain the acyclic nature. I think the library has all the pieces for this, just that they are not centralized. If you find this issue valid, I can add a general merge utility API.

Unable to setup jgrapht with gradle

Hi,

I'm new to both jgrapht and gradle so it is entirely possible that I'm missing something that is absolutely trivial.

I have added this to my build.gradle
compile 'org.jgrapht:jgrapht:0.9.0'

After this I do a gradle build and this is my gradle cache, it seems that it is unable to download the jar for jgrapht.
nikhil ~/.g/c/m/files-2.1> find . | grep '.jar$' ./junit/junit/4.11/28e0ad201304e4a4abf999ca0570b7cffc352c3c/junit-4.11-sources.jar ./junit/junit/4.11/4e031bb61df09069aeb2bffb4019e7a5034a4ee0/junit-4.11.jar ./org.hamcrest/hamcrest-core/1.3/1dc37250fbc78e23a65a67fbbaf71d2e9cbc3c0b/hamcrest-core-1.3-sources.jar ./org.hamcrest/hamcrest-core/1.3/42a25dc3219429f0e5d060061f71acb49bf010a0/hamcrest-core-1.3.jar ./org.slf4j/slf4j-api/1.7.5/654135274d4c27132ea208a4ec07f344bdb83bcb/slf4j-api-1.7.5-sources.jar ./org.slf4j/slf4j-api/1.7.5/6b262da268f8ad9eff941b25503a9198f0a0ac93/slf4j-api-1.7.5.jar

But I can see that the pom has been downloaded
nikhil ~/.g/c/m/files-2.1> find . | grep '.pom$' ./junit/junit/4.11/cddf7490ffe839978cf5d6c944c01f2a8cb70a49/junit-4.11.pom ./org.hamcrest/hamcrest-core/1.3/872e413497b906e7c9fa85ccc96046c5d1ef7ece/hamcrest-core-1.3.pom ./org.hamcrest/hamcrest-parent/1.3/80391bd32bfa4837a15215d5e9f07c60555c379a/hamcrest-parent-1.3.pom ./org.javabits.jgrapht/jgrapht/0.9.1/807e3b9202e811eb85411d4f23a36d1d9f33ed6d/jgrapht-0.9.1.pom ./org.jgrapht/jgrapht/0.9.0/8ce3cbdd6ebcfecc6d1dde4c23f16605439a9615/jgrapht-0.9.0.pom

I only have maven central in my sources. Is jgrapht not present there?
If not is there some other source I could add to my build.gradle to get this to work. I don't want to be downloading jars and adding them to the classpath all the time.

Working with android

I want to transverse node on android phone. I want to know that does this api works with android or not

Bug in Floyd Warshall Implementation

The implementation of the diameter in the Floyd Warshall shortest path algorithm appears to be incorrect:
http://jgrapht.org/javadoc/org/jgrapht/alg/FloydWarshallShortestPaths.html

The following simple script returns diameter 0 for a graph consisting of only one edge (instead of 1):

DirectedGraph<String, DefaultEdge> graph = new DefaultDirectedGraph<String, DefaultEdge>(DefaultEdge.class);
String a = "a", b = "b", c = "c";
graph.addVertex(a);
graph.addVertex(b);
graph.addEdge(a, b);
    // graph.addVertex(c);   // comment out those two lines to get diameter 2
    // graph.addEdge(b, c);
FloydWarshallShortestPaths<String, DefaultEdge> fw = new FloydWarshallShortestPaths<String, DefaultEdge>(graph);
System.out.println(fw.getDiameter());

Adding just one edge by commenting out two lines leads to a diameter of 2. (The shortest path cannot increase by 2 when only adding one edge.)

Strange results with HamiltonianCycle.getApproximateOptimalForCompleteGraph

I am currently creating a random complete graph and then calculating the HamiltonianCycle on it. I placed the points of the graph all on a circle around the center and I am rendering it with my own Google maps renderer. the resulting HamiltonianCycle looks like in the image:

:
I never get a normal connected closed circle when I run my test, it looks always something like in the photo.

Here is the code I use:

public class DefaultWeightedGeoEdge extends DefaultWeightedEdge {
    @Override
    protected double getWeight() {
        GroupPoi s = (GroupPoi) getSource();
        GroupPoi t = (GroupPoi) getTarget();
        return s.getLocation().getDistanceTo(t.getLocation());
    }
}

public void testDefaultTsp() {
    VertexFactory<GroupPoi> vertexFactory = new VertexFactory<GroupPoi>() {
        int c = 1;

        @Override
        public GroupPoi createVertex() {
            return new GroupPoi("poi " + c++,
                    GeoLocation.createRandomLocation(new GeoLocation(0, 0),
                            900, 1000));
        }
    };
    EdgeFactory<GroupPoi, DefaultWeightedGeoEdge> edgeFactory = new EdgeFactory<GroupPoi, DefaultWeightedGeoEdge>() {

        @Override
        public DefaultWeightedGeoEdge createEdge(GroupPoi sourceVertex,
                GroupPoi targetVertex) {
            return new DefaultWeightedGeoEdge();
        }
    };
    final SimpleWeightedGraph<GroupPoi, DefaultWeightedGeoEdge> targetGraph = new SimpleWeightedGraph<>(
            edgeFactory);
    Map<String, GroupPoi> r = new HashMap<String, GroupPoi>();
    CompleteGraphGenerator<GroupPoi, DefaultWeightedGeoEdge> generator = new CompleteGraphGenerator<>(
            100);
    generator.generateGraph(targetGraph, vertexFactory, r);

    new GoogleMap(new MapEventListener() {

        @Override
        public void onMapLoaded(MapController map) {
            BreadthFirstIterator<GroupPoi, DefaultWeightedGeoEdge> i = new BreadthFirstIterator<>(
                    targetGraph);
            while (i.hasNext()) {
                GroupPoi groupPoi = i.next();
                map.drawGeoElement(groupPoi);
            }
            List<GroupPoi> tspTour = HamiltonianCycle
                    .getApproximateOptimalForCompleteGraph(targetGraph);
            map.setCenterTo(tspTour.get(0).getLocation());

            List<GeoLocation> lineForTspTour = new ArrayList<>();
            for (GroupPoi groupPoi : tspTour) {
                lineForTspTour.add(groupPoi.getLocation());
            }
            map.drawPolyLine(lineForTspTour, GeoColor.random());
        }

        @Override
        public boolean onMapClicked(GeoLocation geoLocation) {
            return false;
        }

    }).open();
}

I hope all of the additional stuff I wrote with the maps and GroupPois is clear, the point is, I'm not even totally sure if the HamiltonianCycle is correct or not, intuitively it does not look correct at least ;) Can someone tell me if I'm missing something?

Thanks, Simon

How to import a ready made JgraphT so that I can use it in a different program.

I am asking this question because my program takes half an hour to create a graph of 16000 nodes (3x 16000 to get edge no). I don't know why it takes so long. I use my own Vertex and Edge class. So I figured perhaps I can precompute the graph (for half an hour!) and then import a ready populated version for visualizationa and further processing.

Dijkstra with radius param not working

I used the DijkstraShortestPath(Graph<V, E> graph, V startVertex, V endVertex, double radius) for a Yen's Algorithm implementation but it aways returns me a null path. Running the DijkstraShortestPath without the radius param it returns me the expected.

Loops in DirectedWeightedMultigraph

While using DirectedWeightedMultigraph I ran into an error when I added edges where the source and target are the same, i.e. loops. The documentation says: "A directed weighted multigraph is a non-simple directed graph in which loops and multiple edges between any two vertices are permitted, and edges have weights."

DirectedWeightedMultigraph<Object, Object> g = new DirectedWeightedMultigraph<Object, Object>(Object.class);
Object n1 = new Object();
g.addVertex(n1);
g.addEdge(n1, n1);

But this code results in:

Exception in thread "main" java.lang.IllegalArgumentException: loops not allowed
    at org.jgrapht.graph.AbstractBaseGraph.addEdge(AbstractBaseGraph.java:203)

A fix could be to modify the constructor in DirectedWeightedMultigraph:

public FixedDirectedWeightedMultigraph(EdgeFactory<V, E> ef) {
    super(ef, true, true);
}

Which means that the super class DirectedMultigraph needs an additional constructor:

public FixedDirectedMultigraph(EdgeFactory<V, E> ef,
            boolean allowMultipleEdges, boolean allowLoops) {
    super(ef, allowMultipleEdges, allowLoops);
}

Can anyone confirm this issue?

Thanks.

Wiki

The wiki now lives at https://github.com/jgrapht/jgrapht/wiki

@jsichi Could you please have a look if all pages are there?

• Removed news section, The commit history, HISTORY.md and announcement on mailing list should suffice

Open:

• pull etc/graph-links.html into wiki, remove from source repo
• pull etc/release-process.html into wiki, remove from source repo (merge with existing ContributorGuidelines)
• What about the donation page at sourceforge? Will it still be maintained after github move?

Move over MANIFEST.MF support from svn

A contributor had previously added OSGi support, but I think the manifest got left out during the maven move. Need to port that over.

uber-jar for jgrapht-ext module?

The pom for jgrapht-ext includes the maven-shade plugin. The function of this plug-in, in general, is to create, in addition to the module's regular jar, an uber-jar which includes the classes of all of the module's dependencies.

In this case, it would presumably be helpful to someone whose main objective is to exclusively use the jgrapht-ext module: instead of having to download two or more jars, they get to download this single uber-jar to do their thing. (This doesn't contribute anything to someone who uses jgrapht-ext as part of a maven-controlled project as maven would resolve those dependencies; it's only helpful to someone who's manually downloading jars.)

Thing is, the shade-plugin is configured to include (to the exclusion of anything else) "net.sf.jgrapht". Since this is not one of the module's dependencies (in fact, no such artifact exists), nothing at all gets added to the uber-jar, and the combined jar is merely a duplicate of the regular jar.

The question is whether this should be fixed such that the module does generate an uber-jar, or should the whole shade piece be dropped from this module?

Bundle Version not correct for release 0.9.0

Within the manifest the Bundle Version is not aligned with your release version 0.9.0 it is set to 0.8.4.dev instead.

Manifest line:
Bundle-Version: 0.8.4.dev

DirectedAcyclicGraph doesn't have constructor that takes an EdgeFactory

There doesn't seem to be a way to construct a DirectedAcyclicGraph with a specific EdgeFactory instance.

kShortestPaths algorithm error

I create a Simple Graph with edges below,
1 2
1 5
2 3
2 4
3 4
4 5

Then find the k shortest paths from 1 to 2, the algorithm gives:
[[(1 : 2)], [(1 : 5), (1 : 5), (1 : 2)], [(1 : 5), (4 : 5), (2 : 4)], [(1 : 5), (4 : 5), (3 : 4), (2 : 3)]]

the path [(1 : 5), (1 : 5), (1 : 2)] has a loop in it!!!

Any thing wrong?

New release?

There are plenty of algorithms in the current master branch that are not part of 0.8.3 (e.g. HopcroftKarp), how about a new release?

Resubmit kuhn-munkres

I had to revert the last merge due to build failure, so a new pull request is needed.

Class cast exception's

Dear Member's community,

I see a lot of java.lang.classcastException 's in the JGrapht Libray.

For example, when I tried to test the classes in org.jgrapht.alg package such as DijkstraShortestPath I am getting the class cast Exception's from org.jgrapht.graph, org.jgrapht.traverse, and org.jgrapht.util.

And BellmanFordShortestPath algorithm, I see the same kind of exception's in AbstractPathElement, BellmanFordIterator classes from the org.jgrapht.alg package.

Is there any solid reason behind this.Can you please enlighten me upon this.

Your help is appreciated

Error in FloydWarshwall algorithm

Hi,

It seems that the FloydWarshallShortestPaths algorithm could give a wrong result for PseudoGraph. Actually, it assumes there is only one edge between two node.

During path length computation process, the d matrix is initialized with the following lines :
Set edges = graph.edgeSet();
for (E edge : edges) {
V v1 = graph.getEdgeSource(edge);
V v2 = graph.getEdgeTarget(edge);

        int v_1 = vertices.indexOf(v1);
        int v_2 = vertices.indexOf(v2);

        d[v_1][v_2] = graph.getEdgeWeight(edge);
        if (!(graph instanceof DirectedGraph<?, ?>)) {
            d[v_2][v_1] = graph.getEdgeWeight(edge);
        }
    }

And no test are done to check if d[v_1][v_2] already have a value. It should be an if to check that :
Set edges = graph.edgeSet();
for (E edge : edges) {
V v1 = graph.getEdgeSource(edge);
V v2 = graph.getEdgeTarget(edge);

        int v_1 = vertices.indexOf(v1);
        int v_2 = vertices.indexOf(v2);
        if (d[v_1][v_2] > graph.getEdgeWeight(edge) {
            d[v_1][v_2] = graph.getEdgeWeight(edge);
            if (!(graph instanceof DirectedGraph<?, ?>)) {
                d[v_2][v_1] = graph.getEdgeWeight(edge);
            }
        }
    }

Sorry to don't make a real proper patch, it is my first comment on github so I'm not used to available tools ;).

Thanks for your work on JGraphT :)
M. Nadal

BUG: Suspected integer overflow in RandomGraphGenerator

When generating a random SimpleDirectedGraph with "aNumOfVertexes" = 50000 and "aNumOfEdges" = 150000 we get the exception below. It appears there might be some integer overflow issues. We tried changing to double in the code and it seemed to work fine. Is this a known issue and is there an official patch for this?

Exception in thread "main" java.lang.IllegalArgumentException: numOfEdges is not valid for the graph type
-> Invalid number Of Edges=150000 for: graph type=class org.jgrapht.graph.SimpleDirectedGraph ,number Of Vertexes=50000
-> Advice: For the Max value , check the javadoc for org.jgrapht.generate.RandomGraphGenerator.DefaultEdgeTopologyFactory

Querying DAG

Should jgraph also have ability through API to perform queries on graphs. I am not suggesting venturing into full scale graph DB but surely an API/language based constructs could be very helpful.

Graph.contains() methods: take Object not generic type

contains() methods of graph implementations take only the specified generic type and not Object. This is fundamentally wrong and should be fixed to take any Object.

// edit: the same applies to remove() methods

GraphPath for simple graphs - constructor without edge list?

In simple graphs, where there can only be one edge between two vertices, it would be useful to have a constructor for graph paths where the edge list is not needed, unlike the parameter in GraphPathImpl's constructor. If this is a desirable feature I could implement it, just wanted to have someone else's opinion first.

Thanks.

DirectedNeighborIndex + ListenableDirectedGraph = bug?

Hello jgrapht!

I think I came across a bug that affects a general graph behavior.

When using ListenableDirectedGraph one can add a listener using method 'addGraphListener()'.
When using DirectedNeighborIndex a listenable graph should be passed in the DirectedNeighborIndex's contructor as a parameter.
According to the DirectedNeighborIndex's spec "If it [DirectedNeighborIndex] is added as a listener to a graph other than the one it indexes, results are undefined." Does it mean that the behavior of the DirectedNeighborIndex becomes undefined or also the behavior of the graphs concerned as well?
I suppose, that graphs concerned shouldn't be affected in this situation. Is it true?

In reality the behavior of graph changes and java.lang.IllegalArgumentException is thrown at org.jgrapht.graph.AbstractGraph.assertVertexExist() when trying to add a new edge in the graph.

The following JUnit test highlights the problem:

    public void testListenableDirectedGraph() throws Exception {
        ListenableDirectedGraph<String, DefaultEdge> listenDG = new ListenableDirectedGraph<String, DefaultEdge>(
                DefaultEdge.class);
        String vertex1 = "v1";
        listenDG.addVertex(vertex1);
        String vertex2 = "v2";
        listenDG.addVertex(vertex2);
        listenDG.addEdge(vertex1, vertex2);

        ListenableDirectedGraph<String, DefaultEdge> listenDG2 = new ListenableDirectedGraph<String, DefaultEdge>(
                DefaultEdge.class);
        DirectedNeighborIndex<String, DefaultEdge> dni = new DirectedNeighborIndex<String, DefaultEdge>(
                listenDG2);

        listenDG.addGraphListener(dni);

        String vertex3 = "v3";
        listenDG.addVertex(vertex3);
        listenDG.addEdge(vertex3, vertex1); // throws IllegalArgumentException exception
    }

In the jgrapht mailing list there's a bug which looks related, although I cannot be sure: http://jgrapht-users.107614.n3.nabble.com/Re-Bug-in-the-induced-subgraphs-Patch-and-JUnit-test-td1605888.html

Could you please confirm if this is a problem?
As a possible solution, is it possible to have a check in the 'addGraphListener()' to avoid such behavior?

Thanks,
Konstantin

Broken link in Graph interface javadoc

The URL here:
https://github.com/jgrapht/jgrapht/blob/master/jgrapht-core/src/main/java/org/jgrapht/Graph.java#L72
should be https://github.com/jgrapht/jgrapht/wiki/EqualsAndHashCode instead of http://pub.eigenbase.org/wiki/JGraphT:EqualsAndHashCode.

I'll send a PR to fix this

Incorrect return value of indegree

hi, Barak Naveh

I am now using JGraphT to implement a tool.

However, I found something interesting in class DirectedMultigraph, which I used in my code to build a DirectedMultigraph-type Graph with loops in it. the calling of method "inDegreeOf" or "outDegreeOf " returns incorrect value.

For example, the expected number of a vertex inDegree is 3, while it returns 2. And the method "outgoingEdgesOf " "incomingEdgesOf" have the same problem. sometimes it works well with different parameters.

I am not sure whether there is bug in these class or I just misunderstanding the usage of these class ?

below is my code :
<DirectedMultigraph<URL, DefaultEdge> g =
new DirectedMultigraph<URL, DefaultEdge>(DefaultEdge.class);

    try {
        URL root = new URL("http://www.popsugar.com");
        URL shopstyle = new URL("http://www.shopstyle.com");
        URL fashion = new URL("http://www.popsugar.com/fashion");
        URL bella = new URL("http://www.bellasugar.com");
        URL fit = new URL("http://www.fitsugar.com");
        URL buzz = new URL("http://www.buzzsugar.com");
        URL tres = new URL("http://www.tressugar.com");
        URL yum = new URL("http://www.yumsugar.com");

        // add the vertices
        g.addVertex(root);
        g.addVertex(shopstyle);
        g.addVertex(fashion);
        g.addVertex(bella);
        g.addVertex(fit);
        g.addVertex(buzz);
        g.addVertex(tres );
        g.addVertex(yum);


       g.addEdge(root, buzz);
       g.addEdge(root, yum);
       g.addEdge(root, fit);

        g.addEdge(shopstyle,root);
        g.addEdge(shopstyle,fashion);
        g.addEdge(shopstyle, yum);

       g.addEdge(fit, bella);
        g.addEdge(fit, shopstyle);

    } catch (MalformedURLException e) {
        e.printStackTrace();
    }

// create a graph based on URL objects
DirectedMultigraph<URL, DefaultEdge> hrefGraph = createHrefGraph();

 System.out.println("allow loops: " +hrefGraph.isAllowingLoops());
 System.out.println("AllowingMultipleEdges: " +hrefGraph.isAllowingMultipleEdges());


    URL popsugar = new URL("http://www.yumsugar.com");
    System.out.println(hrefGraph.containsVertex(popsugar));

    Set<DefaultEdge> relatedEdges = hrefGraph.edgesOf(popsugar);
    Set<DefaultEdge> incomingEdges = hrefGraph.incomingEdgesOf(popsugar);
    Set<DefaultEdge> outgoingEdges = hrefGraph.outgoingEdgesOf(popsugar);

hope to get your feedback asap.

Lucy

Inheritance problem with JGraphXAdapter/mxGraph

I am able to correctly compile and run the JGraphXAdapterDemo class included in the demo package. However, the same exact code copied and pasted into a project I'm working on generates a inheritance error whenever the JGraphXAdapter object (named jgxAdapter in the demo file) is implicitly casted as a mxGraphx, such as in the constructor mxGraphComponent(com.mxgraph.view.mxGraph arg0). If I try to instantiate a previously declared mxGraph object as a JGraphXAdapter<A,B>(), I also get a "Type mismatch: cannot convert ..." error from Eclipse.

This issue most likely has nothing to do with any bugs or problems in the jgrapht code; nevertheless, I would appreciate any guidance as to what may be causing it (perhaps some user had the same issue before). I am using the most recent jgrapht and jgraphx code fetched from Git. Thank you

With Listenable Graph edgeSet is not correct

Hi,

I have a problem when using a ListenableDirectedGraph with a custom edge, as shown below:

ListenableDirectedGraph<CypherBasicNode, CypherBasicEdge> dirGraph =
new ListenableDirectedGraph<CypherBasicNode, CypherBasicEdge>(CypherBasicEdge.class);

Everything is displayed fine in the Applet, but when I issue a dirGraph.edgeSet() the set is not correct. The first value in the set it is correct, while all the rest are null. I was researching and saw that when an addEdge is made, the empty constructor of the custom edge class is called (which I don't understand why, because I create the edge beforehand and I add it using:

CypherBasicEdge edge = new CypherBasicEdge(relId);

dirGraph.addEdge(firstNode, secondNode, edge);

). If I delete the empty constructor I get a "java.lang.RuntimeException: Edge factory failed" exception, because in add newInstance() is called (which is weird considering that an edge Object is given as an argument to addEdge ).

If I run this code:

CypherBasicEdge edge = new CypherBasicEdge(relId);

dirGraph.addEdge(firstNode, secondNode, edge);

System.out.println("first edge: " + edge);

System.out.println("second edge: " + dirGraph.getEdge(firstNode, secondNode));

I get the following output:

first edge: r2 {}
second edge: null {}

Which to me seems very unlikely to be correct. Meanwhile, the visual representation is correct. Also, if I change the graph from ListenableDirectedGraph to DefaultDirectedGraph, everything works correctly.

I am using Jgrapht 0.9.0.

Best regards,
Andreea Sandu

Provide jgrapht as an Eclipse plugin

Our Eclipse project would like to use jgrapht libraries and it would make our life much more easier if it was available either in Orbit or any other update site that our project could just depend on. Is it already available anywhere? If not, any reason why?

KShortestPaths / graph must contain the start vertex

When searching for a path in a graph with 2 loops (sample below), attempting to search with k=2 results in an exception.

This oddly enough seems to depend on node-names.
Substituting the node 616 with 1 will allow the method call to succeed without incident.

// long[] nodes_ = { 590,from, from,1, 1,to, to,622, 1,622, 1,590};

Can't come up with a better explanation, I'm simply perplexed by this behavior.

public static void main(String[] arr) { ListenableDirectedGraph g = new ListenableDirectedGraph( DefaultEdge.class ); long from = 0; long to = 100;

    long[] nodes_ = { 590,from, from,616, 616,to, to,622, 616,622, 616,590};
    for (int i = 0; i < nodes_.length; i ++) {
        g.addVertex(nodes_[i]);
    }

    System.out.println("digraph g {");
    for (int i = 0; i < nodes_.length; i += 2) {
        g.addEdge(nodes_[i+1], nodes_[i]);
        g.addEdge(nodes_[i], nodes_[i+1]);
        System.out.println("  " + nodes_[i] + " -> " + nodes_[i+1] + ";");
        System.out.println("  " + nodes_[i+1] + " -> " + nodes_[i] + ";");
    }
    System.out.println("}");

    // if k=1 then 609->590->609 is ignored and no exception is thrown
    KShortestPaths ksp = new KShortestPaths(g, from, 2); 
    System.out.println("// Searching path from " + from + " to " + to);
    List<GraphPath> paths = ksp.getPaths(to);
    if (paths == null)
        System.out.println("no path found.");
    else {
        for (GraphPath p : paths) {
            System.out.println(p.getEdgeList());
        }
    }
}

Result:

Exception in thread "main" java.lang.IllegalArgumentException: graph must contain the start vertex
    at org.jgrapht.traverse.CrossComponentIterator.(CrossComponentIterator.java:170)
    at org.jgrapht.traverse.BreadthFirstIterator.(BreadthFirstIterator.java:92)
    at org.jgrapht.alg.ConnectivityInspector.connectedSetOf(ConnectivityInspector.java:142)
    at org.jgrapht.alg.ConnectivityInspector.pathExists(ConnectivityInspector.java:208)
    at org.jgrapht.alg.RankingPathElementList.isGuardVertexDisconnected(RankingPathElementList.java:347)
    at org.jgrapht.alg.RankingPathElementList.isNotValidPath(RankingPathElementList.java:364)
    at org.jgrapht.alg.RankingPathElementList.addPathElements(RankingPathElementList.java:203)
    at org.jgrapht.alg.KShortestPathsIterator.tryToAddNewPaths(KShortestPathsIterator.java:361)
    at org.jgrapht.alg.KShortestPathsIterator.updateOutgoingVertices(KShortestPathsIterator.java:398)
    at org.jgrapht.alg.KShortestPathsIterator.next(KShortestPathsIterator.java:177)
    at org.jgrapht.alg.KShortestPaths.getPaths(KShortestPaths.java:150)
    at main.main(main.java:46)

Help needed: Looking for OSGi bundle

Currently, I am using jgrapht-0.8.3-bundle but want to upgrade to the latest. I could not find any OSGi bundle great than 0.8.3.

Any pointers will be appreciated.

.addEdge should take care of adding non-existing vertexes

I've been testing the lib and now when testing basic functionality i just reacted when .addEdge is throwing an exception "vertices must be in the graph already!"

When doing...

DirectedAcyclicGraph<String, DefaultEdge> a = new DirectedAcyclicGraph<String, DefaultEdge>(DefaultEdge.class);

String str1 = "Foo";
String str2 = "Bar";

a.addEdge(str1, str2);

addEdge should take care of adding the non-existing vertexes passed as parameters to the nodes list when they do not exist...

Dual license under LGPL and EPL

JGraphT is currently licensed under LGPL. This makes it impossible to base on JGraph in any Apache or Eclipse project as LGPL is incompatible with Apache 2.0 lciense (http://www.apache.org/legal/3party.html and EPL license http://mmilinkov.wordpress.com/2009/04/30/lgpl-pain/). The blog post provides following main reason: Inclusion in commercial projects, where only binaries are distributed.

As EPL and LGPL are pretty similar in their requirements: Changes in the code have to be made available again. Therefore I want to ask to dual license JGraphT. That means, a user can choose whether to use the LGPL license or the EPL license, making it possible to use JGraphT in GPL, Apache and Eclipse projects.

Example projects with dual license (and explanation text)

• Logback: http://logback.qos.ch/license.html
• qooxdoo. http://qooxdoo.org/license

GraphML import

Hi,

I have seen that this library delivers an GraphML-Export functionality, but I wasn't able to find an import.

Short: Is it possible to read a graphML-File (as a string) and get an Graph-Object(-hierarchy)?

Thanks a lot.

Strange problem with isomorphism

Hi,

I have a strange problem in my code....

I'm working with isomorphisms my code give me an error when I try to do an isomorphism over two particular graphs....

I'm using this:

AdaptiveIsomorphismInspectorFactory.createIsomorphismInspector(graph,graph2).isIsomorphic()

and I have this error:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 2
at org.jgrapht.experimental.isomorphism.EquivalenceIsomorphismInspector.createPermutationIterator(Unknown Source)
at org.jgrapht.experimental.isomorphism.AbstractExhaustiveIsomorphismInspector.init(Unknown Source)
at org.jgrapht.experimental.isomorphism.AbstractExhaustiveIsomorphismInspector.(Unknown Source)
at org.jgrapht.experimental.isomorphism.EquivalenceIsomorphismInspector.(Unknown Source)
at org.jgrapht.experimental.isomorphism.AdaptiveIsomorphismInspectorFactory.createTopologicalExhaustiveInspector(Unknown Source)
at org.jgrapht.experimental.isomorphism.AdaptiveIsomorphismInspectorFactory.createAppropriateConcreteInspector(Unknown Source)
at org.jgrapht.experimental.isomorphism.AdaptiveIsomorphismInspectorFactory.createIsomorphismInspector(Unknown Source)
at org.jgrapht.experimental.isomorphism.AdaptiveIsomorphismInspectorFactory.createIsomorphismInspector(Unknown Source)

over thousands of graphs it works, but over those two graphs it doesn't work....
why?

Any advice??

Thanks

GraphIsomorphismInspector infinite loop?

Hi,

I'm trying to verify isomorphism between two graphs. The isIsomorphic method seems not to terminate when I have to check graph04 and graph05 (see the java code).

---

package tests.jgrapht;

import org.jgrapht.UndirectedGraph;
import org.jgrapht.experimental.isomorphism.AdaptiveIsomorphismInspectorFactory;
import org.jgrapht.experimental.isomorphism.GraphIsomorphismInspector;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.SimpleGraph;

public final class JGraphTIsomorphicTest {
private JGraphTIsomorphicTest() {

    UndirectedGraph<String, DefaultEdge> graph04 = createGraph04();
    UndirectedGraph<String, DefaultEdge> graph05 = createGraph05();

    GraphIsomorphismInspector iso3 = AdaptiveIsomorphismInspectorFactory.createIsomorphismInspector(graph04, graph05, null, null);
    boolean isoResult3 = iso3.isIsomorphic();
    if (isoResult3) {
        System.out.println("Graphs are isomorphic.");
    } else {
        System.out.println("Graphs are NOT isomorphic.");
    }
}

public static void main(String[] args) {
    JGraphTIsomorphicTest test = new JGraphTIsomorphicTest();
}

private UndirectedGraph<String, DefaultEdge> createGraph04() {
    UndirectedGraph<String, DefaultEdge> g = new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);

    String v1 = "1";
    String v2 = "2";
    String v3 = "3";
    String v4 = "4";
    String v5 = "5";
    String v6 = "6";
    String v7 = "7";
    String v8 = "8";
    String v9 = "9";
    String v10 = "10";
    String v11 = "11";
    String v12 = "12";
    String v13 = "13";
    String v14 = "14";
    String v15 = "15";
    String v16 = "16";

    g.addVertex(v1);
    g.addVertex(v2);
    g.addVertex(v3);
    g.addVertex(v4);
    g.addVertex(v5);
    g.addVertex(v6);
    g.addVertex(v7);
    g.addVertex(v8);
    g.addVertex(v9);
    g.addVertex(v10);
    g.addVertex(v11);
    g.addVertex(v12);
    g.addVertex(v13);
    g.addVertex(v14);
    g.addVertex(v15);
    g.addVertex(v16);

    g.addEdge(v1, v2);
    g.addEdge(v3, v2);
    g.addEdge(v2, v4);
    g.addEdge(v5, v4);
    g.addEdge(v4, v6);
    g.addEdge(v7, v5);
    g.addEdge(v5, v8);
    g.addEdge(v9, v6);
    g.addEdge(v6, v10);
    g.addEdge(v11, v8);
    g.addEdge(v8, v9);
    g.addEdge(v9, v12);
    g.addEdge(v13, v3);
    g.addEdge(v3, v7);
    g.addEdge(v7, v11);
    g.addEdge(v11, v14);
    g.addEdge(v15, v13);
    g.addEdge(v13, v14);
    g.addEdge(v14, v12);
    g.addEdge(v12, v16);
    g.addEdge(v1, v15);
    g.addEdge(v15, v16);
    g.addEdge(v16, v10);
    g.addEdge(v1, v10);

    return g;
}

private UndirectedGraph<String, DefaultEdge> createGraph05() {
    UndirectedGraph<String, DefaultEdge> g = new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);

    String v1 = "1";
    String v2 = "2";
    String v3 = "3";
    String v4 = "4";
    String v5 = "5";
    String v6 = "6";
    String v7 = "7";
    String v8 = "8";
    String v9 = "9";
    String v10 = "10";
    String v11 = "11";
    String v12 = "12";
    String v13 = "13";
    String v14 = "14";
    String v15 = "15";
    String v16 = "16";

    g.addVertex(v1);
    g.addVertex(v2);
    g.addVertex(v3);
    g.addVertex(v4);
    g.addVertex(v5);
    g.addVertex(v6);
    g.addVertex(v7);
    g.addVertex(v8);
    g.addVertex(v9);
    g.addVertex(v10);
    g.addVertex(v11);
    g.addVertex(v12);
    g.addVertex(v13);
    g.addVertex(v14);
    g.addVertex(v15);
    g.addVertex(v16);

    g.addEdge(v1, v2);
    g.addEdge(v3, v4);
    g.addEdge(v5, v6);
    g.addEdge(v7, v8);
    g.addEdge(v9, v1);
    g.addEdge(v1, v3);
    g.addEdge(v3, v5);
    g.addEdge(v5, v10);
    g.addEdge(v11, v9);
    g.addEdge(v9, v10);
    g.addEdge(v10, v7);
    g.addEdge(v7, v12);
    g.addEdge(v13, v8);
    g.addEdge(v8, v6);
    g.addEdge(v6, v4);
    g.addEdge(v4, v14);
    g.addEdge(v15, v13);
    g.addEdge(v13, v14);
    g.addEdge(v14, v2);
    g.addEdge(v2, v16);
    g.addEdge(v11, v12);
    g.addEdge(v12, v15);
    g.addEdge(v15, v16);
    g.addEdge(v11, v16);

    return g;
}

}

How to copy a graph?

I've spent 1 hour to get way to copy a graph.

I've found graph generator package but It seems it doesn't have such feature.