JGraphT

例1: 添加点、边

import java.net.*;

import org.jgrapht.*;
import org.jgrapht.graph.*;

/**
 * A simple introduction to using JGraphT.
 *
 * @author Barak Naveh
 * @since Jul 27, 2003
 */
public final class HelloJGraphT
{
    private HelloJGraphT()
    {
    } // ensure non-instantiability.

    /**
     * The starting point for the demo.
     *
     * @param args ignored.
     */
    public static void main(String[] args)
    {
        UndirectedGraph<String, DefaultEdge> stringGraph = createStringGraph();

        // note undirected edges are printed as: {<v1>,<v2>}
        System.out.println(stringGraph.toString());

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

        // note directed edges are printed as: (<v1>,<v2>)
        System.out.println(hrefGraph.toString());
    }

    /**
     * Creates a toy directed graph based on URL objects that represents link structure.
     *
     * @return a graph based on URL objects.
     */
    private static DirectedGraph<URL, DefaultEdge> createHrefGraph()
    {
        DirectedGraph<URL, DefaultEdge> g = new DefaultDirectedGraph<URL, DefaultEdge>(DefaultEdge.class);

        try {
            URL amazon = new URL("http://www.amazon.com");
            URL yahoo = new URL("http://www.yahoo.com");
            URL ebay = new URL("http://www.ebay.com");

            // add the vertices
            g.addVertex(amazon);
            g.addVertex(yahoo);
            g.addVertex(ebay);

            // add edges to create linking structure
            g.addEdge(yahoo, amazon);
            g.addEdge(yahoo, ebay);
        } catch (MalformedURLException e) {
            e.printStackTrace();
        }

        return g;
    }

    /**
     * Create a toy graph based on String objects.
     *
     * @return a graph based on String objects.
     */
    private static UndirectedGraph<String, DefaultEdge> createStringGraph()
    {
        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;
    }
}

结果

