



"""simple docstring"""
__a           =							[
    ["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   A_    (     _lowercase      ):







						'''simple docstring'''


						snake_case_					:List[str]		=     set()
						for row in edge_array:
												for item in row:
																		distinct_edge.add(item[0]      )
						return list(_lowercase      )
def   A_    (     _lowercase,   _lowercase      ):







						'''simple docstring'''


						snake_case_					:Any		=     ["""0"""] * len(_lowercase      )
						for i, row in enumerate(_lowercase      ):
												for item in row:
																		if distinct_edge in item[0]:
																								snake_case_					:List[Any]		=     """1"""
																								break
						return "".join(_lowercase      )
def   A_    (     _lowercase      ):







						'''simple docstring'''


						snake_case_					:List[Any]		=     get_distinct_edge(_lowercase      )
						snake_case_					:List[str]		=     {}

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







						'''simple docstring'''


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







						'''simple docstring'''


						snake_case_					:Union[str, Any]		=     {}
						for key, value in nodes.items():
												snake_case_					:int		=     value
						return cluster
def   A_    (     _lowercase      ):







						'''simple docstring'''


						return [i * 100 / len(_lowercase      ) for i in cluster]
def   A_    (     ):







						'''simple docstring'''


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







						'''simple docstring'''


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







						'''simple docstring'''


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







						'''simple docstring'''


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







						'''simple docstring'''


						snake_case_					:Union[str, Any]		=     int(s / 100 * (len(_lowercase      ) - 1)      )
						for i in cluster[k]:
												my_dfs(_lowercase,   tuple(cluster[k][i]      ),   (["""Header"""],)      )
def   A_    (     _lowercase      ):







						'''simple docstring'''


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







						'''simple docstring'''


						for i in range(len(_lowercase      )      ):
												for j in range(len(edge_array[i]      )      ):
																		snake_case_					:List[str]		=     edge_array[i][j].split("""-"""      )
																		snake_case_					:Optional[int]		=     t


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


'''simple docstring'''







import unittest

from cer import CER


__SCREAMING_SNAKE_CASE		:  List[str]        =      CER()
class  SCREAMING_SNAKE_CASE__       (  unittest.TestCase   ):
	def __lowerCamelCase    (				self			):



					'''simple docstring'''






					__a       :     Optional[Any]								=	["""White House"""]
					__a       :     Tuple								=	["""white house"""]
					# S = 2, D = 0, I = 0, N = 11, CER = 2 / 11
					__a       :     Any								=	cer.compute(predictions=__UpperCamelCase  ,    references=__UpperCamelCase			)
					self.assertTrue(abs(char_error_rate - 0.1_8_1_8_1_8_1_8_1_8			) < 1E-6			)
	def __lowerCamelCase    (				self			):



					'''simple docstring'''






					__a       :     Optional[int]								=	["""were wolf"""]
					__a       :     Tuple								=	["""werewolf"""]
					# S = 0, D = 0, I = 1, N = 9, CER = 1 / 9
					__a       :     Any								=	cer.compute(predictions=__UpperCamelCase  ,    references=__UpperCamelCase			)
					self.assertTrue(abs(char_error_rate - 0.1_1_1_1_1_1_1			) < 1E-6			)

					__a       :     str								=	["""werewolf"""]
					__a       :     List[Any]								=	["""weae     wolf"""]
					# S = 1, D = 1, I = 0, N = 8, CER = 0.25
					__a       :     Tuple								=	cer.compute(predictions=__UpperCamelCase  ,    references=__UpperCamelCase			)
					self.assertTrue(abs(char_error_rate - 0.2_5			) < 1E-6			)

					# consecutive whitespaces case 1
					__a       :     int								=	["""were wolf"""]
					__a       :     Dict								=	["""were               wolf"""]
					# S = 0, D = 0, I = 0, N = 9, CER = 0
					__a       :     str								=	cer.compute(predictions=__UpperCamelCase  ,    references=__UpperCamelCase			)
					self.assertTrue(abs(char_error_rate - 0.0			) < 1E-6			)

					# consecutive whitespaces case 2
					__a       :     List[str]								=	["""were   wolf"""]
					__a       :     Optional[int]								=	["""were               wolf"""]
					# S = 0, D = 0, I = 0, N = 9, CER = 0
					__a       :     Optional[Any]								=	cer.compute(predictions=__UpperCamelCase  ,    references=__UpperCamelCase			)
					self.assertTrue(abs(char_error_rate - 0.0			) < 1E-6			)
	def __lowerCamelCase    (				self			):



					'''simple docstring'''






					__a       :     Dict								=	["""werewolf"""]
					__a       :     str								=	["""weaewolf"""]
					# S = 1, D = 0, I = 0, N = 8, CER = 0.125
					__a       :     Optional[int]								=	cer.compute(predictions=__UpperCamelCase  ,    references=__UpperCamelCase			)
					self.assertTrue(abs(char_error_rate - 0.1_2_5			) < 1E-6			)
	def __lowerCamelCase    (				self			):



					'''simple docstring'''






					__a       :     List[str]								=	["""werewolf"""]
					__a       :     Tuple								=	["""wereawolf"""]
					# S = 0, D = 1, I = 0, N = 8, CER = 0.125
					__a       :     Optional[Any]								=	cer.compute(predictions=__UpperCamelCase  ,    references=__UpperCamelCase			)
					self.assertTrue(abs(char_error_rate - 0.1_2_5			) < 1E-6			)
	def __lowerCamelCase    (				self			):



					'''simple docstring'''






					__a       :     List[str]								=	["""werewolf"""]
					__a       :     Optional[Any]								=	["""wereolf"""]
					# S = 0, D = 0, I = 1, N = 8, CER = 0.125
					__a       :     int								=	cer.compute(predictions=__UpperCamelCase  ,    references=__UpperCamelCase			)
					self.assertTrue(abs(char_error_rate - 0.1_2_5			) < 1E-6			)
	def __lowerCamelCase    (				self			):



					'''simple docstring'''






					__a       :     Dict								=	["""werewolf"""]
					__a       :     Tuple								=	cer.compute(predictions=__UpperCamelCase  ,    references=__UpperCamelCase			)
					self.assertEqual(__UpperCamelCase  ,    0.0			)
	def __lowerCamelCase    (				self			):



					'''simple docstring'''






					__a       :     List[str]								=	["""werewolf""", """I am your father"""]
					__a       :     int								=	cer.compute(predictions=__UpperCamelCase  ,    references=__UpperCamelCase			)
					self.assertEqual(__UpperCamelCase  ,    0.0			)

					__a       :     Dict								=	["""werewolf""", """I am your father""", """doge"""]
					__a       :     Optional[Any]								=	["""werxwolf""", """I       am your father""", """doge"""]
					# S = 1, D = 0, I = 0, N = 28, CER = 1 / 28
					__a       :     Union[str, Any]								=	cer.compute(predictions=__UpperCamelCase  ,    references=__UpperCamelCase			)
					self.assertTrue(abs(char_error_rate - 0.0_3_5_7_1_4_2_8			) < 1E-6			)
	def __lowerCamelCase    (				self			):



					'''simple docstring'''






					__a       :     List[str]								=	["""My hovercraft""", """is full of eels"""]
					__a       :     Union[str, Any]								=	["""My hovercraft is full""", """ of eels"""]
					# S = 0, D = 0, I = 2, N = 28, CER = 2 / 28
					# whitespace at the front of " of eels" will be strip during preporcessing
					# so need to insert 2 whitespaces
					__a       :     str								=	cer.compute(predictions=__UpperCamelCase  ,    references=__UpperCamelCase  ,    concatenate_texts=__UpperCamelCase			)
					self.assertTrue(abs(char_error_rate - 0.0_7_1_4_2_8			) < 1E-6			)
	def __lowerCamelCase    (				self			):



					'''simple docstring'''






					__a       :     int								=	["""我能吞下玻璃而不伤身体"""]
					__a       :     Optional[Any]								=	[""" 能吞虾玻璃而 不霜身体啦"""]
					# S = 3, D = 2, I = 0, N = 11, CER = 5 / 11
					__a       :     List[Any]								=	cer.compute(predictions=__UpperCamelCase  ,    references=__UpperCamelCase			)
					self.assertTrue(abs(char_error_rate - 0.4_5_4_5_4_5_4_5_4_5			) < 1E-6			)

					__a       :     Union[str, Any]								=	["""我能吞下玻璃""", """而不伤身体"""]
					__a       :     Optional[Any]								=	["""我    能 吞 下 玻 璃""", """而不伤身体"""]
					# S = 0, D = 5, I = 0, N = 11, CER = 5 / 11
					__a       :     List[str]								=	cer.compute(predictions=__UpperCamelCase  ,    references=__UpperCamelCase			)
					self.assertTrue(abs(char_error_rate - 0.4_5_4_5_4_5_4_5_4_5_4_5			) < 1E-6			)

					__a       :     Union[str, Any]								=	["""我能吞下玻璃而不伤身体"""]
					__a       :     Dict								=	cer.compute(predictions=__UpperCamelCase  ,    references=__UpperCamelCase			)
					self.assertFalse(__UpperCamelCase  ,    0.0			)

	def __lowerCamelCase    (				self			):



					'''simple docstring'''






					__a       :     List[Any]								=	[""""""]
					__a       :     Dict								=	["""Hypothesis"""]
					with self.assertRaises(__UpperCamelCase			):
									cer.compute(predictions=__UpperCamelCase  ,    references=__UpperCamelCase			)


if __name__ == "__main__":
					unittest.main()