基于JGraphT实现的路径探寻

时间:2024-01-26 09:33:42

基于JGraphT实现的路径探寻

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

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

图实例简介

以下资料来源graph-structures

可用图概览

图类 边方向 自环 顶点对间多边 加权
SimpleGraph undirected no no no
Multigraph undirected no yes no
Pseudograph undirected yes yes no
DefaultUndirectedGraph undirected yes no no
SimpleWeightedGraph undirected no no yes
WeightedMultigraph undirected no yes yes
WeightedPseudograph undirected yes yes yes
DefaultUndirectedWeightedGraph undirected yes no yes
SimpleDirectedGraph directed no no no
DirectedMultigraph directed no yes no
DirectedPseudograph directed yes yes no
DefaultDirectedGraph directed yes no no
SimpleDirectedWeightedGraph directed no no yes
DirectedWeightedMultigraph directed no yes yes
DirectedWeightedPseudograph directed yes yes yes
DefaultDirectedWeightedGraph directed yes no yes

结构特性

无向边(undirected edges):一条边只连接一个顶点对,不施加方向。

有向边(directed edges):边具有起点和终点。

自环(self-loops):是否允许顶点的边连接到自身。

同向多边(multiple edges):是否在同一顶点对之间存在多个边(有向图中,同一顶点对之间,方向相反的两条边不计为多边)。

加权(weighted):边是否具有浮点值权重(对于该类图,通常用DefaultWeightedEdge作边类型),
未加权图被视为有统一的边权重1.0,这使它们可以用于算法中,例如查找最短路径。

业务类

抽象顶点类

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并去重,形成的边集即为最小子图。