基于JGraphT实现的路径探寻

业务中提出基于内存，探寻的两点间的有向以及无向路径，多点间的最小子图等需求，以下记录使用JGraphT的实现过程。

GraphT是免费的Java类库，提供数学图论对象和算法，本文只涉及路径探寻中的部分内容。

图实例简介

业务类

抽象顶点类

public class Node{

    //顶点id

    private String id;

    ...

}

抽象边缘类

public class Link{

    //边缘id

    private String id;

    //起始点id

    private String source;

    //终止点id

    private String target;

    ...

}

抽象图数据类

public class GraphDescription{

    //顶点集合

    private List<Node> nodes;

    //边缘集合

    private List<Link> links;

    ...

}

两点有向路径探寻

使用业务中的UID（String）作为顶点类，边构造使用默认边类DefaultEdge。

Graph<String, DefaultEdge> directedGraph = new DirectedMultigraph<>(DefaultEdge.class);

graphDescription.getNodes().forEach(node -> directedGraph.addVertex(node.getId()));

graphDescription.getLinks().forEach(link -> directedGraph.addEdge(link.getSource(), link.getTarget()));

最短路径探寻，先找出有向最短路径长度，最短路径长度小于限制时，按照最短路径跳数找出所有非自环路径

DijkstraShortestPath<String, DefaultEdge> dijkstraAlg = new DijkstraShortestPath<>(directedGraph);

GraphPath<String, DefaultEdge> shorest = dijkstraAlg.getPath(start, end);

if (shorest != null && shorest.getLength() <= hopsLimit) {

 AllDirectedPaths allPaths = new AllDirectedPaths(directedGraph);

 fullRes = allPaths.getAllPaths(start, end, true, shorest.getLength());

}

全路径探寻，按照跳数限制直接探寻结果

AllDirectedPaths allPaths = new AllDirectedPaths(directedGraph);

fullRes = allPaths.getAllPaths(start, end, true, hopsLimit);

两点无向路径探寻

我们构造支持无向及多边的Multigraph

Graph<String, DefaultEdge> multiGraph = new Multigraph<>(DefaultEdge.class);

graphDescription.getNodes().forEach(node -> graph.addVertex(node.getId()));

graphDescription.getLinks().forEach(link -> graph.addEdge(link.getSource(), link.getTarget()));

无向路径探寻类似于有向步骤，确认最短路径跳数探寻，结果数限制k设置为整型最大值

BidirectionalDijkstraShortestPath<String, DefaultEdge> dijkstraAlg = new BidirectionalDijkstraShortestPath<>(multiGraph);

GraphPath<String, DefaultEdge> shorest = dijkstraAlg.getPath(start, end);

if (shorest != null && shorest.getLength() <= hopsLimit) {

    KShortestSimplePaths simplePaths = new KShortestSimplePaths(multiGraph, shorest.getLength());

    fullRes = simplePaths.getPaths(start, end, Integer.MAX_VALUE);

}

全路径探寻，按照跳数限制直接探寻结果

KShortestSimplePaths simplePaths = new KShortestSimplePaths(graph, hopsLimit);

fullRes = simplePaths.getPaths(start, end, Integer.MAX_VALUE);

多点最小子图探寻

基于MultiGraph，多个点形成的集合，与自身作笛卡尔积，两两探寻最短路径后加入fullRes并去重，形成的边集即为最小子图。