标签: jgrapht

我编写了寻找加权图最佳路径的代码：

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

它返回正确的最短路径：1->2->4->5->3。我现在的问题是 - 对于同一个图，我想获得包含顶点之间传输次数最少的路径（在本例中是1->2->3）。对于这个用例，BFS 将是完美的解决方案。有没有办法以某种方式使用BreadthFirstIteratorJGraphT API 还是我必须自己编写算法？

我有一个简单的无向图G = (V, E)。给定一个节点n，有没有一种简单的方法来找到它的所有邻居，即所有节点m，使得{n, m} in E？

有edgesOf一种方法，它返回连接到给定节点的所有边。但是，似乎在无向图中它多少有些随意，哪个节点是源，哪个节点是目标。

我想我可以简单地检查我的节点是源节点还是目标节点，然后另一个节点是我要寻找的邻居，但这很麻烦。有没有更优雅的方式？

从这里开始，JGraphT 的Pair类是Serializable。但该类包含的实例成员（first和second）不是强制的Serializable。

当前的实现如下所示：

public class Pair<A, B>
    implements
    Serializable

我认为应该是这样的：

public class Pair<A extends Serializable, B extends Serializable>
    implements
    Serializable

我错过了什么吗？如果不是，那么为什么 JGraphT 不这样做呢？

我的任务类在执行之前依赖于其他任务。我想对可以并行的任务进行分组并对它们进行排序。我决定首先可以将其表示为 DAG 并尝试使用 JGrapht。首先，我遍历任务的输入列表以获取所有任务及其依赖项并将它们收集在一个列表中。然后，对于每个任务，我在图中创建一个顶点。

DirectedAcyclicGraph<Task, DefaultEdge> d = new DirectedAcyclicGraph<>(DefaultEdge.class);
Set<Task> all = collectAllTasks(tasks);
all.forEach(d::addVertex);

然后使用相同的列表我尝试在节点之间创建边缘。

all.forEach(task -> {
        Set<TaskName> predecessors = task.getPredecessors();

        predecessors.forEach(name -> {
            Task predecessor = taskService.getTaskByName(name);
            d.addEdge(predecessor, task);
        });

    });

然后我尝试对任务进行分组

private Set<Set<TaskId>> groupTasks(DirectedAcyclicGraph<TaskId, DefaultEdge> dag) {
    Set<Set<TaskId>> groups = new LinkedHashSet<>();
    Iterator<TaskId> iterator = new TopologicalOrderIterator<>(dag);

    iterator.forEachRemaining(taskId -> {
        //source?
        if (dag.incomingEdgesOf(taskId).isEmpty()) {
            if (groups.isEmpty()) {
                Set<TaskId> set = new HashSet<>();
                set.add(taskId);
                groups.add(set);
            } else {
                groups.iterator().next().add(taskId);
            }
        }

        Set<TaskId> tasks = new HashSet<>(Graphs.successorListOf(dag, taskId)); …

我正在使用一个名为JGraphT的图形库,在我的程序中,我有几个顶点通过边缘连接在一起,并且具有行程成本的权重.

在一个例子中,我只是一个整数,它的工作原理!但是,当我改变这个使用我的班级FlightData作为重量时,它不起作用.

这是我的代码,权重只是一个整数:

List<DefaultWeightedEdge> path = DijkstraShortestPath.findPathBetween(graph, start, end);
    for(int i = 0; i < path.size(); i++) {
        DefaultWeightedEdge edge = path.get(i);
        System.out.println((i+1) + " " + graph.getEdgeSource(edge) + " -> " + graph.getEdgeTarget(edge));
    }

这是我的FlightData类的权重代码:

List<FlightData> path = DijkstraShortestPath.findPathBetween(graph, start, end);    
for(int i = 0; i < path.size(); i++) {
        FlightData f = path.get(i);
    System.out.println((i+1) + " " + graph.getEdgeSource(f) + " -> " + graph.getEdgeTarget(f));
}

我的FlightData类只是一个带有访问器方法的类:

import org.jgrapht.graph.DefaultWeightedEdge;

public class FlightData extends DefaultWeightedEdge
{
    private …