Python code - RoIX & ESU Tree

RoIX

GitHub - benedekrozemberczki/RolX: An alternative implementation of Recursive Feature and Role Extraction (KDD11 & KDD12)GitHub

ESU Tree

def EnumerateSubgraphs(G, k):
  N = len(G)
  visited = [False] * N
  queue = []
  ans = 0
  sub = {}
  sub_graph = {}
  for i in range(N):
    queue.append([i])
  while queue:
    front = queue[0]
    queue = queue[1:]
    if len(front)==k:
      degree = [0] * N
      for f in front:
        for j in front:
          if G[f][j]==1:
            degree[f] += 1
            degree[j] += 1
      if len(set(front)) != len(front):
        continue
      if str(sorted(front)) in sub_graph:
        continue
      sub_graph[str(sorted(front))] = 1
      if str(sorted(degree)) in sub:
        sub[str(sorted(degree))] += 1 
      else:
        sub[str(sorted(degree))] = 1
      print(front)
      continue
    for i in range(N):
      if G[front[-1]][i]==1 and i > front[0]:
        queue.append(front+[i])
  for s in sub:
    ans += sub[s]
  return ans
      
  

G_adj = [[0, 0, 1, 0, 0],[0, 0, 1, 0, 0],[1, 1, 0, 1, 1],[0, 0, 1, 0, 1],[0, 0, 1, 1, 0]]
print("Start!")
ans = EnumerateSubgraphs(G_adj, k=5)
print(ans)