


"""simple docstring"""



lowercase_							 =       [
    ['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    (					_lowercase   :      str  )	->   List[str]:


	"""simple docstring"""




	lowerCAmelCase_			       = set()
	for row in edge_array:
		for item in row:
			distinct_edge.add(item[0]  )
	return list(_SCREAMING_SNAKE_CASE  )
def     UpperCAmelCase    (					_lowercase   :      Any ,      _lowercase   :      Optional[int]  )	->   List[Any]:


	"""simple docstring"""




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


	"""simple docstring"""




	lowerCAmelCase_			       = get_distinct_edge(_SCREAMING_SNAKE_CASE  )
	lowerCAmelCase_			       = {}

	for item in distinct_edge:
		lowerCAmelCase_			       = get_bitcode(_SCREAMING_SNAKE_CASE ,      _SCREAMING_SNAKE_CASE  )
		# print('bit',bit)
		# bt=''.join(bit)
		lowerCAmelCase_			       = bit.count('''1'''  )
		lowerCAmelCase_			       = [s, bit]
	# Store [Distinct edge, WT(Bitcode), Bitcode] in descending order
	lowerCAmelCase_			       = [
	    [k, v[0], v[1]]
	    for k, v in sorted(frequency_table.items() ,      key=lambda _lowercase  : v[1][0] ,      reverse=_SCREAMING_SNAKE_CASE  )
	]
	return sorted_frequency_table
def     UpperCAmelCase    (					_lowercase   :      Union[str, Any]  )	->   Optional[int]:


	"""simple docstring"""




	lowerCAmelCase_			       = {}
	for _, item in enumerate(_SCREAMING_SNAKE_CASE  ):
		nodes.setdefault(item[2] ,      []  ).append(item[0]  )
	return nodes
def     UpperCAmelCase    (					_lowercase   :      Dict  )	->   Tuple:


	"""simple docstring"""




	lowerCAmelCase_			       = {}
	for key, value in nodes.items():
		lowerCAmelCase_			       = value
	return cluster
def     UpperCAmelCase    (					_lowercase   :      List[Any]  )	->   str:


	"""simple docstring"""




	return [i * 1_0_0 / len(_SCREAMING_SNAKE_CASE  ) for i in cluster]
def     UpperCAmelCase    (					)	->   List[Any]:


	"""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    (					_lowercase   :      Tuple ,      _lowercase   :      Optional[Any] ,      _lowercase   :      List[Any] ,      _lowercase   :      int  )	->   Tuple:


	"""simple docstring"""




	for i in cluster[ca]:
		lowerCAmelCase_			       = 0
		lowerCAmelCase_			       = 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:
						lowerCAmelCase_			       = [nodes[j]]
					count += 1
			if count == 0:
				lowerCAmelCase_			       = ca + 1
			else:
				break
def     UpperCAmelCase    (					_lowercase   :      List[str] ,      _lowercase   :      Any  )	->   Optional[Any]:


	"""simple docstring"""




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


	"""simple docstring"""




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


	"""simple docstring"""




	lowerCAmelCase_			       = int(s / 1_0_0 * (len(_SCREAMING_SNAKE_CASE  ) - 1)  )
	for i in cluster[k]:
		my_dfs(_SCREAMING_SNAKE_CASE ,      tuple(cluster[k][i]  ) ,      (['''Header'''],)  )
def     UpperCAmelCase    (					_lowercase   :      List[Any]  )	->   Optional[int]:


	"""simple docstring"""




	lowerCAmelCase_			       = []
	for edges in paths:
		lowerCAmelCase_			       = []
		for j in range(len(_SCREAMING_SNAKE_CASE  ) - 1  ):
			lowerCAmelCase_			       = list(edges[j]  )
			for e in temp:
				lowerCAmelCase_			       = (e[0], e[1])
				el.append(_SCREAMING_SNAKE_CASE  )
		freq_sub_el.append(_SCREAMING_SNAKE_CASE  )
	return freq_sub_el
def     UpperCAmelCase    (					_lowercase   :      List[str]  )	->   Union[str, Any]:


	"""simple docstring"""




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


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



"""simple docstring"""



def     UpperCAmelCase    (					_lowercase   :      list[int]  )	->   int:


	"""simple docstring"""




	lowerCAmelCase_			       = len(_lowercase  )
	if n in (0, 1):
		return 0
	return sum(query * (n - i - 1) for i, query in enumerate(sorted(_lowercase  )  )  )


if __name__ == "__main__":
		import doctest

		doctest.testmod()