Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Matrix = [
- [0, 1, 0, 0, 0],
- [1, 0, 1, 0, 0],
- [0, 1, 0, 0, 0],
- [1, 0, 1, 0, 0],
- [1, 1, 0, 0, 0]
- ]
- def Bron_Kerbosch_Max_By_Inclusion(m):
- results = []
- def check(candidates, wrong):
- for i in wrong:
- q = True
- for j in candidates:
- if m[i][j]:
- q = False
- break
- if q: return False
- return True
- def extend(compsub, candidates, wrong):
- while candidates and check(candidates, wrong):
- v = candidates[0]
- compsub.append(v)
- new_candidates = [ i for i in candidates if not m[i][v] and i != v ]
- new_wrong = [ i for i in wrong if not m[i][v] and i != v ]
- if not new_candidates and not new_wrong:
- results.append(list(compsub))
- else:
- extend(compsub, new_candidates, new_wrong)
- candidates.remove(v)
- compsub.remove(v)
- wrong.append(v)
- extend([], list(range(len(m))), [])
- return results
- print(Bron_Kerbosch_Max_By_Inclusion(Matrix))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement