
UpperCamelCase_	:    Optional[Any]  					=       [
    ['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 		UpperCamelCase    (					_UpperCAmelCase     :      str     )      -> str:






						'''simple docstring'''

						_lowercase					:  Dict    			=      set()
						for row in edge_array:
												for item in row:
																		distinct_edge.add(item[0]     )
						return list(_SCREAMING_SNAKE_CASE     )



def 		UpperCamelCase    (					_UpperCAmelCase     :      Any   , _UpperCAmelCase     :      Optional[int]     )      -> Tuple:






						'''simple docstring'''

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



def 		UpperCamelCase    (					_UpperCAmelCase     :      List[Any]     )      -> Any:






						'''simple docstring'''

						_lowercase					:  Any    			=      get_distinct_edge(_SCREAMING_SNAKE_CASE     )
						_lowercase					:  Any    			=      {}

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



def 		UpperCamelCase    (					_UpperCAmelCase     :      Union[str, Any]     )      -> List[str]:






						'''simple docstring'''

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



def 		UpperCamelCase    (					_UpperCAmelCase     :      Dict     )      -> Optional[int]:






						'''simple docstring'''

						_lowercase					:  List[str]    			=      {}
						for key, value in nodes.items():
												_lowercase					:  Dict    			=      value
						return cluster



def 		UpperCamelCase    (					_UpperCAmelCase     :      List[Any]     )      -> Optional[Any]:






						'''simple docstring'''

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



def 		UpperCamelCase    (					)      -> Dict:






						'''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 		UpperCamelCase    (					_UpperCAmelCase     :      Tuple   , _UpperCAmelCase     :      Optional[Any]   , _UpperCAmelCase     :      List[Any]   , _UpperCAmelCase     :      int     )      -> str:






						'''simple docstring'''

						for i in cluster[ca]:
												_lowercase					:  Tuple    			=      0
												_lowercase					:  str    			=      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:
																																				_lowercase					:  List[str]    			=      [nodes[j]]
																														count += 1
																		if count == 0:
																								_lowercase					:  Union[str, Any]    			=      ca + 1
																		else:
																								break



def 		UpperCamelCase    (					_UpperCAmelCase     :      List[str]   , _UpperCAmelCase     :      Any     )      -> List[Any]:






						'''simple docstring'''

						_lowercase					:  List[Any]    			=      cluster[max(cluster.keys()     )]
						_lowercase					:  Union[str, Any]    			=      'Header'
						_lowercase					:  Optional[int]    			=      {}
						for i in x:
												if (["Header"],) in graph:
																		graph[(["Header"],)].append(x[i]     )
												else:
																		_lowercase					:  Tuple    			=      [x[i]]
						for i in x:
												_lowercase					:  Any    			=      [['Header']]
						_lowercase					:  Any    			=      1
						while i < max(_SCREAMING_SNAKE_CASE     ) - 1:
												create_edge(_SCREAMING_SNAKE_CASE   , _SCREAMING_SNAKE_CASE   , _SCREAMING_SNAKE_CASE   , _SCREAMING_SNAKE_CASE     )
												_lowercase					:  int    			=      i + 1
						return graph



def 		UpperCamelCase    (					_UpperCAmelCase     :      Tuple   , _UpperCAmelCase     :      Dict   , _UpperCAmelCase     :      Tuple   , _UpperCAmelCase     :      Optional[int]=None     )      -> Dict:






						'''simple docstring'''

						_lowercase					:  Dict    			=      (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 		UpperCamelCase    (					_UpperCAmelCase     :      int   , _UpperCAmelCase     :      Optional[Any]   , _UpperCAmelCase     :      Dict     )      -> List[Any]:






						'''simple docstring'''

						_lowercase					:  int    			=      int(s / 100 * (len(_SCREAMING_SNAKE_CASE     ) - 1)     )
						for i in cluster[k]:
												my_dfs(_SCREAMING_SNAKE_CASE   , tuple(cluster[k][i]     )   , (["Header"],)     )



def 		UpperCamelCase    (					_UpperCAmelCase     :      List[Any]     )      -> Union[str, Any]:






						'''simple docstring'''

						_lowercase					:  Optional[int]    			=      []
						for edges in paths:
												_lowercase					:  Tuple    			=      []
												for j in range(len(_SCREAMING_SNAKE_CASE     ) - 1     ):
																		_lowercase					:  Tuple    			=      list(edges[j]     )
																		for e in temp:
																								_lowercase					:  int    			=      (e[0], e[1])
																								el.append(_SCREAMING_SNAKE_CASE     )
												freq_sub_el.append(_SCREAMING_SNAKE_CASE     )
						return freq_sub_el



def 		UpperCamelCase    (					_UpperCAmelCase     :      List[str]     )      -> Optional[Any]:






						'''simple docstring'''

						for i in range(len(_SCREAMING_SNAKE_CASE     )     ):
												for j in range(len(edge_array[i]     )     ):
																		_lowercase					:  Any    			=      edge_array[i][j].split("-"     )
																		_lowercase					:  Union[str, Any]    			=      t


if __name__ == "__main__":
			preprocess(edge_array)
			UpperCamelCase_	:    int  					=       get_frequency_table(edge_array)
			UpperCamelCase_	:    int  					=       get_nodes(frequency_table)
			UpperCamelCase_	:    Tuple  					=       get_cluster(nodes)
			UpperCamelCase_	:    Any  					=       get_support(cluster)
			UpperCamelCase_	:    int  					=       construct_graph(cluster, nodes)
			find_freq_subgraph_given_support(60, cluster, graph)
			UpperCamelCase_	:    list  					=       []
			UpperCamelCase_	:    Union[str, Any]  					=       freq_subgraphs_edge_list(paths)
			print_all()






from __future__ import annotations



def 		UpperCamelCase    (					_UpperCAmelCase     :      list[int]   , _UpperCAmelCase     :      int     )      -> int:






						'''simple docstring'''

						_lowercase			,						_lowercase					:  Any    			=      0, len(_UpperCAmelCase     ) - 1
						while start_ind <= end_ind:
												if array[start_ind] == search_item:
																		return start_ind
												elif array[end_ind] == search_item:
																		return end_ind
												else:
																		start_ind += 1
																		end_ind -= 1
    # returns -1 if search_item is not found in array
						return -1


if __name__ == "__main__":
							print(double_linear_search(list(range(100)), 40))




