1:- module(count_cudg, []).    2:- use_module(util(math)).    3:- use_module(util(meta2)).    4:- use_module(pac(basic)).    5:- use_module(pac(meta)).    6:- use_module(util(misc)).    7:- use_module(pac('expand-pac')).    8:- use_module(zdd('zdd-array')).    9:- use_module(zdd(zdd)).   10:- use_module(zdd('zdd-misc')).   11:- use_module(zdd('zdd-plain')).   12:- use_module(pac(op)).   13
   14:- current_op(X, Y, zdd), op(X, Y, zdd1).   15:- meta_predicate zdd1(:).   16zdd1(G) :- (zdd set_compare(ccu_compare), G).
   17
   18
   19% ?- mk_union_find_command(a-b, [c], F). % false
   20% ?- mk_union_find_command(a-b, [b,c], F).
   21
   22		/***********************************************
   23		*     count connected udg with pow and memo    *
   24		***********************************************/
   25
   26% ?- count_cudg([a,b], C).
   27% ?- count_cudg([a,b,c], C).
   28% ?- count_cudg([a,b,c,d], C).
   29% ?- count_cudg([a,b,c,d,e], C).
   30% ?- count_cudg([a,b,c,d,e,f], C).
   31% ?- count_cudg([a,b,c,d,e,f,g], C).
   32% ?- time(count_cudg([a,b,c,d,e,f,g,h], C)).
   33%@ % 28,100,683 inferences, 1.804 CPU in 1.863 seconds (97% CPU, 15579276 Lips)
   34%@ C = 251548592.
   35%@ % 26,904,200 inferences, 2.565 CPU in 2.623 seconds (98% CPU, 10486976 Lips)
   36%@ C = 251548592.
   37
   38%  Smart version is faster than naive one below.
   39% ?- N=9, numlist(1, N, Ns), time(count_cudg(Ns, C)).
   40%@ % 178,109,543 inferences, 17.234 CPU in 17.837 seconds (97% CPU, 10334881 Lips)
   41%@ N = 9,
   42%@ Ns = [1, 2, 3, 4, 5, 6, 7, 8, 9],
   43%@ C = 66296291072.
   44
   45% ?- N=10, time((numlist(1, 10, Ns), count_cudg(Ns, C))).
   46%@ % 1,069,982,356 inferences, 142.782 CPU in 146.466 seconds (97% CPU, 7493832 Lips)
   47%@ N = 10,
   48%@ Ns = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
   49%@ C = 34496488594816.
   50
   51% ?- N=11, numlist(1, N, Ns), call_with_time_limit(18000, time(count_cudg(Ns, C))).
   52%@ % 9,519,980,664 inferences, 1300.998 CPU in 1317.768 seconds (99% CPU, 7317443 Lips)
   53%@ N = 11,
   54%@ Ns = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
   55%@ C = 35641657548953344.
   56% ?- compare(C, [a,b], [c, d]).
   57
   58count_cudg(Ns, C):- count_connected_udg(Ns, C, _, _).
   59%
   60count_connected_udg(Ns, C, X, S):-
   61	open_state(S),
   62	set_compare(ccu_compare, S),
   63	zdd_sort(Ns, Ns0, S),
   64	all_links(Ns0, Links),
   65	findall([A], member(A, Ns0), Singletons),
   66	zdd_ord_insert(Singletons, 1, Init, S),
   67	memo(add_link(1)-Init, S),
   68	zdd_power(Links, Pow, S),
   69	add_links_to_udg(Pow, U, S),
   70	collect_finals(U, X, S),
   71	card(X, C, S).
   72%
   73add_links_to_udg(0, 0, _):- !.
   74add_links_to_udg(1, Y, S):- !, memo(add_link(1)-Y, S).
   75add_links_to_udg(X, Y, S):- memo(add_link(X)-Y, S),
   76	(	nonvar(Y) -> true		%,  write(.) % many hits.
   77	;	cofact(X, t(A, L, R), S),
   78		add_links_to_udg(L, L0, S),
   79		add_links_to_udg(R, R1, S),
   80		add_link(A, R1, R0, S),
   81		zdd_join(L0, R0, Y, S)
   82	).
   83
   84		/***************************
   85		*     common predicates    *
   86		***************************/
   87% this compare pred is essential.
   88ccu_compare(=, X, X):-!.
   89ccu_compare(<, X, _->_):- listp(X), !.
   90ccu_compare(>, _->_, X):- listp(X), !.
   91ccu_compare(C, X, Y):- compare(C, X, Y).

