1:- module(add_node_one_by_one_indirect, []).    2
    3		/*********************************
    4		*     Obsolete. May not work.    *
    5		*********************************/
    6
    7:- use_module(zdd('zdd-array')).    8:- use_module(zdd(zdd)).    9:- use_module(zdd('minato-r5')).   10:- use_module(pac(op)).   11% :- use_module(zdd('mate-indirect')).
   12% ?- listing(open_mate).
   13
   14		/*******************
   15		*   Tiny helpers   *
   16		*******************/
   17%
   18mate_less_than(_ - A, B -_):- A @< B.
   19
   20% One of the most basic helpers.
   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).
   25%
   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		/****************************************************
   31		*     replace_end/bypass:  Most basic operations.   *
   32		****************************************************/
   33
   34% ?- zdd X<< +[*[c-d]], subst_node([a->c], c, a, X, Y, []), psa(X), psa(Y).
   35
   36subst_node(_, _, _, X, 0, _, _):- X<2, !.
   37subst_node(Es, A, P, X, Y, S, W):-			% replace A with P
   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
   55% ?- rect_nodes(rect(0,2), Ns).
   56% ?- rect_nodes(rect(10,10), Ns), length(Ns, L).
   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
   64% ?- rect_udg(rect(1,1), UDG).
   65% ?- rect_udg(rect(10,10), UDG),length(UDG, L).
   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
   78% ?- rect_mate(rect(0,0), X, [gc(0)], S, W), mate_card(X, C, S, W).
   79% ?- rect_mate(rect(1,0), X, [gc(0)], S, W), mate_card(X, C, S, W).
   80% ?- rect_mate(rect(0,1), X, [gc(0)], S, W), mate_card(X, C, S, W).
   81% ?- rect_mate(rect(1,1), X, [gc(all)], S, W), mate_card(X, C, S, W).
   82% ?- rect_mate(rect(3,3), X, [gc(0)], S, W), mate_card(X, C, S, W).
   83% ?- rect_mate(rect(4,4), X, [gc(0)], S, W), mate_card(X, C, S, W).
   84% ?- time((rect_mate(rect(4,4), X, [gc(0)], S, W), mate_card(X, C, S, W))).
   85% ?- time((rect_mate(rect(5,5), X, [gc(0)], S, W), mate_card(X, C, S, W))).
   86% ?- time((rect_mate(rect(7,7), X, [gc(0)], S, W), mate_card(X, C, S, W))).
   87%@ C = 789360053252 .
   88% ?- call_with_time_limit(1000, time((rect_mate(rect(7,7), X, [gc(0)], S, W), mate_card(X, C, S, W)))).
   89% ?- call_with_time_limit(1000, rect_mate(rect(13,13), X, [gc(all)], S, W)), mate_card(X, C, S, W).
   90% ?- time((rect_mate(rect(13,13), X, [gc(all)], S, W)), mate_card(X, C, S, W)).
   91% ?- rect_mate(rect(20,20), X, [gc(0)], S, W), mate_card(X, C, S, W).
   92% ?- rect_mate(rect(30,30), X, [gc(no)], S, W), mate_card(X, C, S, W), psa(20, W).
   93
   94% [2022/10/05] terminal (swipl-zdd)
   95% ?- call_with_time_limit(36000, rect_mate(rect(10,10), X, [gc(all)], S, W)), mate_card(X, C, S, W).
   96% W = ..,
   97% C = 1568758030464750013214100.
   98
   99reverse_successors(X-A, X-B):- reverse(A, B).
  100
  101% slim(K);  slim(no); slim(all).
  102rect_mate(Rect, X, S, W):-rect_mate(Rect, X, [slim(0)], S, W).
  103
  104%
  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).
  118%
  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
  127%
  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
  142%
  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).
  149%
  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
  156% ?- open_mate(S, W),
  157%	zdd_eval(+[[a-b, c-d]], X, S), ipsa(X, S, W),
  158%	add_link(b-c, X, Y, S,W), ipsa(Y, S, W).
  159
  160% ?- open_mate(S, W),
  161%	zdd_eval(+[[a-b, c-d], [e-f]], X, S), ipsa(X, S, W),
  162%	add_link(b-c, X, Y, S, W), ipsa(Y, S, W).
  163
  164% ?- open_mate(S, W),
  165%	zdd_eval(+[[a-b, c-d], [a-a, b-b]], X, S),
  166%	ipsa(X, S, W),
  167%	add_link(b-c, X, Y, S, W), ipsa(Y, S, W).
  168
  169% ?- open_mate(S, W),
  170%	zdd_eval(+[[a-a, b-b, c-c]], X, S),
  171%	ipsa(X, S, W),
  172%	add_link(b-c, X, Y, S, W), ipsa(Y, S, W).
  173
  174add_link(_, X, 0, _, _):- X<2, !.
  175add_link(U, X, Y, S, W):- % memo is useless here
  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
  190% ?- open_mate(S, W),
  191%  zdd_eval(+[[p(1,1)-p(3,3)]], X, S),
  192%	prune_final(p(0,0), p(3,3), X, Y, S, W).
  193
  194% ?- open_mate(S, W),
  195%  zdd_eval(+[[p(0,0)-p(3,3)]], X, S),
  196%	mate_insert(p(2,2)->p(2,3), X, X0, S, W),
  197%	prune_final(p(0,0), p(3,3), X0, Y, S, W),
  198%	ipsa(Y, S, W).
  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
  217% ?- classify_link(p(0,1), p(3,3), p(1,0)-p(3,3), X).
  218% ?- classify_link(p(0,1), p(3,3), p(0,2)-p(3,3), X).
  219% ?- classify_link(p(0,1), p(3,3), p(0,1)-p(3,3), X).
  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).
  229%
  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.
  234%
  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
  250% ?- open_mate(S, W),
  251%	mate_ord_insert([a-b], 1, X, S, W),
  252%	mate_ord_insert([c-d, e->f], 1, Y, S, W),
  253%	mate_join(X, Y, Z, S, W),
  254%	mate_card(Z, C, S, W), ipsa(Z, S, W).