使用 jgrapht 图库进行图形处理

在 了解数据结构图 （graph） 的学习中，我们了解到了图的基本概念，并通过学习 迪杰斯特拉 ( Dijkstra ) 最短路径算法 和 DFS(深度优先遍历) 以及 BFS(广度优先遍历) ，可以了解到怎么求图中的最短路径。为什么学习图呢？在调度任务中，大量使用了图的概念，处理任务的依赖关系，所以，为了彻底弄懂原理，有必要系统粗略地学习下。除此之外，在机器学习中例如知识图谱、推荐系统等也大量使用了图。

接下来，我们通过 jgrapht 库，对图进行操作。 jgrapht 库提供了在 java 中进行图运算的能力，开源地址：https://github.com/jgrapht/jgrapht 。下面我们将通过一些小栗子，学习该库的使用。

例子1：基本的API

在 图 中，有一些基本的概念，例如 顶点Vertex、边edge、度degree、有环、无环。如果不了解，可以在上面提到的文章中了解。好了，下面实操实操。

代码中，描述了下图所示中的有向图

 

    @Test
    public void testOtherAPI() {
        String a = "A";
        String b = "B";
        String c = "C";
        String d = "D";
        String e = "E";
        String f = "F";

        // 构建图
        Graph<String, DefaultEdge> g = new DefaultDirectedGraph<>(DefaultEdge.class);
        // 添加顶点
        g.addVertex(a);
        g.addVertex(b);
        g.addVertex(c);
        g.addVertex(d);
        g.addVertex(e);
        g.addVertex(f);
        // 添加边
        g.addEdge(a, b);
        g.addEdge(a, c);
        g.addEdge(b, d);
        g.addEdge(c, e);
        g.addEdge(d, f);
        g.addEdge(e, f);

        // 度
        System.out.println(g.degreeOf(a)); // 出度 output: 2
        System.out.println(g.inDegreeOf(a)); // 入度 output: 0
        System.out.println(g.outDegreeOf(a)); // 入度 output: 2

        // Graphs 工具类
        // 当前顶点的后续节点列表 output: [B, C]
        System.out.println(Graphs.successorListOf(g, a));
        // 当前顶点的后续节点列表 output: [D, E]
        System.out.println(Graphs.predecessorListOf(g, f));

        // 图中“环”的操作
        CycleDetector<String, DefaultEdge> cycleDetector = new CycleDetector<>(g);
        // 探测图中是否有环 output: false
        System.out.println(cycleDetector.detectCycles());
        // 找出图中的环 output: []
        System.out.println(cycleDetector.findCycles());
    }

例子2：有向图

    @Test
    public void testDirectedGraph() {
        // create a graph based on URL objects
        Graph<URL, DefaultEdge> hrefGraph = createHrefGraph();

        // note directed edges are printed as: (<v1>,<v2>)
        // 打印所有的路径，默认是第一个添加的edge是起始点顶点
        // 前面的 [] 是显示顶点数；第二个 [] 是路径
        // 打印([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)])
        System.out.println(hrefGraph.toString());
    }

    private static Graph<URL, DefaultEdge> createHrefGraph() {
        Graph<URL, DefaultEdge> 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;
    }

例子3：广度优先和深度优先算法遍历有向无环图

    /**
     * 测试广度优先遍历
     *
     * ([v1, v2, v3, v4, v5], [(v1,v5), (v5,v3), (v3,v4), (v1,v2), (v4,v2)])
     * []
     * [v2, v3, v4, v5]
     * v1
     * v5
     * v2
     * v3
     * v6
     * v4
     */
    @Test
    public void testBreadthFirstIterator() {
        DirectedAcyclicGraph<String, DefaultEdge> dag = createGraph();
        System.out.println(dag);
        System.out.println(dag.getAncestors("v1"));
        System.out.println(dag.getDescendants("v1"));

        BreadthFirstIterator<String, DefaultEdge> bfi = new BreadthFirstIterator<>(dag, "v1");
        while (bfi.hasNext()) {
            System.out.println(bfi.next());
        }
    }

    /**
     ([v1, v2, v3, v4, v5], [(v1,v5), (v5,v3), (v3,v4), (v1,v2), (v4,v2)])
     []
     [v2, v3, v4, v5]
     v1
     v2
     v6
     v5
     v3
     v4
     * 测试深度优先遍历
     */
    @Test
    public void testDepthFirstIterator() {
        DirectedAcyclicGraph<String, DefaultEdge> dag = createGraph();
        System.out.println(dag);
        System.out.println(dag.getAncestors("v1"));
        System.out.println(dag.getDescendants("v1"));

        DepthFirstIterator<String, DefaultEdge> dfi = new DepthFirstIterator<>(dag, "v1");
        while (dfi.hasNext()) {
            System.out.println(dfi.next());
        }
    }

    /**
     * DAG有向无环图
     */
    private static DirectedAcyclicGraph<String, DefaultEdge> createGraph() {
        DirectedAcyclicGraph<String, DefaultEdge> g = new DirectedAcyclicGraph<>(DefaultEdge.class);
        String v1 = "v1";
        String v2 = "v2";
        String v3 = "v3";
        String v4 = "v4";
        String v5 = "v5";
        String v6 = "v6";

        // add the vertices
        g.addVertex(v1);
        g.addVertex(v2);
        g.addVertex(v3);
        g.addVertex(v4);
        g.addVertex(v5);
        g.addVertex(v6);

        // 如果出现了环状，抛异常 IllegalArgumentException
        // add edges to create a circuit
        g.addEdge(v1, v5);
        g.addEdge(v5, v3);
        g.addEdge(v3, v4);
        g.addEdge(v1, v2);
        g.addEdge(v2, v6);

        return g;
    }

