2-approximation

from lib import *
from random import seed
from random import randint

# seed random number generator
seed(1)

filename = "/home/monika/Documents/Studies/3/ADPTO/Lab2/graph/e5"

G = loadGraph(filename)

result = {}
V = len(G)
E = edgeList(G)
print(E)


def VC(E):
    # E to graf złożony z niepokrytych jeszcze krawędzi
    # k liczba wierzchołków, które możemy użyć
    # S to zbiór wierzchołków, który budujemy

    E1 = E.copy()
    S = set()

    while len(E1) > 0:  # and k:
        # if k == 0:
        #     return None  # nie ma rozwiązania

        index = randint(0, len(E1) - 1)
        print(f"index: {index}")
        edge = E1[index]
        # u = edge[0]
        # v = edge[1]
        # print(f"E111111111111: {E1}")
        S.add(edge[0])
        S.add(edge[1])

        # E1.remove(edge)
        # print(E1)

        # print("EDGE: " + str(edge))

        E1 = [e for e in E1 if e[0] != edge[0] and e[1] != edge[0] and e[0] != edge[1] and e[1] != edge[1]]
        # print(E1)
        # k -= 1

    return S


tries_count = 1000

# while not result:
# k += 1
best_result = G
for i in range(0, tries_count):
    result = VC(E)
    if len(result) < len(best_result):
        print(f"UUUUUUUUU, {len(result)}")
        best_result = result

print("\n\n\nZnaleziono rozwiązanie")
print(best_result)
saveSolution(filename + ".sol", best_result)