daily pastebin goal
11%
SHARE
TWEET

Untitled

a guest Jun 3rd, 2018 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package main
  2.  
  3. import "fmt"
  4.  
  5. //var nn1, nn2 int
  6. type Graph struct {
  7.     state, newState, depth, i int
  8.     inputAlphabet, mark, newInputAlphabet string
  9.     parent *Graph
  10. }
  11.  
  12. //Поиск набора parent
  13. func Find(x *Graph) *Graph {
  14.     if x.parent == x {
  15.         return x
  16.     }
  17.     x.parent = Find(x.parent)
  18.     return x.parent
  19. }
  20.  
  21. //Объединения
  22. func Union(x, y *Graph) {
  23.     rootX := Find(x)
  24.     rootY := Find(y)
  25.     if rootX.depth < rootY.depth {
  26.         rootY.parent = rootY
  27.     } else {
  28.         rootY.parent = rootX
  29.         if rootX.depth == rootY.depth && rootX != rootY {
  30.             rootX.depth++
  31.         }
  32.     }
  33. }
  34.  
  35. func Split1(phi [][] Graph, n, X, q int) (int, []int) {
  36.     var m, x, q1, q2 int
  37.     var eq bool
  38.     var Q = make([] Graph, n)
  39.     m = n
  40.     q, q1 = 0, 0
  41.     for q < n {
  42.         Q[q].i = q
  43.         Q[q].parent = &Q[q]
  44.         Q[q].depth = 0
  45.         q++
  46.     }
  47.     for q1 < n {
  48.         q2 = 0
  49.         for q2 < n {
  50.             if Find(&Q[q1]) != Find(&Q[q2]) {
  51.                 eq = true
  52.                 x = 0
  53.                 for x < X {
  54.                     if phi[q1][x].inputAlphabet != phi[q2][x].inputAlphabet {
  55.                         eq = false
  56.                         break
  57.                     }
  58.                     x++
  59.                 }
  60.                 if eq {
  61.                     Union(&Q[q1], &Q[q2])
  62.                     m = m - 1
  63.                 }
  64.             }
  65.             q2++
  66.         }
  67.         q1++
  68.     }
  69.     var pi = make([] int, n)
  70.     q = 0
  71.     for q < n {
  72.         pi[Q[q].i] = Find(&Q[q]).i
  73.         q++
  74.     }
  75.     return m, pi
  76. }
  77.  
  78. func Split(delta [][] Graph, pi[] int, n, X, q int) (int, []int) {
  79.     var m, x, q1, q2 int
  80.     var eq bool
  81.     var Q = make([] Graph, n)
  82.     m = n
  83.     q, q1 = 0, 0
  84.     for q < n {
  85.         Q[q].i = q
  86.         Q[q].parent = &Q[q]
  87.         Q[q].depth = 0
  88.         q++
  89.     }
  90.     for q1 < n {
  91.         q2 = 0
  92.         for q2 < n {
  93.             if pi[Q[q1].i] == pi[Q[q2].i] && Find(&Q[q1]) != Find(&Q[q2]) {
  94.                 eq = true
  95.                 x = 0
  96.                 for x < X {
  97.                     w1 := delta[Q[q1].i][x].state
  98.                     w2 := delta[Q[q2].i][x].state
  99.                     if pi[w1] != pi[w2] {
  100.                         eq = false
  101.                         break
  102.                     }
  103.                     x++
  104.                 }
  105.                 if eq {
  106.                     Union(&Q[q1], &Q[q2])
  107.                     m = m - 1
  108.                 }
  109.             }
  110.             q2++
  111.         }
  112.         q1++
  113.     }
  114.     q = 0
  115.     for q < n {
  116.         pi[Q[q].i] = Find(&Q[q]).i
  117.         q++
  118.     }
  119.     return m, pi
  120. }
  121.  
  122. func AufenkampHohn(A [][] Graph, n, X, qq int) ([]Graph){
  123.     var m1, m, q, x int
  124.     var pi []int
  125.     var matrixes = make([][]Graph, n, n)
  126.     m, pi = Split1(A, n, X, qq)
  127.     for {
  128.         m1, pi = Split(A, pi, n, X, qq)
  129.         if m == m1 {
  130.             break
  131.         }
  132.         m = m1
  133.     }
  134.     for i := 0; i < n; i++ {
  135.         matrixes[i] = make([] Graph, X)
  136.     }
  137.     var Q = make([] bool, n)
  138.     for q < n {
  139.         q1 := pi[q]
  140.         if !Q[q1] {
  141.             Q[q1] = true
  142.             x = 0
  143.             for x < X {
  144.                 matrixes[q1][x].state = pi[A[q][x].state]
  145.                 matrixes[q1][x].inputAlphabet = A[q][x].inputAlphabet
  146.                 x++
  147.             }
  148.         }
  149.         q++
  150.     }
  151.     return DFS(matrixes, n, X, pi[qq])
  152.     //return matrixes
  153. }
  154.  
  155. func DFS(arr1[][] Graph, n, m, q int) ([]Graph){
  156.     var sizeStack, count, i, j int
  157.     var newMatrix = make([] Graph, n)
  158.     var stack = make([]int, n*n)
  159.     count = 0
  160.     stack[0] = q
  161.     sizeStack = 1
  162.     for sizeStack > 0 {
  163.         sizeStack--
  164.         var v = stack[sizeStack]
  165.         if newMatrix[v].mark != "black" {
  166.             newMatrix[v].mark = "black"
  167.             newMatrix[v].i = count
  168.             count++
  169.         }
  170.         i = m - 1
  171.         for i > -1 {
  172.             u := arr1[v][i].state
  173.             if newMatrix[u].mark != "black" {
  174.                 stack[sizeStack] = u
  175.                 sizeStack++
  176.             }
  177.             i--
  178.         }
  179.     }
  180.     i = 0
  181.     for i < n {
  182.         if newMatrix[i].mark == "black" {
  183.             j = 0
  184.             for j < m {
  185.                 arr1[newMatrix[i].i][j].newState = newMatrix[arr1[i][j].state].i
  186.                 arr1[newMatrix[i].i][j].newInputAlphabet = arr1[i][j].inputAlphabet
  187.                 j++
  188.             }
  189.         }
  190.         i++
  191.     }
  192.     return newMatrix
  193.  
  194.     //fmt.Print("digraph {\n", "        rankdir = LR\n", "      dummy [label = \"\", shape = none]\n")
  195.     //for i := 0; i < count; i++ {
  196.     //  fmt.Print("     ", i, " [shape = circle]\n")
  197.     //}
  198.     //fmt.Print("       dummy -> ", 0, "\n")
  199.     //for i := 0; i < count; i++ {
  200.     //  for j := 0; j < m; j++ {
  201.     //      fmt.Print("     ", i, " -> ", arr1[i][j].newState, " [label = \"", (string)(97+j), "(", arr1[i][j].newInputAlphabet, ")\"]\n")
  202.     //  }
  203.     //}
  204.     //fmt.Print("}")
  205. }
  206.  
  207. func main() {
  208.     //первый автомат
  209.     var n, m, q0 int
  210.     fmt.Scan(&n, &m, &q0) //количество состояний автомата, размер входного автомата, номер начального состояния
  211.     var matrix = make([][] Graph, n, n)
  212.  
  213.     //матрица переходов
  214.     for i := 0; i < n; i++ {
  215.         matrix[i] = make([] Graph, m)
  216.         for j := 0; j < m; j++ {
  217.             fmt.Scan(&matrix[i][j].state)
  218.         }
  219.     }
  220.  
  221.     //матрица выходов
  222.     for i := 0; i < n; i++ {
  223.         for j := 0; j < m; j++ {
  224.             fmt.Scan(&matrix[i][j].inputAlphabet)
  225.         }
  226.     }
  227.  
  228.     nn1 := AufenkampHohn(matrix, n, m, q0)
  229.     //второй автомат
  230.     var n1, m1, q1 int
  231.     fmt.Scan(&n1, &m1, &q1) //количество состояний автомата, размер входного автомата, номер начального состояния
  232.     var matrix1 = make([][] Graph, n1, n1)
  233.  
  234.     //матрица переходов
  235.     for i := 0; i < n1; i++ {
  236.         matrix1[i] = make([] Graph, m1)
  237.         for j := 0; j < m1; j++ {
  238.             fmt.Scan(&matrix1[i][j].state)
  239.         }
  240.     }
  241.  
  242.     //матрица выходов
  243.     for i := 0; i < n1; i++ {
  244.         for j := 0; j < m1; j++ {
  245.             fmt.Scan(&matrix1[i][j].inputAlphabet)
  246.         }
  247.     }
  248.  
  249.     nn2 := AufenkampHohn(matrix1, n1, m1, q1)
  250.     //for i := 0; i < n1; i++ {
  251.     //  for j := 0; j < m1; j++ {
  252.     //      if matrix[i][j].state != matrix1[i][j].state ||  matrix[i][j].inputAlphabet != matrix1[i][j].inputAlphabet{
  253.     //          break
  254.     //          fmt.Print("NOT EQUAL\n")
  255.     //
  256.     //      } else if matrix[i][j].state == matrix1[i][j].state &&  matrix[i][j].inputAlphabet == matrix1[i][j].inputAlphabet{
  257.     //          fmt.Print("EQUAL\n")
  258.     //      }
  259.     //  }
  260.     //}
  261.     flag := true
  262.     //if m == m1 {
  263.     //  flag = true
  264.     //} else {
  265.     if n < n1 {
  266.         for i := 0; i < n; i++ {
  267.             //for j := 0; j < m1; j++ {
  268.             if nn1[i] == nn2[i] {
  269.                 //break
  270.                 //fmt.Print("EQUAL\n")
  271.                 flag = true
  272.             } else { //else if matrix[i][j].state == matrix1[i][j].state &&  matrix[i][j].inputAlphabet == matrix1[i][j].inputAlphabet{
  273.                 //fmt.Print("NOT EQUAL\n")
  274.                 flag = false
  275.                 //break
  276.             }
  277.         }
  278.     } else {
  279.         for i := 0; i < n1; i++ {
  280.             //for j := 0; j < m1; j++ {
  281.             if nn1[i] == nn2[i] {
  282.                 //break
  283.                 //fmt.Print("EQUAL\n")
  284.                 flag = true
  285.             } else { //else if matrix[i][j].state == matrix1[i][j].state &&  matrix[i][j].inputAlphabet == matrix1[i][j].inputAlphabet{
  286.                 //fmt.Print("NOT EQUAL\n")
  287.                 flag = false
  288.                 //break
  289.             }
  290.         }
  291.     }
  292.     //}
  293.     //}
  294.     if flag == true {
  295.         fmt.Print("EQUAL\n")
  296.     } else {
  297.         fmt.Print("NOT EQUAL\n")
  298.     }
  299.     //if AufenkampHohn(matrix1, n1, m1, q1) == AufenkampHohn(matrix, n, m, q0) {
  300.     //  fmt.Print("EQUAL\n")
  301.     //} else {
  302.     //fmt.Print("NOT EQUAL\n")
  303.     //}
  304. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top