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.

# Algorithms

# 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 g.addVertex(v1); g.addVertex(v2); g.addVertex(v3); g.addVertex(v4); // add edges to create a circuit g.addEdge(v1, v2); g.addEdge(v2, v3); g.addEdge(v3, v4); g.addEdge(v4, v1); 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. g.addVertex((Integer)1); g.addVertex((Integer)2); g.addVertex((Integer)3); // 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 g.addEdge("Edge-B", 2, 3);

#### Keywords

graph clustering modularity network optimization

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

I am not sure if JGrapT implements sub-graph isomorphism.

This might help: http://stackoverflow.com/questions/9599451/vf2-or-other-graph-isomorphism-implementation-in-java