


UpperCAmelCase			=    [
    ["""ab-e1""", """ac-e3""", """ad-e5""", """bc-e4""", """bd-e2""", """be-e6""", """bh-e12""", """cd-e2""", """ce-e4""",
     """de-e1""", """df-e8""", """dg-e5""", """dh-e10""", """ef-e3""", """eg-e2""", """fg-e6""", """gh-e6""", """hi-e3"""],
    ["""ab-e1""", """ac-e3""", """ad-e5""", """bc-e4""", """bd-e2""", """be-e6""", """cd-e2""", """de-e1""", """df-e8""",
     """ef-e3""", """eg-e2""", """fg-e6"""],
    ["""ab-e1""", """ac-e3""", """bc-e4""", """bd-e2""", """de-e1""", """df-e8""", """dg-e5""", """ef-e3""", """eg-e2""",
     """eh-e12""", """fg-e6""", """fh-e10""", """gh-e6"""],
    ["""ab-e1""", """ac-e3""", """bc-e4""", """bd-e2""", """bh-e12""", """cd-e2""", """df-e8""", """dh-e10"""],
    ["""ab-e1""", """ac-e3""", """ad-e5""", """bc-e4""", """bd-e2""", """cd-e2""", """ce-e4""", """de-e1""", """df-e8""",
     """dg-e5""", """ef-e3""", """eg-e2""", """fg-e6"""]
]






def        __lowerCAmelCase    (SCREAMING_SNAKE_CASE					)->  Dict:




      """simple docstring"""

      snake_case_       =      set()
      for row in edge_array:
            for item in row:
                  distinct_edge.add(item[0]					)
      return list(SCREAMING_SNAKE_CASE					)






def        __lowerCAmelCase    (SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE					)->  Tuple:




      """simple docstring"""

      snake_case_       =      ['''0'''] * len(SCREAMING_SNAKE_CASE					)
      for i, row in enumerate(SCREAMING_SNAKE_CASE					):
            for item in row:
                  if distinct_edge in item[0]:
                        snake_case_       =      '''1'''
                        break
      return "".join(SCREAMING_SNAKE_CASE					)






def        __lowerCAmelCase    (SCREAMING_SNAKE_CASE					)->  List[Any]:




      """simple docstring"""

      snake_case_       =      get_distinct_edge(SCREAMING_SNAKE_CASE					)
      snake_case_       =      {}

      for item in distinct_edge:
            snake_case_       =      get_bitcode(SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE					)
            # print('bit',bit)
            # bt=''.join(bit)
            snake_case_       =      bit.count('''1'''					)
            snake_case_       =      [s, bit]
      # Store [Distinct edge, WT(Bitcode), Bitcode] in descending order
      snake_case_       =      [
          [k, v[0], v[1]]
          for k, v in sorted(frequency_table.items()					,					key=lambda SCREAMING_SNAKE_CASE					: v[1][0]					,					reverse=SCREAMING_SNAKE_CASE					)
      ]
      return sorted_frequency_table






def        __lowerCAmelCase    (SCREAMING_SNAKE_CASE					)->  List[str]:




      """simple docstring"""

      snake_case_       =      {}
      for _, item in enumerate(SCREAMING_SNAKE_CASE					):
            nodes.setdefault(item[2]					,					[]					).append(item[0]					)
      return nodes






def        __lowerCAmelCase    (SCREAMING_SNAKE_CASE					)->  Any:




      """simple docstring"""

      snake_case_       =      {}
      for key, value in nodes.items():
            snake_case_       =      value
      return cluster






def        __lowerCAmelCase    (SCREAMING_SNAKE_CASE					)->  Optional[Any]:




      """simple docstring"""

      return [i * 100 / len(SCREAMING_SNAKE_CASE					) for i in cluster]






def        __lowerCAmelCase    ()->  None:




      """simple docstring"""

      print('''\nNodes\n'''					)
      for key, value in nodes.items():
            print(SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE					)
      print('''\nSupport\n'''					)
      print(SCREAMING_SNAKE_CASE					)
      print('''\n Cluster \n'''					)
      for key, value in sorted(cluster.items()					,					reverse=SCREAMING_SNAKE_CASE					):
            print(SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE					)
      print('''\n Graph\n'''					)
      for key, value in graph.items():
            print(SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE					)
      print('''\n Edge List of Frequent subgraphs \n'''					)
      for edge_list in freq_subgraph_edge_list:
            print(SCREAMING_SNAKE_CASE					)






