# 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]))
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