反转有向加权图中的边

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：

这是正确的link：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;
}

反转有向加权图中的边

Reversing the edges in directed weighted graph

java

transpose

graph