JGraphT - 将BFS应用于WeightedGraph [英] JGraphT - apply BFS to WeightedGraph
问题描述
SimpleDirectedWeightedGraph< String，DefaultWeightedEdge> graph =
New SimpleDirectedWeightedGraph< String，DefaultWeightedEdge>（DefaultWeightedEdge.class）;
graph.addVertex（1）;
graph.addVertex（2）;
graph.addVertex（3）;
graph.addVertex（4）;
graph.addVertex（5）;
DefaultWeightedEdge e1 = graph.addEdge（1，2）;
graph.setEdgeWeight（e1，5）;
DefaultWeightedEdge e2 = graph.addEdge（2，3）;
graph.setEdgeWeight（e2，10）;
DefaultWeightedEdge e3 = graph.addEdge（2，4）;
graph.setEdgeWeight（e3，2）;
DefaultWeightedEdge e4 = graph.addEdge（4，5）;
graph.setEdgeWeight（e4，2）;
DefaultWeightedEdge e5 = graph.addEdge（5，3）;
graph.setEdgeWeight（e5，2）;
System.out.println（从顶点1到顶点3的最短路径：）;
List shortest_path = DijkstraShortestPath.findPathBetween（graph，1，3）;
System.out.println（shortest_path）;
它返回正确的最短路径： 1-> 2-> 4-将5-→3 。我现在的问题是 - 对于同一个图，我想获得包含顶点之间最少传输次数的路径（在这种情况下，它将是 1-> 2-> 3 ）。对于这种使用情况，BFS将是完美的解决方案。有没有办法以某种方式使用JGraphT API中的 BreadthFirstIterator 或者我必须自己编写一个算法？
最简单的解决方案是按照Dijkstra算法忽略每个边权重并计算最短路径。
它是可以使用 从加权有向图创建未加权有向图> AsUnweightedDirectedGraph 类。这简单地覆盖了每条边的 getEdgeWeight 方法，并返回 1.0 ，即默认权重。
图< String，DefaultWeightedEdge> unweightedGraph = new AsUnweightedDirectedGraph<>（graph）;
列表< DefaultWeightedEdge> path = DijkstraShortestPath.findPathBetween（unweightedGraph，1，3）;
System.out.println（path）; //打印[（1：2），（2：3）]
这可能不会提供最棒的表演。为了改进它，您可以构建自己的 BreadthFirstIterator 来迭代遍历图。此代码基于这个类，但更新以匹配更新版本的JGraphT。它提供了一个 BFSShortestPath 类，无论每个边上的权重如何，它都可以找到两个顶点之间的最短路径与BFS。
< pre $
public class Test {
public static void main（String [] args）{
SimpleDirectedWeightedGraph< String，DefaultWeightedEdge> graph =
New SimpleDirectedWeightedGraph< String，DefaultWeightedEdge>（DefaultWeightedEdge.class）;
graph.addVertex（1）;
graph.addVertex（2）;
graph.addVertex（3）;
graph.addVertex（4）;
graph.addVertex（5）;
DefaultWeightedEdge e1 = graph.addEdge（1，2）;
graph.setEdgeWeight（e1，5）;
DefaultWeightedEdge e2 = graph.addEdge（2，3）;
graph.setEdgeWeight（e2，10）;
DefaultWeightedEdge e3 = graph.addEdge（2，4）;
graph.setEdgeWeight（e3，2）;
DefaultWeightedEdge e4 = graph.addEdge（4，5）;
graph.setEdgeWeight（e4，2）;
DefaultWeightedEdge e5 = graph.addEdge（5，3）;
graph.setEdgeWeight（e5，2）;
System.out.println（BFSShortestPath.findPathBetween（graph，1，3））;
}
}
final class BFSShortestPath {
private BFSShortestPath（）{} //确保非实例化。
public static< V，E>列表与LT E - 代替; findPathBetween（Graph< V，E>图，V startVertex，V endVertex）{
MyBreadthFirstIterator< V，E> iter = new MyBreadthFirstIterator<>（graph，startVertex）;
while（iter.hasNext（））{
Object vertex = iter.next（）;
if（vertex.equals（endVertex））{
return createPath（iter，endVertex）;
}
}
返回null;
}
private static< V，E>列表与LT E - 代替; createPath（MyBreadthFirstIterator< V，E> iter，V endVertex）{
List< E> path = new ArrayList< E>（）;
while（true）{
E edge = iter.getSpanningTreeEdge（endVertex）;
if（edge == null）{
break;
}
path.add（edge）;
endVertex = Graphs.getOppositeVertex（iter.getGraph（），edge，endVertex）;
}
Collections.reverse（path）;
返回路径;
}
私有静态类MyBreadthFirstIterator< V，E>扩展BreadthFirstIterator< V，E> {
public MyBreadthFirstIterator（Graph< V，E> g，V startVertex）{
super（g，startVertex）;
$ b @Override
protected void encounterVertex（V vertex，E edge）{
super.encounterVertex（vertex，edge）;
putSeenData（vertex，edge）;
}
@SuppressWarnings（unchecked）
public E getSpanningTreeEdge（V vertex）{
return（E）getSeenData（vertex）;
}
}
}
I have written the code finding the optimal path for a Weighted Graph:
SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> graph =
new SimpleDirectedWeightedGraph<String, DefaultWeightedEdge>(DefaultWeightedEdge.class);
graph.addVertex("1");
graph.addVertex("2");
graph.addVertex("3");
graph.addVertex("4");
graph.addVertex("5");
DefaultWeightedEdge e1 = graph.addEdge("1", "2");
graph.setEdgeWeight(e1, 5);
DefaultWeightedEdge e2 = graph.addEdge("2", "3");
graph.setEdgeWeight(e2, 10);
DefaultWeightedEdge e3 = graph.addEdge("2", "4");
graph.setEdgeWeight(e3, 2);
DefaultWeightedEdge e4 = graph.addEdge("4", "5");
graph.setEdgeWeight(e4, 2);
DefaultWeightedEdge e5 = graph.addEdge("5", "3");
graph.setEdgeWeight(e5, 2);
System.out.println("Shortest path from vertex 1 to vertex 3:");
List shortest_path = DijkstraShortestPath.findPathBetween(graph, "1", "3");
System.out.println(shortest_path);
It returns the correct, shortest path: 1->2->4->5->3. My problem now is - for the same graph, I want to obtain the path containing the fewest number of transfers between vertices (in this case it would be 1->2->3). For this use-case the BFS would be the perfect solution. Is there a way to somehow use the BreadthFirstIterator from JGraphT API or do I have to write an algorithm by myself?
The simplest solution would be to ignore each of the edge weights and calculate the shortest path as per Dijkstra's algorithm.
It is possible to create an unweighted directed graph from a weighted directed graph with the AsUnweightedDirectedGraph class. This simply overrides the getEdgeWeight method for each edge and returns 1.0, i.e. the default weight.
Graph<String, DefaultWeightedEdge> unweightedGraph = new AsUnweightedDirectedGraph<>(graph);
List<DefaultWeightedEdge> path = DijkstraShortestPath.findPathBetween(unweightedGraph, "1", "3");
System.out.println(path); // prints [(1 : 2), (2 : 3)]
This might not provide the best performance. To improve it, you can build your own BreadthFirstIterator to just iterate through the graph. This code is based on this class, but updated to match the more recent versions of JGraphT. It provides a BFSShortestPath class that finds the shortest path between two vertices with a BFS, whatever the weight on each edge.
public class Test {
public static void main(String[] args) {
SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> graph =
new SimpleDirectedWeightedGraph<String, DefaultWeightedEdge>(DefaultWeightedEdge.class);
graph.addVertex("1");
graph.addVertex("2");
graph.addVertex("3");
graph.addVertex("4");
graph.addVertex("5");
DefaultWeightedEdge e1 = graph.addEdge("1", "2");
graph.setEdgeWeight(e1, 5);
DefaultWeightedEdge e2 = graph.addEdge("2", "3");
graph.setEdgeWeight(e2, 10);
DefaultWeightedEdge e3 = graph.addEdge("2", "4");
graph.setEdgeWeight(e3, 2);
DefaultWeightedEdge e4 = graph.addEdge("4", "5");
graph.setEdgeWeight(e4, 2);
DefaultWeightedEdge e5 = graph.addEdge("5", "3");
graph.setEdgeWeight(e5, 2);
System.out.println(BFSShortestPath.findPathBetween(graph, "1", "3"));
}
}
final class BFSShortestPath {
private BFSShortestPath() {} // ensure non-instantiability.
public static <V, E> List<E> findPathBetween(Graph<V, E> graph, V startVertex, V endVertex) {
MyBreadthFirstIterator<V, E> iter = new MyBreadthFirstIterator<>(graph, startVertex);
while (iter.hasNext()) {
Object vertex = iter.next();
if (vertex.equals(endVertex)) {
return createPath(iter, endVertex);
}
}
return null;
}
private static <V, E> List<E> createPath(MyBreadthFirstIterator<V, E> iter, V endVertex) {
List<E> path = new ArrayList<E>();
while (true) {
E edge = iter.getSpanningTreeEdge(endVertex);
if (edge == null) {
break;
}
path.add(edge);
endVertex = Graphs.getOppositeVertex(iter.getGraph(), edge, endVertex);
}
Collections.reverse(path);
return path;
}
private static class MyBreadthFirstIterator<V, E> extends BreadthFirstIterator<V, E> {
public MyBreadthFirstIterator(Graph<V, E> g, V startVertex) {
super(g, startVertex);
}
@Override
protected void encounterVertex(V vertex, E edge) {
super.encounterVertex(vertex, edge);
putSeenData(vertex, edge);
}
@SuppressWarnings("unchecked")
public E getSpanningTreeEdge(V vertex) {
return (E) getSeenData(vertex);
}
}
}
这篇关于JGraphT - 将BFS应用于WeightedGraph的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
