halozatrombolas/destroy_p3.py

import numpy as np
import networkx as nx
import argparse
import time

parser = argparse.ArgumentParser(description='')
parser.add_argument('-g', '--graph', dest='graph', action='store', default=None)
args = parser.parse_args()

if not args.graph:
    print("need a graph as input")
    exit()


def read_graph(graph_file):
    with open(graph_file) as f:
        n = int(f.readline())  # pontok száma
        m = int(f.readline())  # élek száma
        A = [[0] * n for _ in range(n)]  # táblázat, ahol az élek helyén 1 van, ammeg 0
        for _ in range(m):
            [u, v] = map(int, f.readline().split())
            A[u][v] = 1
            A[v][u] = 1
    G = nx.Graph(np.array(A))
    return G


input_graph = read_graph(args.graph)


def max_comp_size(G):
    return max([len(c) for c in nx.connected_components(G)])


def run_random_once() -> list:
    del_list = []
    G = input_graph.copy()
    target = len(G.nodes) / 2
    while max_comp_size(G) > target:
        u = np.random.choice(G.nodes)
        if u not in del_list:
            del_list.append(u)
            G.remove_node(u)

    return del_list


def remove_highest_kebab() -> list:
    del_list = []
    G = input_graph.copy()
    target = len(G.nodes) / 2

    while max_comp_size(G) > target:
        highest_node = None
        highest_node_deg = 0
        for node in G.nodes:
            if G.degree[node] > highest_node_deg:
                highest_node = node
                highest_node_deg = G.degree[node]

        del_list.append(highest_node)
        G.remove_node(highest_node)

    return del_list


print(len(remove_highest_kebab()))

# target_runtime = 600
# start_time = time.time()
# results = []
# while (time.time() - start_time) < target_runtime:
#     for _ in range(50):
#         results.append(run_random_once())
#
# print("Total runs: ", len(results))
# print("Min: ", min(results))
# print("Max: ", max(results))
# print("Runtime: ", time.time() - start_time)