Generate appropriate union_find subcommand depending on membership of A and B in Cluster, where Link = A-B.

   98mk_union_find_command(A-B, D, F):-	successive_select(D, [A, B], R),
   99	(	R = []  -> F = zdd_ord_insert([D, A->B])
  100	;	R = [A] -> F = union_find_insert(A->B, A, D)
  101	;	R = [B] -> F = union_find_insert(A->B, B, D)
  102	).
  103
  104% ?- successive_select([b, a, c], [d], R).
  105% ?- successive_select([b, a, b, c], [b, a], R).
  106successive_select([], Y, Y):-!.
  107successive_select([A|X], Y, Z):-select(A, Y, Y0), !,
  108	successive_select(X, Y0, Z).
  109successive_select([_|X], Y, Z):-successive_select(X, Y, Z).
  110
  111% ?- all_links([a,b,c], Links).
  112all_links(Nodes, Links):-
  113	findall(A-B, (append(_, [A|R], Nodes),
  114				  member(B, R),
  115				  A@<B
  116				 ),
  117			Links).
  118
  119%
  120union_find_insert(_E, _A, _G, X, X, _):- X < 2, !.
  121union_find_insert(E, A, G, X, Y, S):-
  122	cofact(X, t(U, L, R), S),
  123	(	U= (_->_) ->	Y = 0
  124	;	union_find_insert(E, A, G, L, L0, S),
  125		(	memberchk(A, U) ->
  126			ord_union(G, U, H),
  127			zdd_ord_insert([H,E], R, R0, S)
  128		;	union_find_insert(E, A, G, R, R1, S),
  129			zdd_insert(U, R1, R0, S)
  130		),
  131		zdd_join(L0, R0, Y, S)
  132	).
  133
  134% ?- ccu_compare(C, [a,b], a->b).
  135%@ C = (<).
  136% ?- zdd1 zdd_compare(C, [a,b], a->b).
  137
  138% ?- zdd1 X<<{[[a], [b], [c]]}, add_links([a-b, b-c], X, Y), psa(Y).
  139% ?- zdd1 X<<{[[a],[b],[c]]}, add_links([a-b, a-c], X, Y), collect_finals(Y, Y0), psa(Y0).
  140% ?- zdd1 X<<{[[a], [b], [c], [d]]}, psa(X), add_link(a-b, X, Y), psa(Y),
  141%	add_link(b-c, Y, Z), add_link(a-d, Z, U), psa(U).
  142
  143add_link(_, X, 0, _):- X<2, !.
  144add_link(U, X, Y, S):- % memo is useless here.
  145	cofact(X, t(A, L, R), S),
  146	(	A = (_->_) -> Y = 0
  147	;	add_link(U, L, L0, S),
  148		(	mk_union_find_command(U, A, F) ->
  149			call(F, R, R0, S)
  150		;	add_link(U, R, R1, S),
  151			zdd_insert(A, R1, R0, S)
  152		),
  153		zdd_join(L0, R0, Y, S)
  154	).
  155
  156% ?- zdd1 X<<{[[a,b], a->b]}, psa(X), collect_finals(X, Y), psa(Y).
  157collect_finals(X, 0, _):- X<2, !.
  158collect_finals(X, Y, S):- cofact(X, t(_, L, R), S),
  159	collect_finals(L, L0, S),
  160	collect_pure_links(R, R0, S),
  161	zdd_join(L0, R0, Y, S).
  162
  163%
  164collect_pure_links(X, X, _):-X<2, !.
  165collect_pure_links(X, Y, S):- cofact(X, t(A, L, R), S),
  166	collect_pure_links(L, L0, S),
  167	(	A=[] -> collect_pure_links(R, R0, S)
  168	;	A=[_|_] -> R0 = 0
  169	; 	zdd_insert(A, R, R0, S)
  170	),
  171	zdd_join(L0, R0, Y, S).
  172
  173		/***********************************
  174		*     naive count connected udg    *
  175		***********************************/
  176
  177% ?- naive_count_cudg([a, b], C).
  178% ?- naive_count_cudg([a, b, c], C).
  179% ?- N=2, numlist(1, N, Ns), naive_count_cudg(Ns, C).
  180% ?- N=3, numlist(1, N, Ns), naive_count_cudg(Ns, C).
  181% ?- N=4, numlist(1, N, Ns), naive_count_cudg(Ns, C).
  182% ?- N=5, numlist(1, N, Ns), naive_count_cudg(Ns, C).
  183% ?- N=6, numlist(1, N, Ns), naive_count_cudg(Ns, C).
  184% ?- N=7, numlist(1, N, Ns), naive_count_cudg(Ns, C).
  185% ?- N=8, numlist(1, N, Ns), time(naive_count_cudg(Ns, C)).
  186% ?- N=9, numlist(1, N, Ns), time(naive_count_cudg(Ns, C)).
  187%@ % 526,646,646 inferences, 61.497 CPU in 62.799 seconds (98% CPU, 8563757 Lips)
  188%@ N = 9,
  189%@ Ns = [1, 2, 3, 4, 5, 6, 7, 8, 9],
  190%@ C = 66296291072.
  191
  192naive_count_cudg(Ns, C):- naive_count_connected_udg(Ns, C, _, _).
  193%
  194naive_count_connected_udg(Ns, C, X, S):-
  195	open_state(S),
  196	set_compare(ccu_compare, S),
  197	zdd_sort(Ns, Ns0, S),
  198	all_links(Ns0, Links),
  199	findall([A], member(A, Ns0), Singletons),
  200	zdd_ord_insert(Singletons, 1, Init, S),
  201	add_links(Links, Init, U, S),
  202	collect_finals(U, X, S),
  203	card(X, C, S).
  204
  205%
  206add_links([], X, X, _).
  207add_links([L|Ls], X, X0, S):- % memo is useless here.
  208	add_link(L, X, X1, S),
  209	zdd_join(X, X1, X2, S),
  210	add_links(Ls, X2, X0, S)