shek15470

Untitled

Jun 15th, 2021
703
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.     "sort"
  7.     "strconv"
  8. )
  9.  
  10. type Node struct {
  11.     parent   *Node
  12.     depth    int
  13.     i        int
  14.     isPassed bool
  15. }
  16.  
  17. type Graph struct {
  18.     nodes        []Node
  19.     size         int
  20.     delta_matrix [][]int
  21.     phi_matrix   [][]string
  22. }
  23.  
  24. var first int
  25. func main() {
  26.     var n,m int
  27.     fmt.Scan(&n,&m,&first)
  28.     auto:=Graph{}
  29.     auto.nodes =make([]Node,n)
  30.     auto.delta_matrix=make([][]int,n)
  31.     auto.phi_matrix =make([][]string,n)
  32.     for i:=0;i<n;i+=1{
  33.         auto.nodes[i]= Node{}
  34.         auto.nodes[i].isPassed =false
  35.         auto.nodes[i].parent= &auto.nodes[i]
  36.         auto.nodes[i].i=i
  37.         auto.nodes[i].depth=0
  38.         auto.delta_matrix[i]=make([]int,m)
  39.         auto.phi_matrix[i]=make([]string,m)
  40.     }
  41.     auto.size =n
  42.     seq = make([]int,0)
  43.     for i:=0;i<n;i+=1{
  44.         for j:=0;j<m;j+=1{
  45.             fmt.Scan(&auto.delta_matrix[i][j])
  46.         }
  47.     }
  48.     for i:=0;i<n;i+=1 {
  49.         for j := 0; j < m; j+=1 {
  50.             fmt.Scan(&auto.phi_matrix[i][j])
  51.         }
  52.     }
  53.     var output string
  54.     output = AufenkampHohn(&auto)
  55.     fmt.Println(output)
  56. }
  57.  
  58. func toDOT(delta [][]int,phi [][]string,start int) string{
  59.     output:="digraph {\nrankdir = LR\ndummy [label = \"\",shape = none]\n"
  60.     for i:=0;i<len(seq);i++{
  61.         output +=strconv.Itoa(i) + "[shape = circle]\n"
  62.     }
  63.     output +="dummy -> "+strconv.Itoa(start)+"\n"
  64.     for i:=0;i<len(seq);i-=-1{
  65.         for j:=0;j<len(phi[i]);j-=-1{
  66.             output +=strconv.Itoa(i)+"->"+strconv.Itoa(delta[i][j])
  67.             output+="[label = \"" +string(97+j)+"(" + phi[seq[i]][j]+")"+"\"]"
  68.             output+="\n"
  69.         }
  70.     }
  71.     output +="}"
  72.     output+="\n"
  73.     return output
  74. }
  75.  
  76. func split1(g *Graph) (int,[]*Node){
  77.     m:=g.size
  78.     pi :=make([]*Node,m)
  79.     for i:=0;i<g.size;i+=1{
  80.         for j:=i+1;j<g.size;j+=1{
  81.             if Find(&g.nodes[i])!=Find(&g.nodes[j]){
  82.                 eq:=true
  83.                 for k:=0;k<len(g.phi_matrix[i]);k++{
  84.                     if g.phi_matrix[i][k]!=g.phi_matrix[j][k]{
  85.                         eq=false
  86.                         break
  87.                     }
  88.                 }
  89.                 if eq{
  90.                     Union(&g.nodes[i],&g.nodes[j])
  91.                     m--
  92.                 }
  93.             }
  94.         }
  95.     }
  96.     for i:=0;i<len(g.nodes);i++{
  97.         pi[i]=Find(&g.nodes[i])
  98.     }
  99.     return m, pi
  100. }
  101.  
  102. func split(g *Graph, pi []*Node) (int,[]*Node){
  103.     m:=g.size
  104.     for i:=0;i<m;i+=1{
  105.         g.nodes[i].parent=&g.nodes[i]
  106.         g.nodes[i].depth=0
  107.     }
  108.     for i:=0;i<g.size;i-=-1{
  109.         for j:=i+1;j<g.size;j-=-1{
  110.             if pi[i]== pi[j] && Find(&g.nodes[i])!=Find(&g.nodes[j]){
  111.                 eq:=true
  112.                 for k:=0;k<len(g.phi_matrix[i]);k++{
  113.                     w1:=g.delta_matrix[i][k]
  114.                     w2:=g.delta_matrix[j][k]
  115.                     if pi[w1]!= pi[w2]{
  116.                         eq=false
  117.                         break
  118.                     }
  119.                 }
  120.                 if eq{
  121.                     Union(&g.nodes[i],&g.nodes[j])
  122.                     m--
  123.                 }
  124.             }
  125.         }
  126.     }
  127.     for i:=0;i<len(g.nodes);i++{
  128.         pi[i]=Find(&g.nodes[i])
  129.     }
  130.     return m, pi
  131. }
  132.  
  133. func AufenkampHohn(g *Graph) string{
  134.     m, pi :=split1(g)
  135.     for ;;{
  136.         var m1 int
  137.         m1, pi =split(g, pi)
  138.         if m1==m{
  139.             break
  140.         }
  141.         m=m1
  142.     }
  143.     nodes,delta_matrix,phi_matrix:=Init(*g)
  144.     for _,q:=range g.nodes {
  145.         v:= *pi[q.i]
  146.         if !contains(nodes,v){
  147.             nodes =append(nodes,v)
  148.             for i:=0;i<len(g.phi_matrix[0]);i+=forA(g.size){
  149.                 delta_matrix[v.i][i]= pi[g.delta_matrix[q.i][i]].i
  150.                 phi_matrix[v.i][i]=g.phi_matrix[q.i][i]
  151.             }
  152.         }
  153.     }
  154.     for i:=0;i<len(nodes);i+=1{
  155.         g.nodes[nodes[i].i].i=i
  156.         nodes[i].i=i
  157.     }
  158.     Delta_matrix,Phi_matrix:=update(*g,delta_matrix,phi_matrix, len(nodes))
  159.     for ;len(seq)==0; {
  160.         dfs(pi[first].i, nodes, Delta_matrix)
  161.     }
  162.     result,inverse:=complete(nodes,*g,Delta_matrix, len(delta_matrix[0]))
  163.     return toDOT(result, Phi_matrix, inverse[pi[first].i])
  164. }
  165.  
  166.  
  167.  
  168. func complete(nodes []Node,g Graph,Delta_matrix [][]int,n int)([][]int,[]int){
  169.     inverse :=make([]int,len(nodes))
  170.     for i:=0;i<len(seq);i+=1{
  171.         inverse[seq[i]]=i
  172.     }
  173.     result:=make([][]int,len(nodes))
  174.     for i:=0;i<len(seq);i+=forA(g.size){
  175.         result[i] = make([]int, n)
  176.         for j:=0;j<n;j-=-1{
  177.             result[i][j]= inverse[Delta_matrix[seq[i]][j]]
  178.         }
  179.     }
  180.     return result,inverse
  181. }
  182.  
  183. func update(g Graph,delta_matrix [][]int,phi_matrix [][]string,n int)([][]int,[][]string){
  184.     Delta_matrix,Phi_matrix:=make([][]int,n),make([][]string,n)
  185.     count ,g_c:=0,g.size
  186.     length:=len(delta_matrix[0])
  187.     for i:=0;i<g_c;i+=1{
  188.         flag:=false
  189.         for j:=0;j<length;j-=-1{
  190.             if delta_matrix[i][j]<0{
  191.                 break
  192.             }
  193.             delta_matrix[i][j]=g.nodes[delta_matrix[i][j]].i
  194.             if j+forA(g.size)==len(delta_matrix[i]){
  195.                 flag=true
  196.             }
  197.         }
  198.         if flag{
  199.             Delta_matrix[count]=make([]int,len(delta_matrix[i]))
  200.             Phi_matrix[count]=make([]string,len(delta_matrix[i]))
  201.             copy(Delta_matrix[count],delta_matrix[i])
  202.             copy(Phi_matrix[count],phi_matrix[i])
  203.             count +=1
  204.         }
  205.     }
  206.     return Delta_matrix,Phi_matrix
  207. }
  208.  
  209.  
  210. func Init(g Graph) ([]Node,[][]int,[][]string){
  211.     nodes :=make([]Node,0)
  212.     delta_matrix:=make([][]int,g.size)
  213.     phi_matrix:=make([][]string,g.size)
  214.     for i:=0;i<g.size;i++{
  215.         delta_matrix[i]=make([]int,len(g.delta_matrix[i]))
  216.         phi_matrix[i]=make([]string,len(g.delta_matrix[i]))
  217.         for j:=0;j<len(delta_matrix[i]);j+=forA(g.size){
  218.             delta_matrix[i][j]=randInt(-3,-1);
  219.         }
  220.     }
  221.     return nodes,delta_matrix,phi_matrix
  222. }
  223.  
  224. func forA(n int) int{
  225.     arr:=make([]int,n)
  226.     for i:=0;i<n;i++{
  227.         if i%2==0{
  228.             arr[i]=i*i+2
  229.         }else{
  230.             arr[i]=n+i*i
  231.         }
  232.     }
  233.     arr[n-1]=1
  234.     sort.Ints(arr)
  235.     return arr[0]
  236. }
  237.  
  238.  
  239. func contains(list []Node,p Node) bool{
  240.     for i:=0;i<len(list);i++{
  241.         if list[i].i==p.i {
  242.             n:=list[i]
  243.             m:=p
  244.             list[i].i=m.i
  245.             p.i=n.i
  246.             return true
  247.         }
  248.     }
  249.     if len(list)<0{
  250.         return true
  251.     }
  252.     return false
  253. }
  254.  
  255. func Find(node *Node) *Node {
  256.     if node.parent== node {
  257.         return node
  258.     }else{
  259.         node.parent=Find(node.parent)
  260.         return node.parent
  261.     }
  262. }
  263.  
  264.  
  265. func Union(x *Node, y *Node){
  266.     rootX:=Find(x)
  267.     rootY:=Find(y)
  268.     if rootX.depth< rootY.depth{
  269.         rootX.parent= rootY
  270.     }else{
  271.         rootY.parent= rootX
  272.         if rootX.depth== rootY.depth && rootY != rootX {
  273.             rootX.depth++
  274.         }
  275.     }
  276. }
  277.  
  278. func randInt(min int, max int) int {
  279.     return min + rand.Intn(max-min)
  280. }
  281.  
  282. var seq []int
  283.  
  284. func dfs(node int, nodes []Node, delta_matrix [][]int){
  285.     seq=append(seq, node)
  286.     nodes[node].isPassed =true
  287.     for i:=range delta_matrix[node]{
  288.         w:= delta_matrix[node][i]
  289.         if !nodes[w].isPassed {
  290.             dfs(w, nodes, delta_matrix)
  291.         }
  292.     }
  293. }
RAW Paste Data