Advertisement
Guest User

Untitled

a guest
Oct 22nd, 2017
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.12 KB | None | 0 0
  1. Matrix = [
  2.     [0, 1, 0, 0, 0],
  3.     [1, 0, 1, 0, 0],
  4.     [0, 1, 0, 0, 0],
  5.     [1, 0, 1, 0, 0],
  6.     [1, 1, 0, 0, 0]
  7. ]
  8.  
  9. def Bron_Kerbosch_Max_By_Inclusion(m):
  10.  
  11.     results = []
  12.  
  13.     def check(candidates, wrong):
  14.         for i in wrong:
  15.             q = True
  16.             for j in candidates:
  17.                 if m[i][j]:
  18.                     q = False
  19.                     break
  20.             if q: return False
  21.         return True
  22.  
  23.     def extend(compsub, candidates, wrong):
  24.  
  25.         while candidates and check(candidates, wrong):
  26.  
  27.             v = candidates[0]
  28.             compsub.append(v)
  29.  
  30.             new_candidates = [ i for i in candidates if not m[i][v] and i != v ]
  31.             new_wrong = [ i for i in wrong if not m[i][v] and i != v ]
  32.  
  33.             if not new_candidates and not new_wrong:
  34.                 results.append(list(compsub))
  35.             else:
  36.                 extend(compsub, new_candidates, new_wrong)
  37.  
  38.             candidates.remove(v)
  39.             compsub.remove(v)
  40.             wrong.append(v)
  41.  
  42.     extend([], list(range(len(m))), [])
  43.  
  44.     return results
  45.  
  46. print(Bron_Kerbosch_Max_By_Inclusion(Matrix))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement