Let f(n) be the number of undirected connected graphs (CUDG) with n nodes. For examples, f(2)=1, f(3)=4.
I wrote a codes using ZDD library to enumerate such CUGD for give n. Although this was a hobby programming for me for curiosity, it may have two possible interesting points. One is that it uses prolog lists of nodes as atoms of ZDD. Usual ZDD atoms are prolog atoms or ground flat terms of fixed arity. The second point that the codes at first constructs the power set of the set of possible links between nodes, and use them as an integer key of key-vals for tabling, which is due to the property of ZDD that each family of sets has a unique integer index.
I have compared two versions, one is a naive version which does not use key-val memo ( tabling), the other builds the power set of possible links. The smart version appeared to be 3 times faster, which I was a little bit surprised to see.
For those who are interested in this feature, I listed the smart version codes below. It should work with the current ZDD library included in the pack pac-1.6.6.
% ?- count_cudg([a,b], C).
%@ C = 1.
% ?- count_cudg([a,b,c], C).
%@ C = 4.
% ?- count_cudg([a,b,c,d], C).
%@ C = 38.
% ?- N = 10, time((numlist(1, 10, Ns), count_cudg(Ns, C))).
%@ % 1,439,423,037 inferences, 142.657 CPU in 145.688 seconds (98% CPU, 10090105 Lips)
%@ N = 10,
%@ Ns = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
%@ C = 34496488594816.
% ?- N = 11, numlist(1, N, Ns), call_with_time_limit(18000, time(count_cudg(Ns, C))).
%@ % 9,519,980,664 inferences, 1300.998 CPU in 1317.768 seconds (99% CPU, 7317443 Lips)
%@ N = 11,
%@ Ns = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
%@ C = 35641657548953344.
:- module(count_cudg, []).
:- use_module(util(math)).
:- use_module(util(meta2)).
:- use_module(pac(basic)).
:- use_module(pac(meta)).
:- use_module(util(misc)).
:- use_module(pac('expand-pac')).
:- use_module(zdd('zdd-array')).
:- use_module(zdd(zdd)).
:- use_module(zdd('zdd-misc')).
:- use_module(zdd('zdd-plain')).
:- use_module(pac(op)).
/***********************************************
* count connected udg with pow and memo *
***********************************************/
count_cudg(Ns, C):- count_connected_udg(Ns, C, _, _).
%
count_connected_udg(Ns, C, X, S):-
open_state(S),
set_compare(link_compare, S),
zdd_sort(Ns, Ns0, S),
all_links(Ns0, Links),
findall([A], member(A, Ns0), Singletons),
zdd_ord_insert(Singletons, 1, Init, S),
memo(add_link(1)-Init, S),
zdd_power(Links, Pow, S),
add_links_to_udg(Pow, U, S),
collect_finals(U, X, S),
card(X, C, S).
%
add_links_to_udg(0, 0, _):- !.
add_links_to_udg(1, Y, S):- !, memo(add_link(1)-Y, S).
add_links_to_udg(X, Y, S):- memo(add_link(X)-Y, S),
( nonvar(Y) -> true %, write(.) % many hits.
; cofact(X, t(A, L, R), S),
add_links_to_udg(L, L0, S),
add_links_to_udg(R, R1, S),
add_link(A, R1, R0, S),
zdd_join(L0, R0, Y, S)
).
/***************************
* common predicates *
***************************/
%! mk_union_find_command(+,+,?) semidet.
mk_union_find_command(A-B, D, F):- successive_select(D, [A, B], R),
( R = [] -> F = zdd_ord_insert([D, A->B])
; R = [A] -> F = union_find_insert(A->B, A, D)
; R = [B] -> F = union_find_insert(A->B, B, D)
).
successive_select([], Y, Y):-!.
successive_select([A|X], Y, Z):-select(A, Y, Y0), !,
successive_select(X, Y0, Z).
successive_select([_|X], Y, Z):-successive_select(X, Y, Z).
link_compare(C, A->B, D->E):-!, compare(C, (A,B), (D,E)).
link_compare(<, _, _->_):-!.
link_compare(>, _->_, _):-!.
link_compare(C, X, Y):- compare(C, X, Y).
all_links(Nodes, Links):-
findall(A-B, (append(_, [A|R], Nodes),
member(B, R),
A@<B
),
Links).
union_find_insert(_E, _A, _G, X, X, _):- X < 2, !.
union_find_insert(E, A, G, X, Y, S):-
cofact(X, t(U, L, R), S),
( U= (_->_) -> Y = X
; union_find_insert(E, A, G, L, L0, S),
( memberchk(A, U) ->
ord_union(G, U, H),
zdd_ord_insert([H,E], R, R0, S)
; union_find_insert(E, A, G, R, R1, S),
zdd_insert(U, R1, R0, S)
),
zdd_join(L0, R0, Y, S)
).
% ?- zdd((set_compare(link_compare), X<<{[[a], [b], [c]]},
% shift0(add_links([a-b, b-c], X, Y)), psa(Y))).
add_link(_, X, 0, _):- X<2, !.
add_link(U, X, Y, S):- % memo is useless here.
cofact(X, t(A, L, R), S),
( A = (_->_) -> Y = 0
; add_link(U, L, L0, S),
( mk_union_find_command(U, A, F) ->
call(F, R, R0, S)
; add_link(U, R, R1, S),
zdd_insert(A, R1, R0, S)
),
zdd_join(L0, R0, Y, S)
).
collect_finals(X, 0, _):- X<2, !.
collect_finals(X, Y, S):- cofact(X, t(_, L, R), S),
collect_finals(L, L0, S),
collect_pure_links(R, R0, S),
zdd_join(L0, R0, Y, S).
%
collect_pure_links(X, X, _):-X<2, !.
collect_pure_links(X, Y, S):- cofact(X, t(A, L, R), S),
collect_pure_links(L, L0, S),
( A = [_|_] -> R0 = 0
; zdd_insert(A, R, R0, S)
),
zdd_join(L0, R0, Y, S).