jgrapht示例

 

官网文档地址： https://jgrapht.org/guide/UserOverview

 

import org.apache.commons.lang3.StringUtils;
import org.jgrapht.Graph;
import org.jgrapht.GraphPath;
import org.jgrapht.Graphs;
import org.jgrapht.alg.cycle.CycleDetector;
import org.jgrapht.alg.shortestpath.DijkstraShortestPath;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.traverse.BreadthFirstIterator;
import org.jgrapht.traverse.DepthFirstIterator;

import java.util.Iterator;

/**
 * @ClassName: Test
 * @author kanpiaoxue
 * @version 1.0
 * @CreateTime: 2018/12/06 10:08:24
 * @Description: jgrapht 示例
 * 
 *               <dependency>
 *               <groupId>org.jgrapht</groupId>
 *               <artifactId>jgrapht-core</artifactId>
 *               <version>1.3.0</version>
 *               </dependency>
 */
public class JgraphtExample {

    /**
     *
     * @param args
     * @author kanpiaoxue
     * @throws Exception
     * @CreateTime: 2018/12/06 10:08:24
     */
    public static void main() throws Exception {
        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));

        // 图的遍历
        // --深度优先遍历
        Iterator<String> depthFirstIterator = new DepthFirstIterator<>(g, a);
        while (depthFirstIterator.hasNext()) {
            String p = depthFirstIterator.next();
            System.out.println(p);
            /*
             * <pre>
             * A
             * C
             * E
             * F
             * B
             * D
             * </pre>
             */
        }
        System.out.println(StringUtils.center("split", 100, "=")); // 分割线
        // --广度优先遍历
        Iterator<String> breadthFirstIterator = new BreadthFirstIterator<>(g, a);
        while (breadthFirstIterator.hasNext()) {
            String p = breadthFirstIterator.next();
            System.out.println(p);
            /*
             * <pre>
             * A
             * B
             * C
             * D
             * E
             * F
             * </pre>
             */
        }

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

        // 最短路径
        GraphPath<String, DefaultEdge> path = DijkstraShortestPath.findPathBetween(g, a, f);
        // [A, B, D, F]
        System.out.println(path.getVertexList());
        DijkstraShortestPath<String, DefaultEdge> dijkstraAlg = new DijkstraShortestPath<>(g);
        // [A, B, D, F]
        GraphPath<String, DefaultEdge> path1 = dijkstraAlg.getPath(a, f);
        System.out.println(path1.getVertexList());

    }
}