import numpy as np
import copy # για τη συνάρτηση deepcopy που αντιγράφει πλήρως λεξικά (dictionaries)
def findcut(V):
"""
Για το γράφημα που περιγράφεται από το λεξικό V (τα κλειδιά είναι τα ονόματα των κορυφών, που
αρχικά είναι απλά αριθμοί σε μορφή string και οι τιμές σε κάθε κλειδί είναι οι γειτονικές κορυφές)
η συνάρτηση αυτή τρέχει τον randomized αλγόριθμό μας και επιστρέφει μια διαμέριση του συνόλου των κορυφών
σε δύο ομάδες και το μέγεθος του cut που αντιστοιχεί στη διαμέριση αυτή. Από την ανάλυση του αλγορίθμου
αυτού ξέρουμε ότι έχει πιθανότητα τουλάχιστον 1/(2*n*(n-1)) να βρει ένα minimum cut. Η πιθανότητα αυτή
αρκετά μικρή, οπότε αυτό που κάνουμε είναι ότι τρέχουμε πολλές φορές τον αλγόριθμο αυτό και κρατάμε το
ελάχιστο cut που θε βρει.
"""
W = copy.deepcopy(V) # φτιάχνουμε ένα αντίγραφο του γραφήματος
# το οποίο θα αλλάζει κατά τη διάρκεια του αλγορίθμου
# Θα κάνουμε συνολικά n-2 συμπτύξεις (contractions) ακμών, αφού θέλουμε να μείνουν 2 κορυφές στο
# τέλος και σε κάθε σύμπτυξη φεύγει μια κορυφή.
for i in range(n-2):
EE = [] # λίστα με όλες τις ακμές μέσα, μια φορά την κάθε μια
for j in W.keys():
for v in W[j]:
if [v, j] not in EE: # δεν προσθέτουμε την ακμή στην ΕΕ αν έχει ήδη μπει με την ανάποδη
# σειρά κορυφών
EE.append([j, v])
E = len(EE) # E είναι ο αριθμός των ακμών
e = np.random.randint(0, E) # τυχαία ακμή
u = EE[e][0] # αρχική κορυφή της e
v = EE[e][1] # τελική κορυφή της e
Euv = [] # Ποιες ακμές συνδέονται με τις u ή v πριν τη σύμπτυξη
for x in W[u]:
if x != v: Euv.append([u, x])
for x in W[v]:
if x != u: Euv.append([v, x])
del W[u] # διαγραφή της u
del W[v] # διαγραφή της v
uv = u+"-"+v # όνομα της νέας super κορυφής
W[uv] = [] # εδώ φτιάχνουμε τη λίστα κορυφών που συνδέονται με τη νέα super κορυφή uv
for edge in Euv:
if edge[0]==u or edge[0]==v: W[uv].append(edge[1])
else: W[uv].append(edge[0])
for z in W.keys(): # γυρνάμε τις άλλες ακμές προς u ή v να δείχνουν στην uv
if z==uv: continue
for t in range(len(W[z])):
if W[z][t] == u or W[z][t] == v:
W[z][t] = uv
if len(W.keys()) != 2: # Στο τέλος της διαδικασίας θα πρέπει να έχουμε μείνει με δύο κορυφές μόνο
print("Error - 1")
VV = list(W.keys())
a = VV[0]; b = VV[1] # a, b είναι τα ονόματα των δύο super κορυφών που απέμειναν
La = a.split("-") # La, Lb είναι οι κορυφές του αρχικού γραφήματος που ανήκουν στις δύο ομάδες
Lb = b.split("-")
cut = 0 # εδώ μετράμε πόσο μεγάλο είναι το cut για αυτή τη διαμέριση
for u in La:
for v in V[u]:
if v in Lb: cut += 1
return cut, La, Lb
V = {} # λεξικό που θα έχει τα ονόματα των κορυφών ως κλειδιά και για κάθε κορυφή
# θα έχει σε μια λίστα τους γείτονές της
# Αυτό θα είναι το γράφημα με το οποίο θα δουλέψουμε αρχικά
V = { '0': ['1', '3', '4', '4'],
'1': ['0', '2', '3', '4'],
'2': ['1', '3', '4'],
'3': ['0', '1', '2', '4'],
'4': ['0', '0', '1', '3', '2']
}
n = len(V.keys()) # πλήθος κορυφών
N = n**2 # Πόσες φορές θα τρέξουμε τον αλγόριθμο
cut = 100*n**2 # εδώ θέλουμε ένα αριθμό που είναι σίγουρα μεγαλύτερος από το minimum cut
la = []
lb = []
for i in range(N):
c, La, Lb = findcut(V)
if c < cut: # βρήκαμε καλύτερο cut: το κρατάμε (και το μέγεθός του αλλά και τη διαμέρισή του)
cut = c; la = La.copy(); lb = Lb.copy()
print(f"Το ελάχιστο cut που βρήκαμε έχει μέγεθος {cut}\nκαι αντιστοιχεί στη διαμέριση κορυφών\n {la}\n {lb}")