Lekcja – Wykrywanie klik Bron-Kerbosh
g = {
'D1': ['D2', 'P'],
'D2': ['D1', 'P', 'D3'],
'D3': ['D2'],
'P': ['D1', 'D2', 'K', 'Q', 'H'],
'K': ['P', 'Q', 'H'],
'Q': ['P', 'K', 'H'],
'H': ['P', 'K', 'Q']
}
def search_clicques(R, P, X, g):
if not P and not X:
print(f'Clicque: {R}')
return
P_copy = P.copy()
for person in P_copy:
neighbours = g[person]
R2 = R.copy()
R2.append(person)
P2 = [x for x in P if x in neighbours]
X2 = [x for x in X if x in neighbours]
search_clicques(R2, P2, X2, g)
P.remove(person)
X.append(person)
R = []
P = list(g.keys())
X = []
search_clicques(R, P, X, g)
Lab
karate = {
1: [2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 18, 20, 22, 32],
2: [1, 3, 4, 8, 14, 18, 20, 22, 31],
3: [1, 2, 4, 8, 9, 10, 14, 28, 29, 33],
4: [1, 2, 3, 8, 13, 14],
5: [1, 7, 11],
6: [1, 7, 11, 17],
7: [1, 5, 6, 17],
8: [1, 2, 3, 4],
9: [1, 3, 31, 33, 34],
10: [3, 34],
11: [1, 5, 6],
12: [1],
13: [1, 4],
14: [1, 2, 3, 4, 34],
17: [6, 7],
18: [1, 2],
20: [1, 2, 34],
22: [1, 2],
26: [24, 25, 32],
24: [26, 28, 30, 33, 34],
25: [26, 28, 32],
28: [3, 24, 25, 34],
29: [3, 32, 34],
30: [24, 27, 33, 34],
27: [30, 34],
31: [2, 9, 33, 34],
32: [1, 25, 26, 29, 33, 34],
33: [3, 9, 15, 16, 19, 21, 23, 24, 30, 31, 32, 34],
15: [33, 34],
16: [33, 34],
19: [33, 34],
21: [33, 34],
23: [33, 34],
34: [9, 10, 14, 15, 16, 19, 20, 21, 23, 24, 27, 28, 29, 30, 31, 32, 33]}
def search_clicques(R, P, X, g):
if not P and not X:
if len(R)>3:
print(f'Clicque: {R}')
return
P_copy = P.copy()
for person in P_copy:
neighbours = g[person]
R2 = R.copy()
R2.append(person)
P2 = [x for x in P if x in neighbours]
X2 = [x for x in X if x in neighbours]
search_clicques(R2, P2, X2, g)
P.remove(person)
X.append(person)
R = []
P = list(karate.keys())
X = []
search_clicques(R, P, X, karate)