java - 反转有向加权图中的边

Question

我正在尝试反转我的图形小示例中的边，来自:

(1)---1--->(8)
 \         /
  2       1
   \     /
    v   v
     (4)

为此:.

 (1)<---1---(8)
  ^          ^
   \        /
    2      1
     \    /
       (4)

我试过:

private static void Transpose(EdgeWeightedDigraph G) {

    for (int v = 0; v < G.V(); v++) {
        // reverse so that adjacency list is in same order as original
        Stack<DirectedEdge> reverse = new Stack<DirectedEdge>();
        for (DirectedEdge e : G.adj(v)) {
            reverse.push(e);
        }
        for (DirectedEdge e : reverse) {
            adj[v].add(e);
        }
    }

}

有什么想法吗？

---

更新 1:

     private static Bag<DirectedEdge>[] adj;    // adj[v] = adjacency list for vertex v

      adj = (Bag<DirectedEdge>[]) new Bag[G.V()];
    for (int v = 0; v < G.V(); v++)
        adj[v] = new Bag<DirectedEdge>();

我的代码输出的是同一张图，我的代码没有反转边

---

更新 2: EdgeWeightedGraph

---

更新 3:

这是正确的链接:EdgeWeightedDigraph

不是以前的

这也很有用 DirectedEdge

Answer 1

由于这似乎是一个家庭作业问题(如果我对此有误请告诉我)，并且您已经说明了到目前为止您尝试过的内容以及您遇到的困难，我会给一个高分级解决方案，并省略代码来执行此操作。

基本上，您要做的就是通过 EdgeWeightedDirectedGraph.edges() 方法获取边列表。然后，为 V 个新边实例化一个新的空 EdgeWeightedDirectedGraph。由于 Edge 类型是不可变的，因此您需要创建新的边。因此，对于从原始图中检索到的每条原始边，实例化一条新边，该边的 v 和 w 颠倒但权重相同。然后，将该新的反向边添加到您的新图形中。将新的反转边添加到新图形后，您现在拥有原始图形的副本，但边缘反转了。

请注意，这种创建新图的方法是最可行的，因为 EdgeWeightedDirectedGraph 代码似乎没有删除边的便捷方法，只能添加边。

编辑:根据要求添加一些示例代码。

public static void main(String[] args) {
    EdgeWeightedDigraph g = new EdgeWeightedDigraph(3);
    DirectedEdge e1 = new DirectedEdge(0, 1, 01.10);
    g.addEdge(e1);
    DirectedEdge e2 = new DirectedEdge(1, 2, 12.21);
    g.addEdge(e2);
    DirectedEdge e3 = new DirectedEdge(2, 0, 20.02);
    g.addEdge(e3);
    System.out.println(g.toString());

    EdgeWeightedDigraph gr = reverse(g);
    System.out.println(gr.toString());
}

private static EdgeWeightedDigraph reverse(EdgeWeightedDigraph g) {
    int numVertices = g.V();
    EdgeWeightedDigraph gr = new EdgeWeightedDigraph(numVertices);
    for (DirectedEdge e : g.edges()) {
        int f = e.from();
        int t = e.to();
        double w = e.weight();
        DirectedEdge er = new DirectedEdge(t, f, w);
        gr.addEdge(er);
    }
    return gr;
}