Graph Algorithms Libraries for Java

Update: I have created a jgrapht-gephi library that works well for algorithm-centric tasks.

Gephi is currently by far the best library for visualizing and interacting with graphs, it also has a large number of algorithms (many of them through plugins).

However since Gephi is oriented towards UI aspects, it’s graph implementation has quite a heavy overhead.  In addition manipulation of graphs is geared towards UI as well; e.g. only one graphModel per workspace, etc.

To solve the above problem I have combined JGraphT with Gephi.

For more details see the rest of the post and
https://github.com/gephi/gephi/issues/526
https://forum.gephi.org/viewtopic.php?f=27&t=1639

It seems that the main libraries (not including Gephi) focused on algorithms are JGraphT and JUNG.

SubGraphs

JGraphT has a nice Subgraph class.

JUNG does not have an explicit subgraph; the indirect usage of subgraphs seems to be only for the task of filtering.

Graph Interface

Seem quite similar for both; see examples bellow.

JGraphT

// @see http://sourceforge.net/apps/mediawiki/jgrapht/index.php?title=jgrapht:HelloWorld

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

String v1 = "v1";
String v2 = "v2";
String v3 = "v3";
String v4 = "v4";

// add the vertices

// add edges to create a circuit

return g;

JUNG

// @see http://www.grotto-networking.com/JUNG/JUNG2-Tutorial.pdf
// Graph<V, E> where V is the type of the vertices
// and E is the type of the edges
Graph<Integer, String> g = new SparseMultigraph<Integer, String>();
// Add some vertices. From above we defined these to be type Integer.
// Add some edges. From above we defined these to be of type String
// Note that the default is for undirected edges.
g.addEdge("Edge-A", 1, 2); // Note that Java 1.5 auto-boxes primitives

Keywords

graph clustering modularity network optimization see http://ActiveIntelligence.org
This entry was posted in Uncategorized. Bookmark the permalink.

2 Responses to Graph Algorithms Libraries for Java

1. Blazo says:

Hi,

I am new to JGraphT. I need an algorithm for sub-graph ismorphism. I searched in this forum, but all I found are a topics on a simple graph ispomorphism.
“The subgraph isomorphism problem asks whether a graph G has a subgraph G′⊂G that is isomorphmic to a graph P. So basically you have the picture on the box of a puzzle (G) and want to know where a particular piece (P) fits, if at all. It is NP-complete because Hamiltonian cycle is a special case.”
This problem is solved by Ullman’s algorithm (1976) and the VF2 algorithm (2004).
Are this algorithms implemented? and if so can you propose a simple “how to use” example?

Thank you,

Blazo