Σε αυτό το μάθημα υλοποιήσαμε τον αλγόριθμο εύρεσης (προσέγγισης) του πλήθους των συνεκτικών συνιστωσών ενός γραφήματος.
Κάναμε κάποιες τροποποιήσεις στον αλγόριθμο κυρίως επειδή το μέγεθος του γραφήματος δεν είναι αρκετά μεγάλο. Οι τροποποιήσεις αυτές φαίνονται στα σχόλια παρακάτω.
Το γράφημα στο οποίο δοκιμάζουμε τον αλγόριθμό μας είναι ένα γράφημα που αποτελείται από $m$ κύκλους, ο καθένας από τους οποίους έχει τυχαίο μήκος (ανάμεσα στις δύο παραμέτρους small και large που φαίνονται στον κώδικα παρακάτω). Το πλήθος των συνεκτικών συνιστωσών είναι λοιπόν $m$. Δε χρησιμοποιούμε τις παραμέτρους $\epsilon$ (ακρίβειας) και $\delta$ (βεβαιότητας) γιατί τα νούμερα είναι πολύ μικρά για να κάνουν διαφορά, αλλά διαλέγουμε "με το χέρι" τις παραμέτρους $k$ (πλήθος τυχαίων κορυφών που εξετάζουμε) και cutoff αντί για την τιμή $2/\epsilon$ που προβλέπει ο αλγόριθμος.
import math
import numpy as np
adj = [] # Λίστες συνεδσμολογίας, μια λίστα για κάθε κορυφή
m = 10000 # Αριθμός κύκλων του γραφήματος
small = 10; large = 200 # ελάχιστο και μέγιστο μέγεθος κύκλου - επιλέγεται τυχαία
n = 0 # Τρέχον πλήθος κορυφών. Αυξάνει ανάλογα κάθε φορά που προσθέτουμε στο γράφημα ένα κύκλο τυχαίου μήκους
for i in range(m): # Δημιουργία m κύκλων με τυχαίο μήκος από small έως large
L = np.random.randint(small, large+1) # μήκος κύκλου
adj += L*[[]] # Προσθέτουμε τις λίστες συνδεσμολογίας για τις κορυφές του κύκλου αυτού
for j in range(L):
adj[n+j] = [n+(j+1)%L, n+(j-1)%L] # Κάθε κορυφή n+j συνδέεται με την μπροστά από αυτήν και πίσω από αυτήν
n += L # Αυξάνουμε το συνολικό πλήθος κορυφών του γραφήματος κατά το μήκος του κύκλου αυτού.
# Κανονικά θα έπρεπε να χρησιμοποιήσουμε τις παρακάτω παραμέτρους ακρίβειας (ε) και βεβαιότητας (δ) αλλά δεν
# το κάνουμε γιατί για ένα τόσο μικρό γράφημα δεν έχουν πολύ νόημα.
#epsilon = 1e-3
#delta = 0.1
# cutoff = 2/epsilon
# Από ποιο μέγεθος και πέρα "κόβουμε" το μέγεθος της συνεκτικής συνιστώσας.
cutoff = 120 # Αντί να πάρουμε το cutoff μέσω του ε το διαλέγουμε αυθαίρετα.
# Το πόσες τυχαίες κορυφές πρέπει να πάρουμε.
#Το διαλέγουμε αυθαίρετα αντί αυτού.
#k = (int)(2/epsilon**2*math.log(2/delta))
k = 100 # Παίρνουμε k τυχαίες κορυφές από το γράφημά μας
# Επιλέγουμε τις k τυχαίες κορυφές
v = []
for i in range(k):
v.append(np.random.randint(n))
def component(v): # Υπολογισμός της συνεκτικής συνιστώσας της κορυφής v (breadth first search)
# Δε χρησιμοποιείται παρακάτω, αλλά η επόμενη συνάρτηση είναι τροποποίηση αυτής
"""
Επιστρέφει μια λίστα με κορυφές (η v ανάμεσά τους) που απαρτίζουν τη συνεκτική συνιστώσα της v
"""
L = [v]
lastadded = [v]
while True:
new = []
for x in lastadded:
for y in adj[x]:
if y not in L and y not in new:
new.append(y)
if new == []:
break
L = L + new
lastadded = new[:]
continue
return L
def svprime(v, top):
"""
Επιστρέφει το μέγεθος της συνεκτικής συνιστώσας του v
αν αυτό είναι <= top, αλλιώς επιστρέφει top
"""
L = [v]
lastadded = [v]
S = 1
while True:
new = []
for x in lastadded:
for y in adj[x]:
if y not in L and y not in new:
new.append(y)
if S<top:
L.append(y)
S += 1
if S >= top:
return top
if new == []:
break
lastadded = new[:]
continue
return len(L)
result = 0
for i in range(k): # για κάθε μία από τις τυχαίες κορυφές
svp = svprime(v[i], cutoff) # υπολογίζουμε το τροποποιημένο μέγεθος της συνιστώσας του
print(svp, end=' ') # το τυπώνουμε
result += 1/svp # η συνεισφορά της κορυφής αυτής στο άθροισμα
result *= n/k
print("\n", "Αριθμός κύκλων", m, "αριθμός κορυφών", n, "προσέγγιση", result)