def        __lowerCAmelCase    (SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE					)->  Optional[Any]:




      """simple docstring"""

      for i in cluster[ca]:
            snake_case_       =      0
            snake_case_       =      ca + 1
            while ca < max(cluster.keys()					):
                  for j in cluster[ca]:
                        if int(SCREAMING_SNAKE_CASE					,					2					) & int(SCREAMING_SNAKE_CASE					,					2					) == int(SCREAMING_SNAKE_CASE					,					2					):
                              if tuple(nodes[i]					) in graph:
                                    graph[tuple(nodes[i]					)].append(nodes[j]					)
                              else:
                                    snake_case_       =      [nodes[j]]
                              count += 1
                  if count == 0:
                        snake_case_       =      ca + 1
                  else:
                        break






def        __lowerCAmelCase    (SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE					)->  List[Any]:




      """simple docstring"""

      snake_case_       =      cluster[max(cluster.keys()					)]
      snake_case_       =      '''Header'''
      snake_case_       =      {}
      for i in x:
            if (["Header"],) in graph:
                  graph[(["Header"],)].append(x[i]					)
            else:
                  snake_case_       =      [x[i]]
      for i in x:
            snake_case_       =      [['''Header''']]
      snake_case_       =      1
      while i < max(SCREAMING_SNAKE_CASE					) - 1:
            create_edge(SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE					)
            snake_case_       =      i + 1
      return graph






def        __lowerCAmelCase    (SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE=None					)->  str:




      """simple docstring"""

      snake_case_       =      (path or []) + [start]
      if start == end:
            paths.append(SCREAMING_SNAKE_CASE					)
      for node in graph[start]:
            if tuple(SCREAMING_SNAKE_CASE					) not in path:
                  my_dfs(SCREAMING_SNAKE_CASE					,					tuple(SCREAMING_SNAKE_CASE					)					,					SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE					)






def        __lowerCAmelCase    (SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE					,					SCREAMING_SNAKE_CASE					)->  Union[str, Any]:




      """simple docstring"""

      snake_case_       =      int(s / 100 * (len(SCREAMING_SNAKE_CASE					) - 1)					)
      for i in cluster[k]:
            my_dfs(SCREAMING_SNAKE_CASE					,					tuple(cluster[k][i]					)					,					(['''Header'''],)					)






def        __lowerCAmelCase    (SCREAMING_SNAKE_CASE					)->  Optional[int]:




      """simple docstring"""

      snake_case_       =      []
      for edges in paths:
            snake_case_       =      []
            for j in range(len(SCREAMING_SNAKE_CASE					) - 1					):
                  snake_case_       =      list(edges[j]					)
                  for e in temp:
                        snake_case_       =      (e[0], e[1])
                        el.append(SCREAMING_SNAKE_CASE					)
            freq_sub_el.append(SCREAMING_SNAKE_CASE					)
      return freq_sub_el






def        __lowerCAmelCase    (SCREAMING_SNAKE_CASE					)->  int:




      """simple docstring"""

      for i in range(len(SCREAMING_SNAKE_CASE					)					):
            for j in range(len(edge_array[i]					)					):
                  snake_case_       =      edge_array[i][j].split('''-'''					)
                  snake_case_       =      t


if __name__ == "__main__":
   preprocess(edge_array)
   UpperCAmelCase			=    get_frequency_table(edge_array)
   UpperCAmelCase			=    get_nodes(frequency_table)
   UpperCAmelCase			=    get_cluster(nodes)
   UpperCAmelCase			=    get_support(cluster)
   UpperCAmelCase			=    construct_graph(cluster, nodes)
   find_freq_subgraph_given_support(60, cluster, graph)
   UpperCAmelCase			=    []
   UpperCAmelCase			=    freq_subgraphs_edge_list(paths)
   print_all()



