使用Google Guava Graph API实现Kosaraju算法：求MutableValueGraph转置

嘿，刚好我对Guava Graph这块比较熟，来帮你搞定转置MutableValueGraph的问题！

Guava的ValueGraph系列确实没有内置的转置方法，但你可以手动遍历原图的所有元素，反向构建一个全新的MutableValueGraph，完全保留原接口。代码示例如下：

import com.google.common.graph.MutableValueGraph;
import com.google.common.graph.ValueGraphBuilder;

// 假设你的GraphNode类已提前定义
public static MutableValueGraph<GraphNode, Integer> transposeValueGraph(MutableValueGraph<GraphNode, Integer> originalGraph) {
    // 复制原图的所有配置（有向、自环、平行边等）
    MutableValueGraph<GraphNode, Integer> transposedGraph = ValueGraphBuilder.directed()
            .allowsSelfLoops(originalGraph.allowsSelfLoops())
            .allowsParallelEdges(originalGraph.allowsParallelEdges())
            .build();

    // 先添加所有节点，确保孤立节点也被保留在转置图中
    for (GraphNode node : originalGraph.nodes()) {
        transposedGraph.addNode(node);
    }

    // 遍历原图的每条边，反向添加到转置图，保留边的权重值
    for (GraphNode source : originalGraph.nodes()) {
        for (GraphNode target : originalGraph.successors(source)) {
            Integer edgeWeight = originalGraph.edgeValue(source, target).orElse(null);
            transposedGraph.putEdgeValue(target, source, edgeWeight);
        }
    }

    return transposedGraph;
}

说明 #

• 这段代码完全复刻了原图的配置（比如是否允许自环、平行边），保证转置图和原图的行为一致
• 会保留所有孤立节点（没有任何边的节点），避免转置图丢失信息
• 如果原图允许平行边，代码也能正确处理，因为putEdgeValue会按照配置添加对应的边

如果你可以接受切换底层接口，Guava的MutableNetwork配合Graphs工具类能更简洁地实现转置。因为Network系列支持Graphs.transpose()方法，不过你需要把边的权重封装成边对象：

首先定义一个承载权重的边类：

class WeightedEdge {
    private final int weight;

    public WeightedEdge(int weight) {
        this.weight = weight;
    }

    public int getWeight() {
        return weight;
    }
}

然后构建原Network并生成转置图：

import com.google.common.graph.Graphs;
import com.google.common.graph.MutableNetwork;
import com.google.common.graph.NetworkBuilder;

public static MutableNetwork<GraphNode, WeightedEdge> getTransposedNetwork(MutableNetwork<GraphNode, WeightedEdge> originalNetwork) {
    // 先创建一个和原配置一致的空可变Network
    MutableNetwork<GraphNode, WeightedEdge> transposedNetwork = NetworkBuilder.from(originalNetwork).build();
    
    // 利用Graphs.transpose获取转置视图，再把所有边复制到可变Network中
    Graphs.transpose(originalNetwork).edges().forEach(edge -> {
        // 获取原边的源和目标节点，反转后添加到转置图
        GraphNode originalSource = originalNetwork.incidentNodes(edge).source();
        GraphNode originalTarget = originalNetwork.incidentNodes(edge).target();
        transposedNetwork.addEdge(originalTarget, originalSource, edge);
    });
    
    return transposedNetwork;
}

说明 #

• Graphs.transpose()返回的是原Network的只读视图，所以我们需要把视图里的边复制到新的可变Network中，才能得到独立可修改的转置图
• 边对象的权重会被完整保留，不需要额外处理

内容的提问来源于stack exchange，提问作者Debapriya Biswas