如何在EdmondsKarp最大流算法中使用自定义边并获取最小割边集

问题1：让EdmondsKarp最大流算法适配自定义边 #

你当前通过栈回溯判断调用方来动态返回getWeight结果的实现非常不稳定，库版本升级、内部调用逻辑调整都会导致逻辑失效，建议直接删除这部分覆写逻辑，通过以下方式适配：

1. 调整你的MyDefaultWeightedEdge类中getFreeCapacity方法的访问权限，至少保证和你调用算法的代码同包可访问，建议直接改为public。
2. 构造EdmondsKarpMFImpl实例时传入自定义容量函数，直接指定使用你自定义的freecapacity字段作为容量，示例代码如下：

// 此处V替换为你实际使用的顶点类型
EdmondsKarpMFImpl<V, MyDefaultWeightedEdge> maxFlowImpl = new EdmondsKarpMFImpl<>(
    yourGraph,
    edge -> (double) edge.getFreeCapacity()
);

该方式完全不依赖边的默认权重字段，适配性更强，也不会影响你其他逻辑中对边权重的使用。

问题2：获取最小割/最大流对应的边 #

获取最小割的边 #

最大流计算完成后，直接调用算法实例的getCutEdges()方法即可得到最小割的边集合，这些边是从源点所属割集指向汇点所属割集的边，示例代码：

// 计算最大流
double maxFlowValue = maxFlowImpl.getMaximumFlow(sourceNode, sinkNode);
// 获取最小割边集合
Set<MyDefaultWeightedEdge> minCutEdges = maxFlowImpl.getCutEdges();

获取属于最大流的边 #

最大流的边即所有流量大于0的边，你可以通过getFlowMap()方法获取所有边的流量值，过滤出流量大于0的边即可，注意要规避浮点精度判断问题：

Map<MyDefaultWeightedEdge, Double> edgeFlowMap = maxFlowImpl.getFlowMap();
Set<MyDefaultWeightedEdge> maxFlowEdges = edgeFlowMap.entrySet()
    .stream()
    // 避免浮点精度误差，不要直接判断value > 0
    .filter(entry -> entry.getValue() > 1e-9)
    .map(Map.Entry::getKey)
    .collect(Collectors.toSet());

内容的提问来源于stack exchange，提问作者Gábor Szegedi