class lowerCAmelCase_						:

 '''simple docstring'''

 def __init__(	self		,      _UpperCAmelCase					):
       snake_case_       =      val
       # Number of nodes in left subtree
       snake_case_       =      0
       snake_case_       =      None
       snake_case_       =      None
       snake_case_       =      None





 def 						UpperCamelCase__     (	self		,      _UpperCAmelCase					):
       assert self.left_tree_size == other.left_tree_size, "Unequal Sizes of Blocks"

       if self.val < other.val:
             snake_case_       =      self.right
             snake_case_       =      None
             if self.right:
                   snake_case_       =      other
             snake_case_       =      other
             snake_case_       =      self.left_tree_size * 2 + 1
             return self
       else:
             snake_case_       =      other.right
             snake_case_       =      None
             if other.right:
                   snake_case_       =      self
             snake_case_       =      self
             snake_case_       =      other.left_tree_size * 2 + 1
             return other







class lowerCAmelCase_						:

 '''simple docstring'''

 def __init__(	self		,      _UpperCAmelCase=None		,      _UpperCAmelCase=None		,      _UpperCAmelCase=0					):
       snake_case_       =      heap_size
       snake_case_       =      bottom_root
       snake_case_       =      min_node



 def 						UpperCamelCase__     (	self		,      _UpperCAmelCase					):

       # Empty heaps corner cases
       if other.size == 0:
             return None
       if self.size == 0:
             snake_case_       =      other.size
             snake_case_       =      other.bottom_root
             snake_case_       =      other.min_node
             return None
       # Update size
       snake_case_       =      self.size + other.size

       # Update min.node
       if self.min_node.val > other.min_node.val:
             snake_case_       =      other.min_node
       # Merge

       # Order roots by left_subtree_size
       snake_case_       =      []
       snake_case_       ,    snake_case_       =      self.bottom_root, other.bottom_root
       while i or j:
             if i and ((not j) or i.left_tree_size < j.left_tree_size):
                   combined_roots_list.append((i, True)					)
                   snake_case_       =      i.parent
             else:
                   combined_roots_list.append((j, False)					)
                   snake_case_       =      j.parent
        # Insert links between them
       for i in range(len(_UpperCAmelCase					) - 1					):
             if combined_roots_list[i][1] != combined_roots_list[i + 1][1]:
                   snake_case_       =      combined_roots_list[i + 1][0]
                   snake_case_       =      combined_roots_list[i][0]
        # Consecutively merge roots with same left_tree_size
       snake_case_       =      combined_roots_list[0][0]
       while i.parent:
             if (
                 (i.left_tree_size == i.parent.left_tree_size) and (not i.parent.parent)
             ) or (
                 i.left_tree_size == i.parent.left_tree_size
                 and i.left_tree_size != i.parent.parent.left_tree_size
             ):
                   # Neighbouring Nodes
                   snake_case_       =      i.left
                   snake_case_       =      i.parent.parent

                   # Merging trees
                   snake_case_       =      i.merge_trees(i.parent					)

                   # Updating links
                   snake_case_       =      previous_node
                   snake_case_       =      next_node
                   if previous_node:
                         snake_case_       =      i
                   if next_node:
                         snake_case_       =      i
             else:
                   snake_case_       =      i.parent
        # Updating self.bottom_root
       while i.left:
             snake_case_       =      i.left
       snake_case_       =      i

       # Update other
       snake_case_       =      self.size
       snake_case_       =      self.bottom_root
       snake_case_       =      self.min_node

       # Return the merged heap
       return self



 def 						UpperCamelCase__     (	self		,      _UpperCAmelCase					):
       if self.size == 0:
             snake_case_       =      Node(_UpperCAmelCase					)
             snake_case_       =      1
             snake_case_       =      self.bottom_root
       else:
             # Create new node
             snake_case_       =      Node(_UpperCAmelCase					)

             # Update size
             self.size += 1

             # update min_node
             if val < self.min_node.val:
                   snake_case_       =      new_node
             # Put new_node as a bottom_root in heap
             snake_case_       =      new_node
             snake_case_       =      self.bottom_root
             snake_case_       =      new_node

             # Consecutively merge roots with same left_tree_size
             while (
                 self.bottom_root.parent
                 and self.bottom_root.left_tree_size
                 == self.bottom_root.parent.left_tree_size
             ):
                   # Next node
                   snake_case_       =      self.bottom_root.parent.parent

                   # Merge
                   snake_case_       =      self.bottom_root.merge_trees(self.bottom_root.parent					)

                   # Update Links
                   snake_case_       =      next_node
                   snake_case_       =      None
                   if next_node:
                         snake_case_       =      self.bottom_root



 def 						UpperCamelCase__     (	self					):
       return self.min_node.val



 def 						UpperCamelCase__     (	self					):
       return self.size == 0



 def 						UpperCamelCase__     (	self					):
       snake_case_       =      self.min_node.val

       # Last element in heap corner case
       if self.size == 1:
             # Update size
             snake_case_       =      0

             # Update bottom root
             snake_case_       =      None

             # Update min_node
             snake_case_       =      None

             return min_value
       # No right subtree corner case
       # The structure of the tree implies that this should be the bottom root
       # and there is at least one other root
       if self.min_node.right is None:
             # Update size
             self.size -= 1

             # Update bottom root
             snake_case_       =      self.bottom_root.parent
             snake_case_       =      None

             # Update min_node
             snake_case_       =      self.bottom_root
             snake_case_       =      self.bottom_root.parent
             while i:
                   if i.val < self.min_node.val:
                         snake_case_       =      i
                   snake_case_       =      i.parent
             return min_value
       # General case
       # Find the BinomialHeap of the right subtree of min_node
       snake_case_       =      self.min_node.right
       snake_case_       =      None
       snake_case_       =      bottom_of_new
       snake_case_       =      1

       # Size, min_node and bottom_root
       while bottom_of_new.left:
             snake_case_       =      size_of_new * 2 + 1
             snake_case_       =      bottom_of_new.left
             if bottom_of_new.val < min_of_new.val:
                   snake_case_       =      bottom_of_new
        # Corner case of single root on top left path
       if (not self.min_node.left) and (not self.min_node.parent):
             snake_case_       =      size_of_new
             snake_case_       =      bottom_of_new
             snake_case_       =      min_of_new
             # print("Single root, multiple nodes case")
             return min_value
       # Remaining cases
       # Construct heap of right subtree
       snake_case_       =      BinomialHeap(
           bottom_root=_UpperCAmelCase		,      min_node=_UpperCAmelCase		,      heap_size=_UpperCAmelCase					)

       # Update size
       snake_case_       =      self.size - 1 - size_of_new

       # Neighbour nodes
       snake_case_       =      self.min_node.left
       snake_case_       =      self.min_node.parent

       # Initialize new bottom_root and min_node
       snake_case_       =      previous_node or next_node
       snake_case_       =      next_node

       # Update links of previous_node and search below for new min_node and
       # bottom_root
       if previous_node:
             snake_case_       =      next_node

             # Update bottom_root and search for min_node below
             snake_case_       =      previous_node
             snake_case_       =      previous_node
             while self.bottom_root.left:
                   snake_case_       =      self.bottom_root.left
                   if self.bottom_root.val < self.min_node.val:
                         snake_case_       =      self.bottom_root
       if next_node:
             snake_case_       =      previous_node

             # Search for new min_node above min_node
             snake_case_       =      next_node
             while i:
                   if i.val < self.min_node.val:
                         snake_case_       =      i
                   snake_case_       =      i.parent
        # Merge heaps
       self.merge_heaps(_UpperCAmelCase					)

       return min_value



 def 						UpperCamelCase__     (	self					):
       snake_case_       =      self.bottom_root
       while top_root.parent:
             snake_case_       =      top_root.parent
       # preorder
       snake_case_       =      []
       self.__traversal(_UpperCAmelCase		,      _UpperCAmelCase					)
       return heap_pre_order



 def 						UpperCamelCase__     (	self		,      _UpperCAmelCase		,      _UpperCAmelCase		,      _UpperCAmelCase=0					):
       if curr_node:
             preorder.append((curr_node.val, level)					)
             self.__traversal(curr_node.left		,      _UpperCAmelCase		,      level + 1					)
             self.__traversal(curr_node.right		,      _UpperCAmelCase		,      level + 1					)
       else:
             preorder.append(('''#''', level)					)





 def __str__(	self					):
       if self.is_empty():
             return ""
       snake_case_       =      self.pre_order()

       return "\n".join(('''-''' * level + str(_UpperCAmelCase					)) for value, level in preorder_heap					)


# Unit Tests
if __name__ == "__main__":
   import doctest

   doctest.testmod()