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)