daily pastebin goal
44%
SHARE
TWEET

Untitled

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