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.

Algorithms

JGraphT JUNG
org.jgrapht.alg

Classes  
BellmanFordShortestPath
BiconnectivityInspector
BlockCutpointGraph
BronKerboschCliqueFinder
ChromaticNumber
ConnectivityInspector
CycleDetector
DijkstraShortestPath
DirectedNeighborIndex
EdmondsKarpMaximumFlow
EulerianCircuit
FloydWarshallShortestPaths
HamiltonianCycle
KruskalMinimumSpanningTree
KShortestPaths
NeighborIndex
StoerWagnerMinimumCut
StrongConnectivityInspector
TransitiveClosure
VertexCovers
edu.uci.ics.jung.algorithms.blockmodel
edu.uci.ics.jung.algorithms.cluster
edu.uci.ics.jung.algorithms.filters
edu.uci.ics.jung.algorithms.flows
edu.uci.ics.jung.algorithms.generators
edu.uci.ics.jung.algorithms.generators.random
edu.uci.ics.jung.algorithms.importance
edu.uci.ics.jung.algorithms.layout
edu.uci.ics.jung.algorithms.layout.util
edu.uci.ics.jung.algorithms.layout3d
edu.uci.ics.jung.algorithms.matrix
edu.uci.ics.jung.algorithms.metrics
edu.uci.ics.jung.algorithms.scoring
edu.uci.ics.jung.algorithms.scoring.util
edu.uci.ics.jung.algorithms.shortestpath
edu.uci.ics.jung.algorithms.transformation

 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

About Neil Rubens

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

Leave a Reply

Your email address will not be published. Required fields are marked *

*