NetworkX下实现图中全部最小s-t节点割枚举查找

NetworkX 内置的 minimum_st_node_cut() 接口仅会返回任意一个符合规模要求的最小s-t节点割集，不支持直接枚举全部合法割集，可基于流网络转换+残量闭包枚举的方式完成全量枚举，具体方法如下：

核心实现逻辑 #

• 确定最小割规模阈值：单次调用 minimum_st_node_cut(G, s, t) 获取返回集合的长度值，记为k，所有满足最小s-t节点割定义的集合大小必然等于k，这是后续所有枚举的判断基准。
• 图结构转换：将原始节点图转换为带容量的流网络，适配节点割的计算规则：
  • 对每个非s、非t的节点v，拆为v_in和v_out两个节点，二者之间连一条容量为1的有向边，对应“删除该节点付出1单位代价”的规则。
  • 图中原有的所有边，连接到对应节点的拆分侧（原入边连入v_in，原出边从v_out引出），容量设为大于节点总数的极大值，保证这类边不会被纳入最小割集。
  • s和t节点同样做拆分，但二者拆分侧之间的边容量设为极大值，避免s、t本身被纳入割集。
• 残量网络生成：在转换后的流网络上计算s到t的最大流，计算完成后导出残量网络，保留所有边权剩余值大于0的边构成子图。
• 全量割集枚举：枚举残量网络中所有满足以下条件的闭包集合S：
  • s的拆分出口属于集合S。
  • t的拆分入口不属于集合S。
  • 若集合内存在节点u，且残量网络中u到v的边剩余权值大于0，则v也必须属于S。
    每个合法的闭包S对应一个唯一的最小s-t节点割：只要某节点v满足v_in在S内、v_out不在S内，就将v纳入当前割集。
• 去重处理：所有枚举得到的割集排序后转为不可变元组存入集合，避免因枚举顺序不同导致的重复统计。

简化参考实现 #

import networkx as nx

def get_all_min_st_node_cuts(G, s, t):
    # 基础入参校验
    if G.has_edge(s, t) or G.has_edge(t, s):
        raise ValueError("s和t不能直接相连，不符合节点割的计算前置要求")
    
    # 获取最小割规模阈值
    min_cut_size = len(nx.minimum_st_node_cut(G, s, t))
    node_num = len(G.nodes())
    INF = node_num + 1  # 定义极大容量值

    # 构造拆点后的流网络
    flow_net = nx.DiGraph()
    node_mapping = {}
    # 拆分所有节点
    for v in G.nodes():
        in_node = f"{v}_in"
        out_node = f"{v}_out"
        node_mapping[v] = (in_node, out_node)
        # s和t的拆点边容量设为INF，其余设为1
        cap = INF if v in (s, t) else 1
        flow_net.add_edge(in_node, out_node, capacity=cap)
    
    # 把原图的边映射到拆点后的网络上
    for u, v in G.edges():
        u_out = node_mapping[u][1]
        v_in = node_mapping[v][0]
        flow_net.add_edge(u_out, v_in, capacity=INF)
    
    # 计算最大流，得到残量网络
    source = node_mapping[s][1]
    sink = node_mapping[t][0]
    max_flow_val, flow_dict = nx.maximum_flow(flow_net, source, sink)
    # 构建残量网络
    residual_net = nx.DiGraph()
    for u in flow_net.nodes():
        for v, cap in flow_net[u].items():
            remain = cap['capacity'] - flow_dict[u][v]
            if remain > 0:
                residual_net.add_edge(u, v)
    
    # 枚举残量网络的合法闭包，提取对应割集
    all_cuts = set()
    visited = set()
    def dfs(current, subset):
        subset_key = tuple(sorted(subset))
        if subset_key in visited:
            return
        visited.add(subset_key)
        # 检查subset是否为合法闭包：只要sink不在集合内，就对应一个候选割
        if sink not in subset:
            cut = []
            for orig_v, (in_v, out_v) in node_mapping.items():
                if in_v in subset and out_v not in subset:
                    cut.append(orig_v)
            if len(cut) == min_cut_size:
                cut_tuple = tuple(sorted(cut))
                all_cuts.add(cut_tuple)
        # 递归遍历邻接节点，拓展闭包
        for neighbor in residual_net.neighbors(current):
            new_subset = subset.copy()
            new_subset.add(neighbor)
            dfs(neighbor, new_subset)
    
    dfs(source, {source})
    # 转换为集合格式返回
    return [set(cut) for cut in all_cuts]

关键注意事项 #

• 不要反复在原始图上直接调用minimum_st_node_cut()尝试枚举所有割集，该函数没有内置的记忆化逻辑，每次调用只会返回计算过程中第一个匹配到的割集，无法拿到其他同规模的合法割集。
• 枚举效率和图本身的最小割数量直接相关，最坏情况下图的最小割数量会达到指数级，节点数超过100的稠密图不建议开展全量枚举。
• 构造流网络时的极大容量值必须大于图的总节点数，否则可能把原图的连通边错误纳入割集，导致计算结果偏差。

内容的提问来源于stack exchange，提问作者Estèfano Viteri