jgraph的连通图使用范例

 

 

package utils;

import org.apache.commons.lang3.StringUtils;
import org.jgrapht.Graph;
import org.jgrapht.alg.connectivity.BiconnectivityInspector;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;

import java.util.Set;
import java.util.stream.IntStream;

/**
 * @ClassName: ConnectedGraphExample
 * @author kanpiaoxue
 * @version 1.0
 * @CreateTime: 2019/07/12 11:13:16
 * @Description: 连通图的示例
 */
public class ConnectedGraphExample {

    public static final int ZERO = 0;

    /**
     *
     * @param args
     * @author kanpiaoxue
     * @CreateTime: 2019/07/12 11:13:16
     */
    public static void main(String[] args) {
        Graph<Integer, DefaultEdge> g = new DefaultDirectedGraph<Integer, DefaultEdge>(DefaultEdge.class);
        IntStream.rangeClosed(1, 13).forEach(v -> {
            g.addVertex(v);
        });

        /**
         * <pre>
         * [示意图]：当前Graph是有向无环图(DAG)，方向是：从上到下。
         * -- predecessor:upstream
         *
         *  8   1   5   7   9   11
         *  | / | \  \ /    |
         *  2   3  4  6     10
         *  |   |
         *  12  |
         *    \ |
         *     13
         *
         * -- successor:downstream
         *
         * 也可以下载博客附件：连通图.drawio的压缩包，解压之后，登录 https://www.draw.io/
         * 导入之后可以查看该图。或者查看代码上面的示意图。
         *
         * </pre>
         */

        g.addEdge(8, 2);
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(1, 4);
        g.addEdge(5, 6);
        g.addEdge(7, 6);
        g.addEdge(9, 10);
        g.addEdge(2, 12);
        g.addEdge(3, 13);
        g.addEdge(12, 13);
        // 双连通性检查器
        BiconnectivityInspector<Integer, DefaultEdge> in = new BiconnectivityInspector<>(g);
        Set<Graph<Integer, DefaultEdge>> graphs = in.getConnectedComponents();
        graphs.forEach(g1 -> {
            System.out.println(g1);
        });
        /**
         * <pre>
         *  ---> output
         *  ([1, 2, 3, 4, 8, 12, 13], [{1,2}, {1,3}, {1,4}, {8,2}, {12,13}, {2,12}, {3,13}])
         *  ([5, 6, 7], [{5,6}, {7,6}])
         *  ([9, 10], [{9,10}])
         *  ([11], [])
         * </pre>
         */

        System.out.println(StringUtils.repeat("=", 100));
        Graph<Integer, DefaultEdge> g11 = in.getConnectedComponent(11);
        System.out.println(g11);

        /**
         * <pre>
         *  ---> output
         *  ([11], [])
         * </pre>
         */
        System.out.println(StringUtils.repeat("=", 100));
        Graph<Integer, DefaultEdge> g2 = in.getConnectedComponent(2);
        System.out.println(g2);
        /**
         * <pre>
         *  ---> output
         *  ([1, 2, 3, 4, 8, 12, 13], [{1,2}, {1,3}, {1,4}, {8,2}, {12,13}, {2,12}, {3,13}])
         * </pre>
         */

    }

}