1:- module(add_node_one_by_one_indirect, []). 2
3 6
7:- use_module(zdd('zdd-array')). 8:- use_module(zdd(zdd)). 9:- use_module(zdd('minato-r5')). 10:- use_module(pac(op)). 13
14 18mate_less_than(_ - A, B -_):- A @< B.
19
21composable_pairs(A-B, A-C, B, C).
22composable_pairs(A-B, C-A, B, C).
23composable_pairs(B-A, A-C, B, C).
24composable_pairs(B-A, C-A, B, C).
26normal_pair(A-B, U-V):-!, ( B @< A -> U=B, V=A; U=A, V=B ).
27normal_pair(A->B, U->V):- ( B @< A -> U=B, V=A; U=A, V=B ).
28
29
30 33
35
36subst_node(_, _, _, X, 0, _, _):- X<2, !.
37subst_node(Es, A, P, X, Y, S, W):- 38 cofact(X, t(U, L, R), S),
39 ( U= @(_) -> Y = 0
40 ; U = Lu-_, A @< Lu -> Y = 0
41 ; U = Lu-Ru,
42 subst_node(Es, A, P, L, L0, S, W),
43 ( Ru = A ->
44 normal_pair(Lu-P, V),
45 mate_ord_insert([V|Es], R, R0, S, W)
46 ; Lu = A ->
47 normal_pair(Ru-P, V),
48 mate_ord_insert([V|Es], R, R0, S, W)
49 ; subst_node(Es, A, P, R, R1, S, W),
50 mate_insert(U, R1, R0, S, W)
51 ),
52 mate_join(L0, R0, Y, S, W)
53 ).
54
57rect_nodes(rect(W, H), Ns):-
58 findall(p(I,J),
59 ( between(0, W, I),
60 between(0, H, J)
61 ),
62 Ns).
63
66rect_udg(rect(W, H), UDG):-
67 findall( p(I,J)-Suc,
68 ( between(0, W, I),
69 between(0, H, J),
70 findall( p(K,L),
71 ( L=J, K is I + 1, K =< W
72 ; K=I, L is J + 1, L =< H
73 ),
74 Suc)
75 ),
76 UDG).
77
93
98
99reverse_successors(X-A, X-B):- reverse(A, B).
100
102rect_mate(Rect, X, S, W):-rect_mate(Rect, X, [slim(0)], S, W).
103
105rect_mate(Rect, X, InOpts, S, SW):-
106 ( memberchk(gc(CtrlSlim), InOpts) -> true
107 ; CtrlSlim= 0
108 ),
109 Rect = rect(W,H),
110 rect_udg(Rect, Dg0),
111 maplist(reverse_successors, Dg0, Dg1),
112 reverse(Dg1, Dg),
113 open_mate(S, SW),
114 set_key(max_node, p(W, H), S),
115 udg_mate(CtrlSlim, Dg, 1, X0, S, SW),
116 get_key(max_node, Max, S),
117 prune_final(p(0,0), Max, X0, X, S, SW).
119udg_mate(_, [], X, X, _, _).
120udg_mate(Ctrl, [N-Ps|UDG], X, Y, S, W):-
121 add_node(N, Ps, X, X0, S, W),
122 get_key(max_node, Max, S),
123 prune_by_classify_link(N, Max, X0, X1, S, W),
124 ctrl_slim(Ctrl, N, X1, X2, S),
125 udg_mate(Ctrl, UDG, X2, Y, S, W).
126
128ctrl_slim(all, P, X, Y, S):-!,
129 format("GC at ~w \n", [P]),
130 zdd_slim(X, Y, S),
131 garbage_collect.
132ctrl_slim(no, _, X, X, _):-!.
133ctrl_slim(K, P, X, Y, S):-integer(K),
134 P = p(_, J),
135 ( J = K ->
136 format("GC at ~w \n", [P]),
137 zdd_slim(X, Y, S),
138 garbage_collect
139 ; Y = X
140 ).
141
143add_node(N, [], X, Y, S, _):-!, zdd_insert(N-N, X, Y, S).
144add_node(N, [P|Ps], X, Y, S, W):- normal_pair(N->P, Q),
145 subst_node([Q], P, N, X, X0, S, W),
146 zdd_insert(N-N, X, X1, S),
147 mate_join(X0, X1, X2, S, W),
148 add_neighbor_links(N, Ps, X2, Y, S, W).
150add_neighbor_links(_, [], X, X, _, _):-!.
151add_neighbor_links(N, [P|Ps], X, Y, S, W):- normal_pair(N-P, Link),
152 add_link(Link, X, X0, S, W),
153 mate_join(X0, X, X1, S, W),
154 add_neighbor_links(N, Ps, X1, Y, S, W).
155
159
163
168
173
174add_link(_, X, 0, _, _):- X<2, !.
175add_link(U, X, Y, S, W):- 176 cofact(X, t(A, L, R), S),
177 ( A = @(_) -> Y = 0
178 ; add_link(U, L, L0, S, W),
179 U = Ul-Ur,
180 ( mate_less_than(U, A) -> R0 = 0
181 ; A = U -> R0 = 0
182 ; composable_pairs(U, A, U0, V0) ->
183 subst_node([(Ul->Ur)], U0, V0, R, R0, S, W)
184 ; add_link(U, R, R1, S, W),
185 mate_insert(A, R1, R0, S, W)
186 ),
187 mate_join(L0, R0, Y, S, W)
188 ).
189
193
199
200prune_final(_, _, X, X, _, _):- X<2, !.
201prune_final(P, Q, X, Y, S, W):- cofact(X, t(A, L, R), S),
202 prune_final(P, Q, L, L0, S, W),
203 ( A = @(_) -> cofact(R0, t(A, 0, 1), S)
204 ; A = A1-A2,
205 ( A1 = P ->
206 ( A2 = Q
207 -> prune_final(P, Q, R, R0, S, W)
208 ; R0 = 0
209 )
210 ; A1 = A2 ->
211 prune_final(P, Q, R, R0, S, W)
212 ; R0 = 0
213 )
214 ),
215 mate_join(L0, R0, Y, S, W).
216
220
221classify_link(_, _, @(_), id):-!.
222classify_link(P, End, A-B, Case):- on_frontier(P, A), !,
223 ( on_frontier(P, B) -> Case = keep
224 ; B = End -> Case = keep
225 ; Case = 0
226 ).
227classify_link(_, _, A-A, ignore):-!.
228classify_link(_, _, _, 0).
230on_frontier(p(0, J), p(0, J)):-!.
231on_frontier(p(0, J), p(K, L)):-!, K = 1, L< J.
232on_frontier(p(I, J), p(I, K)):- K >= J, !.
233on_frontier(p(I, J), p(I0, K)):- I0 is I + 1, K < J.
235prune_by_classify_link(_, _, X, X, _, _):- X<2, !.
236prune_by_classify_link(P, End, X, Y, S, W):- cofact(X, t(A, L, R), S),
237 classify_link(P, End, A, Case),
238 ( Case = id -> Y = X
239 ; prune_by_classify_link(P, End, L, L0, S, W),
240 ( Case = keep ->
241 prune_by_classify_link(P, End, R, R1, S, W),
242 mate_insert(A, R1, R0, S, W)
243 ; Case = ignore ->
244 prune_by_classify_link(P, End, R, R0, S, W)
245 ; R0 = 0
246 ),
247 mate_join(L0, R0, Y, S, W)
248 ).
249