EWTD

3

Sep 25th, 2021
1,107
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package main
  2.  
  3. import (
  4.     "fmt"
  5.     "math/rand"
  6. )
  7.  
  8. func dfs(v,alphabet_size int, idx *int, used []bool, order, rev_order []int,transition_matrix [][]int){
  9.     used[v] = true
  10.     order[*idx] = v
  11.     rev_order[v] = *idx
  12.     for i:=0; i < alphabet_size; i++{
  13.         if !used[transition_matrix[v][i]]{
  14.             *idx += 1
  15.             dfs(transition_matrix[v][i],alphabet_size,idx,used,order,rev_order,transition_matrix)
  16.         }
  17.     }
  18. }
  19. func min_g(nodes, start_node, alphabet_size int,transition_matrix [][]int,output_matrix [][]string){
  20.     used := make([]bool,nodes)
  21.     order := make([]int,nodes)
  22.     rev_order :=  make([]int,nodes)
  23.     idx := 0
  24.     for i:=0; i < nodes; i++{
  25.         used[i]=false;order[i] = -1; rev_order[i] = -1
  26.     }
  27.     dfs(start_node,alphabet_size,&idx,used,order,rev_order,transition_matrix)
  28.     new_nodes := idx+1
  29.     start_node = rev_order[start_node]
  30.     new_transition_matrix := make([][]int,new_nodes)
  31.     new_output_matrix := make([][]string,new_nodes)
  32.     new_idx := 0
  33.     for i:= 0; i < nodes; i++{
  34.         current_node := order[i]
  35.         if current_node != -1 && used[current_node]{
  36.             new_transition_matrix[new_idx] = make([]int,alphabet_size)
  37.             new_output_matrix[new_idx] = make([]string,alphabet_size)
  38.             for j := 0; j < alphabet_size; j++{
  39.                 new_transition_matrix[new_idx][j] = rev_order[transition_matrix[current_node][j]]
  40.                 new_output_matrix[new_idx][j] = output_matrix[current_node][j]
  41.             }
  42.             new_idx++
  43.         }
  44.     }
  45.     nodes = new_nodes;transition_matrix = new_transition_matrix;output_matrix = new_output_matrix
  46. }
  47. var parents []int
  48. var classes []int
  49. func dsu_get(vertex int) int{
  50.     if vertex == parents[vertex]{
  51.         return vertex
  52.     }else{
  53.         parents[vertex] = dsu_get(parents[vertex])
  54.         return parents[vertex]
  55.     }
  56. }
  57. func dsu_unite(a, b int){
  58.     a = dsu_get(a)
  59.     b = dsu_get(b)
  60.     if rand.Int() & 1 == 1{tmp := a;a = b;b = tmp}
  61.     if a != b{parents[a] = b}
  62. }
  63. func split1(nodes, alphabet_size int, roots *int,output_matrix [][]string){
  64.     *roots = nodes
  65.     for i:=0;i < nodes; i++{parents[i] = i}
  66.     for i:=0;i < nodes; i++{
  67.         for j:=i+1;j < nodes; j++{
  68.             if dsu_get(i) != dsu_get(j){
  69.                 flag := true
  70.                 for k := 0; k < alphabet_size; k++{if output_matrix[i][k] != output_matrix[j][k]{flag = false;break}}
  71.                 if flag{dsu_unite(i,j);*roots--}
  72.             }
  73.         }
  74.     }
  75.     for i:=0; i < nodes; i++{classes[i] = dsu_get(i)}
  76. }
  77. func split2(nodes, alphabet_size int, roots *int,transition_matrix [][]int){
  78.     *roots = nodes
  79.     for i:=0; i < nodes; i++{parents[i] = i}
  80.     for i:= 0; i < nodes; i++{
  81.         for j:=i+1; j < nodes; j++{
  82.             if classes[i] == classes[j] && dsu_get(i) != dsu_get(j){
  83.                 flag := true
  84.                 for k:=0; k < alphabet_size; k++{if classes[transition_matrix[i][k]] != classes[transition_matrix[j][k]]{flag = false;break}}
  85.                 if flag{dsu_unite(i,j);*roots--}
  86.             }
  87.         }
  88.     }
  89.     for i := 0; i < nodes; i++{classes[i] = dsu_get(i)}
  90. }
  91. func main() {
  92.     var nodes, alphabet_size, start_node int
  93.     var transition_matrix [][]int
  94.     var output_matrix [][]string
  95.     fmt.Scan( &nodes, &alphabet_size, &start_node)
  96.     transition_matrix = make([][]int, nodes)
  97.     output_matrix = make([][]string, nodes)
  98.     for i := 0; i < nodes; i++ {
  99.         transition_matrix[i] = make([]int, alphabet_size)
  100.         output_matrix[i] = make([]string, alphabet_size)
  101.         for j := 0; j < alphabet_size; j++ {
  102.             fmt.Scan( &transition_matrix[i][j])
  103.         }
  104.     }
  105.     for i := 0; i < nodes; i++ {
  106.         for j := 0; j < alphabet_size; j++ {
  107.             fmt.Scan(&output_matrix[i][j])
  108.         }
  109.     }
  110.     min_g(nodes, start_node, alphabet_size,transition_matrix,output_matrix)
  111.     classes = make([]int,nodes)
  112.     parents = make([]int, nodes)
  113.     roots := 0
  114.     new_roots := 0
  115.     split1(nodes, alphabet_size, &roots, output_matrix)
  116.     for true{
  117.         split2(nodes, alphabet_size, &new_roots, transition_matrix)
  118.         if roots == new_roots{break}
  119.         roots = new_roots
  120.     }
  121.     compressed_classes := make(map[int]int)
  122.     idx := 0
  123.     for i:=0;i < new_roots; i++{
  124.         if _, ok := compressed_classes[classes[idx]]; !ok{compressed_classes[classes[idx]] = i}
  125.         for idx < nodes{if _,ok := compressed_classes[classes[idx]]; ok{idx++}else{break}}
  126.     }
  127.     for i:=0; i < nodes; i++{classes[i] = compressed_classes[classes[i]]}
  128.     used_classes := make([]bool,new_roots)
  129.     new_transition_matrix := make([][]int,new_roots)
  130.     new_output_matrix := make([][]string,new_roots)
  131.     for i:= 0; i < new_roots; i++{
  132.         used_classes[i] = false
  133.         new_transition_matrix[i] = make([]int,alphabet_size)
  134.         new_output_matrix[i] = make([]string,alphabet_size)
  135.     }
  136.     for i:=0;i < nodes; i++{
  137.         if !used_classes[classes[i]]{
  138.             used_classes[classes[i]] = true
  139.             for j:=0; j < alphabet_size; j++{
  140.                 new_output_matrix[classes[i]][j] = output_matrix[i][j]
  141.                 new_transition_matrix[classes[i]][j] = classes[transition_matrix[i][j]]
  142.             }
  143.         }
  144.     }
  145.     nodes = new_roots
  146.     transition_matrix = new_transition_matrix
  147.     output_matrix = new_output_matrix
  148.     min_g(nodes, start_node, alphabet_size,transition_matrix,output_matrix)
  149.     fmt.Print("digraph {\n\trankdir = LR\n\tdummy [label = \"\", shape = none]\n")
  150.     for i := 0; i < nodes; i++ {
  151.         fmt.Printf( "\t%d [shape = circle]\n", i)
  152.     }
  153.     fmt.Printf("\tdummy -> %d\n", start_node)
  154.     for i := 0; i < nodes; i++ {
  155.         for j := 0; j < alphabet_size; j++ {
  156.             fmt.Printf("\t%d -> %d [label = \"%s(%s)\"]\n", i, transition_matrix[i][j], (string)(rune('a'+j)), output_matrix[i][j])
  157.         }
  158.     }
  159.     fmt.Print("}")
  160.  
  161. }
RAW Paste Data