在 Jgrapht 的 GraphPath 中插入一个顶点

Question

如何通过使用 JgraphT 在图形中扩展现有图形来创建新的 path，例如在我得到两个顶点之间的最短路径后，如何通过在构成路径的顶点之间插入一个相邻节点来扩展它？假设我有一个看起来像下面指定的路径：

Before Insertion
    VertexList:-> [1, 29, 191, 189, 126, 243, 197]
    EdgeList:-> [((1) : (29)), ((29) : (191)), ((191) : (189)), ((189) : (126)), ((126) : (243)), ((243) : (197))]
    Adjacent vertex to vertex 191 -> 44


After Insertion 
 VertexList:-> [1, 29, 191, 44, 189, 126, 243, 197]
 EdgeList:-> [((1) : (29)), ((29) : (191)), ((191) : (44)), ((44) : (189)), ((189) : (126)), ((126) : (243)), ((243) : (197))]

Answer 1

目前没有在现有 GraphPath 中插入顶点的直接方法。完成你想要的最简单的方法是创建一个新的 GraphPath.

//Get your shortest path
GraphPath<V,E> p1= ...;

//Copy the vertex list and insert your vertex in the desired position
List<V> vertexList=new ArrayList<>(p1.getVertexList());
vertexList.insert(position,vertex);

//Create a new GraphPath from the new vertex list
GraphPath<V,E> p2= new GraphWalk<>(graph, vertexList, weight);

如果图形是简单图形，上述过程通常运行良好。当图形是多重图或伪图时必须格外小心！在多图中，相同顶点之间可以有多个边。多重图中的路径必须根据其边而不是顶点序列来表示。例如。当顶点b和c之间有多个边时，其顶点表示的路径[a,b,c,d]定义不明确。因此，在多图的情况下，必须通过修改路径的 edgeList 来执行顶点插入（参见 GraphPath.getEdgeList()）

在 Jgrapht 的 GraphPath 中插入一个顶点

Inserting a vertex in a GraphPath in Jgrapht

jgrapht