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