([v1, v2, v3, v4], [{v1,v2}, {v2,v3}, {v3,v4}, {v4,v1}])
([http://www.amazon.com, http://www.yahoo.com, http://www.ebay.com], [(http://www.yahoo.com,http://www.amazon.com), (http://www.yahoo.com,http://www.ebay.com)])

例2：强、弱连通

import java.util.List;
import java.util.Set;

import org.jgrapht.DirectedGraph;
import org.jgrapht.alg.KosarajuStrongConnectivityInspector;
import org.jgrapht.alg.interfaces.StrongConnectivityAlgorithm;
import org.jgrapht.alg.ConnectivityInspector;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;

public class GraphConnDemo
{
    private DirectedGraph<String, DefaultEdge> directedGraph;

    public GraphConnDemo(){
        directedGraph = new DefaultDirectedGraph<String, DefaultEdge>(DefaultEdge.class);
        directedGraph.addVertex("a");
        directedGraph.addVertex("b");
        directedGraph.addVertex("c");
        directedGraph.addVertex("d");
        directedGraph.addVertex("e");
        directedGraph.addVertex("f");
        directedGraph.addVertex("h");
        directedGraph.addVertex("i");
        directedGraph.addEdge("a", "b");
        directedGraph.addEdge("b", "c");
        directedGraph.addEdge("c", "d");
        directedGraph.addEdge("d", "a");
        directedGraph.addEdge("c", "e");
        directedGraph.addEdge("f", "h");
        directedGraph.addEdge("f", "i");
    }

    public void testStrongConn(){
        StrongConnectivityAlgorithm<String, DefaultEdge> scAlg =
                new KosarajuStrongConnectivityInspector<String, DefaultEdge>(directedGraph);
        List<Set<String>> stronglyConnetedSet =
                scAlg.stronglyConnectedSets();

        System.out.println("Strongly connected components:");
        for (int i = 0; i < stronglyConnetedSet.size(); i++) {
            System.out.println(stronglyConnetedSet.get(i));
        }
        System.out.println();

    }
    public void testWeakConn() {
        ConnectivityInspector<String, DefaultEdge> connectivityInspector = new ConnectivityInspector<String, DefaultEdge>(directedGraph);
        List<Set<String>> weaklyConnectedSet = connectivityInspector.connectedSets();
        System.out.println("Weakly connected components:");
        for (int i = 0; i < weaklyConnectedSet.size(); i++) {
            System.out.println(weaklyConnectedSet.get(i));
        }
        System.out.println();

    }

    public static void main(String args[])
    {
        GraphConnDemo test = new GraphConnDemo();
        test.testStrongConn();
        test.testWeakConn();
    }
}

图示

结果

Strongly connected components:
[f]
[h]
[i]
[a, b, c, d]
[e]

Weakly connected components:
[a, b, c, d, e]
[f, h, i]

例3：子图

import java.util.HashSet;
import java.util.List;
import java.util.Set;

import org.jgrapht.DirectedGraph;
import org.jgrapht.alg.KosarajuStrongConnectivityInspector;
import org.jgrapht.alg.interfaces.StrongConnectivityAlgorithm;
import org.jgrapht.alg.ConnectivityInspector;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.DirectedSubgraph;

public class GraphConnDemo
{
    private DirectedGraph<String, DefaultEdge> directedGraph;
    private DirectedGraph<String, DefaultEdge> directedSubGraph;

    public GraphConnDemo(){
        directedGraph = new DefaultDirectedGraph<String, DefaultEdge>(DefaultEdge.class);
        directedGraph.addVertex("a");
        directedGraph.addVertex("b");
        directedGraph.addVertex("c");
        directedGraph.addVertex("d");
        directedGraph.addVertex("e");
        directedGraph.addVertex("f");
        directedGraph.addVertex("h");
        directedGraph.addVertex("i");
        directedGraph.addEdge("a", "b");
        directedGraph.addEdge("b", "c");
        directedGraph.addEdge("c", "d");
        directedGraph.addEdge("d", "a");
        directedGraph.addEdge("c", "e");
        directedGraph.addEdge("f", "h");
        directedGraph.addEdge("f", "i");
    }

    public void subGraph() {
        Set<String> subNode = new HashSet<String>();
        subNode.add("a");
        subNode.add("d");
        subNode.add("c");
        subNode.add("f");
        directedSubGraph = new DirectedSubgraph(directedGraph, subNode);
        System.out.println(directedSubGraph.vertexSet());
        System.out.println(directedSubGraph.edgeSet());

    }

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

结果

[a, c, d, f]
[(c : d), (d : a)]

压测： 和networkX对比

对比数据：点：593514    边： 2373298

	NetworkX(str)	JGraphT(str)	JGraphT(int)
建路网	955s	240s	224s
强连通算法	255s	76s	71s
内存峰值	71.82G	78.87G	62.9G
CPU峰值	3.2%	27%	28.5%
释放内存	33min	2min	2min

例4： 得到最短路径

    void testDijkstraShortestPath() {
        DirectedGraph<String, DefaultEdge> g2 = new DefaultDirectedGraph<String, DefaultEdge>(DefaultEdge.class);

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


        // add the vertices
        g2.addVertex(v1);
        g2.addVertex(v2);
        g2.addVertex(v3);


        // add edges to create a circuit
        g2.addEdge(v1, v2);
        g2.addEdge(v2, v3);

        DijkstraShortestPath dijk = new DijkstraShortestPath(g2);
        GraphPath<Integer, DefaultWeightedEdge> shortestPath1 = dijk.getPath(v1, v3);
        GraphPath<Integer, DefaultWeightedEdge> shortestPath2 = dijk.getPath(v1, v2);
        GraphPath<Integer, DefaultWeightedEdge> shortestPath3 = dijk.getPath(v1, v1);
        GraphPath<Integer, DefaultWeightedEdge> shortestPath4 = dijk.getPath(v2, v1);
        GraphPath<Integer, DefaultWeightedEdge> shortestPath5 = dijk.getPath(v2, v3);
        GraphPath<Integer, DefaultWeightedEdge> shortestPath6 = dijk.getPath(v2, v2);
        GraphPath<Integer, DefaultWeightedEdge> shortestPath7 = dijk.getPath(v3, v1);
        GraphPath<Integer, DefaultWeightedEdge> shortestPath8 = dijk.getPath(v3, v2);
        GraphPath<Integer, DefaultWeightedEdge> shortestPath9 = dijk.getPath(v3, v3);

    }

同时也可以判断两点之间是否可连通