例子4：Dijkstra算法获取最短路径

    @Test
    public void testShortestPath() {
        Graph<String, DefaultEdge> 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);


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

        DijkstraShortestPath shortestPath = new DijkstraShortestPath(g2);

        ShortestPathAlgorithm.SingleSourcePaths paths = shortestPath.getPaths(v2);

        System.out.println(paths.toString());

        GraphPath<Integer, DefaultWeightedEdge> shortestPath1 = shortestPath.getPath(v1, v3);
        GraphPath<Integer, DefaultWeightedEdge> shortestPath2 = shortestPath.getPath(v1, v2);
        GraphPath<Integer, DefaultWeightedEdge> shortestPath3 = shortestPath.getPath(v1, v1);
        GraphPath<Integer, DefaultWeightedEdge> shortestPath4 = shortestPath.getPath(v2, v1);
        GraphPath<Integer, DefaultWeightedEdge> shortestPath5 = shortestPath.getPath(v2, v3);

        // [(v1 : v2), (v2 : v3)]
        System.out.println(shortestPath1.toString());

        // [(v1 : v2)]
        System.out.println(shortestPath2.toString());

        // [v1]
        System.out.println(shortestPath3.toString());

        //路径没有联通，所有返回的是null
        Assert.assertNull(shortestPath4);

        // [(v2 : v3)]
        System.out.println(shortestPath5.toString());
    }

例子5：有向加权图

获取从v0到v7的最短路径

    @Test
    public void testDirectedWeightedGraph() {
        SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> graph = createGraph();
        printShortestPath(graph);
    }

    /**
     * 创建一个有向带权图
     */
    public SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> createGraph() {

        String[] str = {"v0", "v1", "v2", "v3", "v4", "v5", "v6", "v7"};
        int[] startPoint = {0, 0, 0, 1, 1, 3, 3, 3, 3, 2, 4, 5, 5, 4, 6};
        int[] endPoint =   {1, 3, 2, 4, 3, 4, 5, 6, 2, 6, 5, 6, 7, 7, 7};
        double[] weights = {2, 8, 1, 1, 6, 5, 1, 2, 7, 9, 3, 4, 6, 9, 3};

        SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> directedGraph =
                new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class);

        //添加顶点
        for (String s : str) {
            directedGraph.addVertex(s);
        }

        // 起点
        DefaultWeightedEdge[] edgeSources = new DefaultWeightedEdge[startPoint.length];
        // 终点
        DefaultWeightedEdge[] edgeTargets = new DefaultWeightedEdge[startPoint.length];

        for (int i = 0; i < endPoint.length; i++) {
            edgeSources[i] = directedGraph.addEdge(str[startPoint[i]], str[endPoint[i]]);
            edgeTargets[i] = directedGraph.addEdge(str[endPoint[i]], str[startPoint[i]]);
            directedGraph.setEdgeWeight(edgeSources[i], weights[i]);
            directedGraph.setEdgeWeight(edgeTargets[i], weights[i]);
        }
        return directedGraph;
    }

    /**
     * 根据得到的带权有向图，Dijkstra计算最短路径，并保存他们的路径权值之和到数组Dij中
     */
    public static void printShortestPath(SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> graph) {

        DijkstraShortestPath<String, DefaultWeightedEdge> dijkstraAlg = new DijkstraShortestPath<>(graph);

        //获取从u0到u7的最短路径
        System.out.println("Shortest path from v1 to v8:");
        ShortestPathAlgorithm.SingleSourcePaths<String, DefaultWeightedEdge> sourcePaths = dijkstraAlg.getPaths("v0");
        GraphPath<String, DefaultWeightedEdge> u0ToU7ShortestPath = sourcePaths.getPath("v7");

        //打印路径
        List<String> pathsList = u0ToU7ShortestPath.getVertexList();
        StringBuilder sb = new StringBuilder();
        boolean firstElement = true;
        for (String s : pathsList) {
            if (firstElement) {
                sb.append(s);
                firstElement = false;
            } else {
                sb.append("->").append(s);
            }
        }
        System.out.println(sb);

        System.out.println("Shortest path weight:" + u0ToU7ShortestPath.getWeight());
    }

 输出：

Shortest path from v0 to v7:
v0->v1->v4->v7
Shortest path weight:12.0