JGraphT-白红宇

JGraphT

阅读量：7081 次

发布时间：2019-06-28

本文共 7471 字，大约阅读时间需要 24 分钟。

例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
     
       stringGraph = createStringGraph();        // note undirected edges are printed as: {
      
       ,
       
        }        System.out.println(stringGraph.toString());        // create a graph based on URL objects        DirectedGraph
        
          hrefGraph = createHrefGraph();        // note directed edges are printed as: (
         
          ,
          
           ) 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
           
             createHrefGraph() { DirectedGraph
            
              g = new DefaultDirectedGraph
             
              (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
              
                createStringGraph() { UndirectedGraph
               
                 g = new SimpleGraph
                
                 (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
     
       directedGraph;    public GraphConnDemo(){        directedGraph = new DefaultDirectedGraph
      
       (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
       
         scAlg =                new KosarajuStrongConnectivityInspector
        
         (directedGraph);        List
         
          
           > 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
           
             connectivityInspector = new ConnectivityInspector
            
             (directedGraph); List
             
              
               > 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
     
       directedGraph;    private DirectedGraph
      
        directedSubGraph;    public GraphConnDemo(){        directedGraph = new DefaultDirectedGraph
       
        (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
        
          subNode = new HashSet
         
          ();        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
     
       g2 = new DefaultDirectedGraph
      
       (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
       
         shortestPath1 = dijk.getPath(v1, v3);        GraphPath
        
          shortestPath2 = dijk.getPath(v1, v2);        GraphPath
         
           shortestPath3 = dijk.getPath(v1, v1);        GraphPath
          
            shortestPath4 = dijk.getPath(v2, v1); GraphPath
           
             shortestPath5 = dijk.getPath(v2, v3); GraphPath
            
              shortestPath6 = dijk.getPath(v2, v2); GraphPath
             
               shortestPath7 = dijk.getPath(v3, v1); GraphPath
              
                shortestPath8 = dijk.getPath(v3, v2); GraphPath
               
                 shortestPath9 = dijk.getPath(v3, v3); }