


__lowerCamelCase   	=  [
    ['''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      (    __UpperCamelCase			):
     a_     :  List[Any]				      =     set()
     for row in edge_array:
          for item in row:
               distinct_edge.add(item[0]			)
     return list(__UpperCamelCase			)



def 			_a      (    __UpperCamelCase	,	__UpperCamelCase			):
     a_     :  Optional[Any]				      =     ["""0"""] * len(__UpperCamelCase			)
     for i, row in enumerate(__UpperCamelCase			):
          for item in row:
               if distinct_edge in item[0]:
                    a_     :  Union[str, Any]				      =     """1"""
                    break
     return "".join(__UpperCamelCase			)



def 			_a      (    __UpperCamelCase			):
     a_     :  str				      =     get_distinct_edge(__UpperCamelCase			)
     a_     :  Dict				      =     {}

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



def 			_a      (    __UpperCamelCase			):
     a_     :  Optional[Any]				      =     {}
     for _, item in enumerate(__UpperCamelCase			):
          nodes.setdefault(item[2]	,	[]			).append(item[0]			)
     return nodes



def 			_a      (    __UpperCamelCase			):
     a_     :  Dict				      =     {}
     for key, value in nodes.items():
          a_     :  Union[str, Any]				      =     value
     return cluster



def 			_a      (    __UpperCamelCase			):
     return [i * 1_0_0 / len(__UpperCamelCase			) for i in cluster]



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



def 			_a      (    __UpperCamelCase	,	__UpperCamelCase	,	__UpperCamelCase	,	__UpperCamelCase			):
     for i in cluster[ca]:
          a_     :  Any				      =     0
          a_     :  Optional[int]				      =     ca + 1
          while ca < max(cluster.keys()			):
               for j in cluster[ca]:
                    if int(__UpperCamelCase	,	2			) & int(__UpperCamelCase	,	2			) == int(__UpperCamelCase	,	2			):
                         if tuple(nodes[i]			) in graph:
                              graph[tuple(nodes[i]			)].append(nodes[j]			)
                         else:
                              a_     :  Tuple				      =     [nodes[j]]
                         count += 1
               if count == 0:
                    a_     :  Optional[int]				      =     ca + 1
               else:
                    break



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



def 			_a      (    __UpperCamelCase	,	__UpperCamelCase	,	__UpperCamelCase	,	__UpperCamelCase=None			):
     a_     :  Optional[int]				      =     (path or []) + [start]
     if start == end:
          paths.append(__UpperCamelCase			)
     for node in graph[start]:
          if tuple(__UpperCamelCase			) not in path:
               my_dfs(__UpperCamelCase	,	tuple(__UpperCamelCase			)	,	__UpperCamelCase	,	__UpperCamelCase			)



def 			_a      (    __UpperCamelCase	,	__UpperCamelCase	,	__UpperCamelCase			):
     a_     :  List[str]				      =     int(s / 1_0_0 * (len(__UpperCamelCase			) - 1)			)
     for i in cluster[k]:
          my_dfs(__UpperCamelCase	,	tuple(cluster[k][i]			)	,	(["""Header"""],)			)



def 			_a      (    __UpperCamelCase			):
     a_     :  Union[str, Any]				      =     []
     for edges in paths:
          a_     :  Optional[Any]				      =     []
          for j in range(len(__UpperCamelCase			) - 1			):
               a_     :  Union[str, Any]				      =     list(edges[j]			)
               for e in temp:
                    a_     :  Optional[Any]				      =     (e[0], e[1])
                    el.append(__UpperCamelCase			)
          freq_sub_el.append(__UpperCamelCase			)
     return freq_sub_el



def 			_a      (    __UpperCamelCase			):
     for i in range(len(__UpperCamelCase			)			):
          for j in range(len(edge_array[i]			)			):
               a_     :  Union[str, Any]				      =     edge_array[i][j].split("""-"""			)
               a_     :  int				      =     t


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







import unittest

from transformers import SpeechaTextaConfig
from transformers.testing_utils import is_torch_available, require_torch, torch_device

from ...generation.test_utils import GenerationTesterMixin
from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
       import torch

       from transformers.models.speech_to_text_a.modeling_speech_to_text_a import (
           SpeechaTextaDecoder,
           SpeechaTextaForCausalLM,
       )


@require_torch
class 	a__						:

       def __init__( self   :  Dict   ,				lowerCamelCase_   :  Any   ,				lowerCamelCase_   :  Dict=9_9   ,				lowerCamelCase_   :  List[Any]=1_3   ,				lowerCamelCase_   :  Dict=1_6   ,				lowerCamelCase_   :  Any=7   ,				lowerCamelCase_   :  Dict=True   ,				lowerCamelCase_   :  List[str]=True   ,				lowerCamelCase_   :  Tuple=True   ,				lowerCamelCase_   :  Any=False   ,				lowerCamelCase_   :  Union[str, Any]=True   ,				lowerCamelCase_   :  int=2   ,				lowerCamelCase_   :  Tuple=3_2   ,				lowerCamelCase_   :  int=4   ,				lowerCamelCase_   :  Dict=4   ,				lowerCamelCase_   :  str=3_0   ,				lowerCamelCase_   :  Optional[int]=0   ,				lowerCamelCase_   :  Optional[Any]=1   ,				lowerCamelCase_   :  Any=2   ,				lowerCamelCase_   :  Optional[int]=None   ,				):
            a_     :  Optional[Any]				      =     parent
            a_     :  Union[str, Any]				      =     batch_size
            a_     :  Tuple				      =     decoder_seq_length
            # For common tests
            a_     :  Union[str, Any]				      =     self.decoder_seq_length
            a_     :  List[str]				      =     is_training
            a_     :  int				      =     use_attention_mask
            a_     :  Dict				      =     use_labels

            a_     :  List[str]				      =     vocab_size
            a_     :  Optional[int]				      =     d_model
            a_     :  str				      =     d_model
            a_     :  Any				      =     decoder_layers
            a_     :  Tuple				      =     decoder_layers
            a_     :  Dict				      =     decoder_ffn_dim
            a_     :  List[str]				      =     decoder_attention_heads
            a_     :  List[Any]				      =     decoder_attention_heads
            a_     :  List[str]				      =     eos_token_id
            a_     :  Any				      =     bos_token_id
            a_     :  List[Any]				      =     pad_token_id
            a_     :  Dict				      =     decoder_start_token_id
            a_     :  Tuple				      =     use_cache
            a_     :  List[Any]				      =     max_position_embeddings

            a_     :  List[str]				      =     None
            a_     :  Any				      =     decoder_seq_length
            a_     :  List[Any]				      =     2
            a_     :  Optional[Any]				      =     1

       def     UpperCAmelCase( self   :  str     ):
            a_     :  Any				      =     ids_tensor([self.batch_size, self.decoder_seq_length]   ,				self.vocab_size     )

            a_     :  Any				      =     None
            if self.use_attention_mask:
                 a_     :  Optional[Any]				      =     ids_tensor([self.batch_size, self.decoder_seq_length]   ,				vocab_size=2     )

            a_     :  Tuple				      =     None
            if self.use_labels:
                 a_     :  int				      =     ids_tensor([self.batch_size, self.decoder_seq_length]   ,				self.vocab_size     )

            a_     :  int				      =     SpeechaTextaConfig(
                vocab_size=self.vocab_size   ,				d_model=self.d_model   ,				decoder_layers=self.decoder_layers   ,				decoder_ffn_dim=self.decoder_ffn_dim   ,				decoder_attention_heads=self.decoder_attention_heads   ,				eos_token_id=self.eos_token_id   ,				bos_token_id=self.bos_token_id   ,				use_cache=self.use_cache   ,				pad_token_id=self.pad_token_id   ,				decoder_start_token_id=self.decoder_start_token_id   ,				max_position_embeddings=self.max_position_embeddings   ,				)

            return (
                config,
                input_ids,
                attention_mask,
                lm_labels,
            )

       def     UpperCAmelCase( self   :  Tuple   ,				lowerCamelCase_   :  List[str]   ,				lowerCamelCase_   :  str   ,				lowerCamelCase_   :  Optional[int]   ,				lowerCamelCase_   :  List[str]   ,				):
            a_     :  List[Any]				      =     True
            a_     :  Optional[int]				      =     SpeechaTextaDecoder(config=lowerCamelCase_     ).to(lowerCamelCase_     ).eval()
            a_     :  Optional[int]				      =     input_ids[:2]

            input_ids[input_ids == 0] += 1
            # first forward pass
            a_     :  Union[str, Any]				      =     model(lowerCamelCase_   ,				use_cache=lowerCamelCase_     )
            a_     :  Tuple				      =     model(lowerCamelCase_     )
            a_     :  str				      =     model(lowerCamelCase_   ,				use_cache=lowerCamelCase_     )

            self.parent.assertTrue(len(lowerCamelCase_     ) == len(lowerCamelCase_     )     )
            self.parent.assertTrue(len(lowerCamelCase_     ) == len(lowerCamelCase_     ) + 1     )

            a_     :  Tuple				      =     outputs["""past_key_values"""]

            # create hypothetical next token and extent to next_input_ids
            a_     :  Any				      =     ids_tensor((2, 1)   ,				config.vocab_size - 1     ) + 1

            # append to next input_ids and
            a_     :  str				      =     torch.cat([input_ids, next_tokens]   ,				dim=-1     )

            print(lowerCamelCase_     )

            a_     :  Any				      =     model(lowerCamelCase_     )["""last_hidden_state"""]
            a_     :  int				      =     model(lowerCamelCase_   ,				past_key_values=lowerCamelCase_     )["""last_hidden_state"""]

            # select random slice
            a_     :  Tuple				      =     ids_tensor((1,)   ,				output_from_past.shape[-1]     ).item()
            a_     :  List[str]				      =     output_from_no_past[:, next_input_ids.shape[-1] - 1, random_slice_idx].detach()
            a_     :  List[Any]				      =     output_from_past[:, 0, random_slice_idx].detach()

            # test that outputs are equal for slice
            assert torch.allclose(lowerCamelCase_   ,				lowerCamelCase_   ,				atol=1E-3     )

       def     UpperCAmelCase( self   :  Any     ):
            a_     :  List[Any]				      =     self.prepare_config_and_inputs()
            (
                (
                a_
            )      ,      (
                a_
            )      ,      (
                a_
            )      ,      (
                a_
            )      ,      
            )     :  Optional[int]				      =     config_and_inputs

            a_     :  Tuple				      =     {
                """input_ids""": input_ids,
                """attention_mask""": attention_mask,
            }
            return config, inputs_dict


@require_torch
class 	a__						(    lowerCAmelCase_    ,							lowerCAmelCase_    ,							lowerCAmelCase_    ,							unittest.TestCase     ):
       lowerCamelCase__:  int				     =  (SpeechaTextaDecoder, SpeechaTextaForCausalLM) if is_torch_available() else ()
       lowerCamelCase__:  int				     =  (SpeechaTextaForCausalLM,) if is_torch_available() else ()
       lowerCamelCase__:  int				     =  {"""text-generation""": SpeechaTextaForCausalLM} if is_torch_available() else {}
       lowerCamelCase__:  Dict				     =  True
       lowerCamelCase__:  List[Any]				     =  False

       def     UpperCAmelCase( self   :  List[str]   ,				):
            a_     :  Optional[int]				      =     SpeechaTextaStandaloneDecoderModelTester(self   ,				is_training=lowerCamelCase_     )
            a_     :  str				      =     ConfigTester(self   ,				config_class=lowerCamelCase_     )

       def     UpperCAmelCase( self   :  Optional[Any]     ):
            pass

       def     UpperCAmelCase( self   :  Optional[Any]     ):
            pass

       def     UpperCAmelCase( self   :  Optional[Any]     ):
            pass

       def     UpperCAmelCase( self   :  str     ):
            self.config_tester.run_common_tests()

       def     UpperCAmelCase( self   :  Dict     ):
            a_     :  int				      =     self.model_tester.prepare_config_and_inputs()
            self.model_tester.create_and_check_decoder_model_past(*lowerCamelCase_     )

       def     UpperCAmelCase( self   :  int     ):
            return



