时间戳

首页 > 解决方案 > Inserting a vertex in a GraphPath in Jgrapht

jgrapht - Inserting a vertex in a GraphPath in Jgrapht

问题描述

How can I create a new path by expanding an existing one in a graph with JgraphT e.g. after I get the shortest path between two vertices, how can I expand it by inserting an adjacent node in between the vertices that make up the path? Assume I have a path that looks like that specified below: 

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))]

标签： jgrapht

解决方案

Currently there's no direct way to insert a vertex in an existing GraphPath. The easiest way to accomplish what you want is to create a new 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);

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

推荐阅读