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();

    }

}

图示

JGraphT

结果

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);

    }

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

例1: 添加点、边

例2：强、弱连通

例3：子图

压测： 和networkX对比

例4： 得到最短路径

相关文章

压测：和networkX对比

例4：得到最短路径