G2A Many GEOs
SHARE
TWEET

2-approximation

a guest Apr 6th, 2020 132 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from lib import *
  2. from random import seed
  3. from random import randint
  4.  
  5. # seed random number generator
  6. seed(1)
  7.  
  8. filename = "/home/monika/Documents/Studies/3/ADPTO/Lab2/graph/e5"
  9.  
  10. G = loadGraph(filename)
  11.  
  12. result = {}
  13. V = len(G)
  14. E = edgeList(G)
  15. print(E)
  16.  
  17.  
  18. def VC(E):
  19.     # E to graf złożony z niepokrytych jeszcze krawędzi
  20.     # k liczba wierzchołków, które możemy użyć
  21.     # S to zbiór wierzchołków, który budujemy
  22.  
  23.     E1 = E.copy()
  24.     S = set()
  25.  
  26.     while len(E1) > 0:  # and k:
  27.         # if k == 0:
  28.         #     return None  # nie ma rozwiązania
  29.  
  30.         index = randint(0, len(E1) - 1)
  31.         print(f"index: {index}")
  32.         edge = E1[index]
  33.         # u = edge[0]
  34.         # v = edge[1]
  35.         # print(f"E111111111111: {E1}")
  36.         S.add(edge[0])
  37.         S.add(edge[1])
  38.  
  39.         # E1.remove(edge)
  40.         # print(E1)
  41.  
  42.         # print("EDGE: " + str(edge))
  43.  
  44.         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]]
  45.         # print(E1)
  46.         # k -= 1
  47.  
  48.     return S
  49.  
  50.  
  51. tries_count = 1000
  52.  
  53. # while not result:
  54. # k += 1
  55. best_result = G
  56. for i in range(0, tries_count):
  57.     result = VC(E)
  58.     if len(result) < len(best_result):
  59.         print(f"UUUUUUUUU, {len(result)}")
  60.         best_result = result
  61.  
  62. print("\n\n\nZnaleziono rozwiązanie")
  63. print(best_result)
  64. saveSolution(filename + ".sol", best_result)
RAW Paste Data
Ledger Nano X - The secure hardware wallet
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top