用 Python 解决最大权闭合子图问题

import networkx as nx
import numpy as np
def max_weight_closure_subgraph(G):
    s = 'source'
    t = 'target'
    # Step 1: Create a copy of G and add source and target nodes
    G_copy = G.copy()
    G_copy.add_node(s)
    G_copy.add_node(t)
    # Step 2: Add edges from source to each node in G with its weight as capacity
    for node in G.nodes:
        weight = G.nodes[node]['weight']
        G_copy.add_edge(s, node, capacity=weight)
    # Step 3: Add edges from each node in G to target with its weight as capacity
    for node in G.nodes:
        weight = G.nodes[node]['weight']
        G_copy.add_edge(node, t, capacity=weight)
    # Step 4: Create a matrix of node weights (w) and edge capacities (c)
    w = np.array([G.nodes[node]['weight'] for node in G.nodes])
    c = np.array([[G_copy.edges[u, v]['capacity'] for v in G_copy.nodes] for u in G_copy.nodes])
    # Step 5: Solve the minimum cut problem by finding the maximum flow
    flow_value, flow_dict = nx.maximum_flow(G_copy, s, t)
    # Step 6: Determine which nodes belong to the closure subgraph
    nodes_closure = [node for node in flow_dict if flow_dict[node] > 0 and node != s and node != t]
    nodes_nonclosure = [node for node in G.nodes if node not in nodes_closure]
    # Step 7: Calculate the total weight of the closure subgraph
    weight_closure = w[nodes_closure].sum()
    # Step 8: Create a new graph for the closure subgraph
    G_closure = nx.DiGraph()
    G_closure.add_nodes_from(nodes_closure)
    # Step 9: Add edges from closure nodes to other closure nodes
    for u in nodes_closure:
        for v in nodes_closure:
            if u != v and G.has_edge(u, v):
                G_closure.add_edge(u, v)
    return G_closure, weight_closure