47. Graph Cuts

import matplotlib.pyplot as plt
import networkx as nx
import numpy as np

nx_draw_style = dict(node_color="tab:red", font_size=16, font_color="whitesmoke")

seed = 42

47.1. Generate a Graph

G_bb = nx.barbell_graph(3, 0)

pos = nx.spring_layout(G_bb, seed=seed)  # Seed for reproducible layout
nx.draw(G_bb, pos=pos, with_labels = True, **nx_draw_style)
plt.show()

def ratio_cut_size(G, S, T=None, weight=None):

    if T is None:
        T = set(G) - set(S)
    num_cut_edges = nx.cut_size(G, S, T=T, weight=weight)
    norm_S = len(S)
    norm_T = len(T)
    return num_cut_edges * ((1 / norm_S) + (1 / norm_T))


def compare_cuts(graph, partition):

    return {
        "cut": nx.cut_size(graph, partition[1], partition[2]),
        "ncut": nx.normalized_cut_size(graph, partition[1], partition[2]),
        "ratio_cut": ratio_cut_size(graph, partition[1], partition[2])
    }

partition_bb_1 = {
    1: {0, 1, 2},
    2: {3, 4, 5}
}

partition_bb_2 = {
    1: {0, 1, 2, 3},
    2: {4, 5}
}

compare_cuts(
    G_bb, partition_bb_1
), compare_cuts(
    G_bb, partition_bb_2
)

({'cut': 1, 'ncut': 0.2857142857142857, 'ratio_cut': 0.6666666666666666},
 {'cut': 2, 'ncut': 0.7, 'ratio_cut': 1.5})

Created in Deepnote