Разбить график на два больших подграфа в зависимости от веса узла

Question

Учитывая эту сеть, которая в основном является радиальной сетью с весами на каждом узле:

G = nx.Graph()
G.add_node(0, weight=10)
G.add_node(1, weight=5)
G.add_node(2, weight=7)
G.add_node(3, weight=8)
G.add_node(4, weight=13)
G.add_edge(0,1)
G.add_edge(1,2)
G.add_edge(1,3)
G.add_edge(3,4)

Я пытаюсь разбить граф G на два самых больших подграфа, где размер определяется весами узлов. Разделение устранит ребро (1,3) и создаст два подграфа с узлами [0,1,2] и [3,4].

Любая помощь приветствуется!

Answer 1

edges = list(G.edges())
weights = list(G.nodes(data='weight'))
node_weights = []
for i in weights:
    node_weights.append(i[1])

con_comp = []
edge_split = []

for i in edges:

    G.remove_edge(i[0],i[1])
    edge_split.append((i[0],i[1]))
    a = list(nx.connected_component_subgraphs(G))

    b = list(a[0].nodes())
    bw = []
    for j in b:
        bw.append(node_weights[j])
    c = list(a[1].nodes())
    cw = []
    for j in c:
        cw.append(node_weights[j])

    sum_b = sum(bw)
    sum_c = sum(cw)
    con_comp.append((sum_b, sum_c))

    G.add_edge(i[0],i[1])

diff = []

for i in con_comp:
    diff.append(abs(i[0]-i[1]))

val = min(diff)
ind = diff.index(val)

remove = edges[ind]