是否有带加权边的 DAG？

Question

我想创建一个 DAG 以便使用 TopologicalOrderIterator 并且想在边缘上保存一些权重。但是，DAG 不允许加权边并且 TopologicalOrderIterator 不适用于 SimpleDirectedWeightedGraph。我是不是遗漏了什么，应该以某种方式禁止这种组合，还是我只是找不到合适的类?

Answer 1

只是为了更正两个错误的陈述：(1) DAG 确实允许加权边和 (2) TopologicalOrderIterator 确实存在于 SimpleDirectedWeightedGraph.

这是一个使用 SimpleDirectedWeightedGraph 和 TopologicalOrderIterator 的例子：

//Create a standard directed weighted graph. This graph type allows cycles, so, to maintain the acyclic property,
// it's the users responsibility not to add any arcs that create cycles.
Graph<Integer, DefaultWeightedEdge> graph = GraphTypeBuilder.<Integer,DefaultWeightedEdge> directed().weighted(true).buildGraph();
Graphs.addAllVertices(graph, Arrays.asList(0,1,2,3,4));
Graphs.addEdge(graph, 0,1, 10); //Adds a directed arc from vertex 0 to vertex 1 with weight 10
Graphs.addEdge(graph, 0,2, 11);
Graphs.addEdge(graph, 1,2, 12);
Graphs.addEdge(graph, 2,3, 13);
Graphs.addEdge(graph, 2,4, 14);
TopologicalOrderIterator<Integer, DefaultWeightedEdge> it = new TopologicalOrderIterator<>(graph);
while(it.hasNext()){
    System.out.println(it.next());
}

请注意，在本例中，为了构建图形，我使用了构建器范例。而不是

Graph<Integer, DefaultWeightedEdge> graph = GraphTypeBuilder.<Integer,DefaultWeightedEdge> directed().weighted(true).buildGraph();

我本可以写成：

Graph<Integer, DefaultWeightedEdge> graph = new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class);

或者您可以使用专门的 DirectedAcyclicGraph 图形格式：

DirectedAcyclicGraph<Integer, DefaultWeightedEdge> graph = new DirectedAcyclicGraph<>(null, SupplierUtil.createDefaultWeightedEdgeSupplier(),true);
Graphs.addAllVertices(graph, Arrays.asList(0,1,2,3,4));
Graphs.addEdge(graph, 0,1, 10); //Adds a directed arc from vertex 0 to vertex 1 with weight 10
Graphs.addEdge(graph, 0,2, 11);
Graphs.addEdge(graph, 1,2, 12);
Graphs.addEdge(graph, 2,3, 13);
Graphs.addEdge(graph, 2,4, 14);
Iterator<Integer> it = graph.iterator(); //Creates a Topological order iterator
while(it.hasNext()){
    System.out.println(it.next());
}

请注意，以下代码是不正确的：

DirectedAcyclicGraph<Integer, DefaultWeightedEdge> graph = new DirectedAcyclicGraph<>(DefaultWeightedEdge.class);
Graphs.addAllVertices(graph, Arrays.asList(0,1));
Graphs.addEdge(graph, 0, 1, 10); //Adds a directed arc from vertex 0 to vertex 1 with weight 10

这将创建一个 未加权 图，然后尝试添加加权边。这将导致以下异常：

Exception in thread "main" java.lang.UnsupportedOperationException
    at org.jgrapht.graph.BaseIntrusiveEdgesSpecifics.setEdgeWeight(BaseIntrusiveEdgesSpecifics.java:138)

为了创建 DirectedAcyclicGraph 的加权版本，应使用正确的构造函数。

是否有带加权边的 DAG？

Is there a DAG with weighted edges?

jgrapht