I know how to do a simple generate and test to return each answer individually. In the following example only items that are greater than 1 are returned.
item(1).
item(1).
item(2).
item(3).
item(1).
item(7).
item(1).
item(4).
gen_test(Item) :-
item(Item), % generate
Item > 1. % test
?- gen_test(Item).
Item = 2 ;
Item = 3 ;
Item = 7 ;
Item = 4.
I can also return the results as a list using bagof/3
gen_test_bagof(List) :-
bagof(Item,(item(Item),Item > 1), List).
?- gen_test_bagof(List).
List = [2, 3, 7, 4].
Now I would like to be able to change the test so that it uses member/2 with a list where the list is the accumulation of all previous valid answers.
I have tried this
gen_test_acc_facts(L) :-
gen_test_acc_facts([],L).
gen_test_acc_facts(Acc0,R) :-
item(H), % generate
(
member(H,Acc0) % test
->
gen_test_acc_facts(Acc0,R) % Passes test, don't accumulate, run generate and test again.
;
gen_test_acc_facts([H|Acc0],R) % Fails test, accumulate, run generate and test again.
).
but since it is recursive, every call of item/1 results in the same first fact being used.
I suspect the answer will require eliminating backtracking as was done in this answer by mat because this needs to preserve information over backtracking.
Details
The example given is a simplified version of the real problem which is to generate graphs with N vertices where the edges are undirected, have no loops (self references), have no weights and the vertexes are labeled and there is no root vertex and set of graphs is only the isomorphic graphs. Generating all of the graphs for N is easy, and while I can accumulate all of the graphs into a list first, then test all of them against each other; once N=8 the memory is exhausted.
?- graph_sizes(N,Count).
N = 0, Count = 1 ;
N = Count, Count = 1 ;
N = Count, Count = 2 ;
N = 3, Count = 8 ;
N = 4, Count = 64 ;
N = 5, Count = 1024 ;
N = 6, Count = 32768 ;
N = 7, Count = 2097152 ;
ERROR: Out of global stack
However as there are many redundant isomorphic graphs generated, by pruning the list as it grows, the size of N can be increased. See: Enumerate all non-isomorphic graphs of a certain size
gen_vertices(N,L) :-
findall(X,between(1,N,X),L).
gen_edges(Vertices, Edges) :-
findall((X,Y), (member(X, Vertices), member(Y, Vertices), X < Y), Edges).
gen_combination_numerator(N,Numerator) :-
findall(X,between(0,N,X),L0),
member(Numerator,L0).
comb(0,_,[]).
comb(N,[X|T],[X|Comb]) :-
N>0,
N1 is N-1,
comb(N1,T,Comb).
comb(N,[_|T],Comb) :-
N>0,
comb(N,T,Comb).
gen_graphs(N,Graph) :-
gen_vertices(N,Vertices),
gen_edges(Vertices,Edges),
length(Edges,Denominator),
gen_combination_numerator(Denominator,Numerator),
comb(Numerator,Edges,Graph).
graph_sizes(N,Count) :-
length(_,N),
findall(.,gen_graphs(N,_), Sols),
length(Sols,Count).
The test for isomorphic graphs in Prolog.
Examples of generated graphs:
?- gen_graphs(1,G).
G = [] ;
false.
?- gen_graphs(2,G).
G = [] ;
G = [(1, 2)] ;
false.
?- gen_graphs(3,G).
G = [] ;
G = [(1, 2)] ;
G = [(1, 3)] ;
G = [(2, 3)] ;
G = [(1, 2), (1, 3)] ;
G = [(1, 2), (2, 3)] ;
G = [(1, 3), (2, 3)] ;
G = [(1, 2), (1, 3), (2, 3)] ;
false.
The differences between all the graphs being generated (A006125) vs the desired graphs (A001349) .
A006125 A001349 Extraneous
0 1 - 1 = 0
1 1 - 1 = 0
2 2 - 1 = 1
3 8 - 2 = 6
4 64 - 6 = 58
5 1024 - 21 = 1003
6 32768 - 112 = 32656
7 2097152 - 853 = 2096299
8 268435456 - 11117 = 268424339
9 68719476736 - 261080 = 68719215656
10 35184372088832 - 11716571 = 35184360372261
11 36028797018963968 - 1006700565 = 36028796012263403
12 73786976294838206464 - 164059830476 = 73786976130778375988
13 302231454903657293676544 - 50335907869219 = 302231454853321385807325
14 2475880078570760549798248448 - 29003487462848061 = 2475880078541757062335400387
15 40564819207303340847894502572032 - 31397381142761241960 = 40564819207271943466751741330072
Using geng and listg
Both of these programs are among many others are included in the nauty and Traces download link on the home page. (User's guide)
The programs are written in C and make use of make and can run on Linux. Instead of using Cygwin on Windows, WSL can be installed instead.
The source code can be downloaded using
wget "http://pallini.di.uniroma1.it/nauty26r11.tar.gz"
then
tar xvzf nauty26r11.tar.gz
cd nauty26r11
./configure
make
nauty generates output in graph6 format by default but can be converted to list of edges using listg, e.g.
eric@WINDOWS-XYZ:~/nauty26r11$ ./geng 3 | ./listg -e
>A ./geng -d0D2 n=3 e=0-3
>Z 4 graphs generated in 0.00 sec
Graph 1, order 3.
3 0
Graph 2, order 3.
3 1
0 2
Graph 3, order 3.
3 2
0 2 1 2
Graph 4, order 3.
3 3
0 1 0 2 1 2
Useful options for the programs
geng
-help : options
-c : only write connected graphs (A001349)
-u : do not output any graphs, just generate and count them
Example
eric@WINDOWS-ABC:~/nauty26r11$ ./geng -c -u 10
>A ./geng -cd1D9 n=10 e=9-45
>Z 11716571 graphs generated in 5.09 sec
Notice that 11716571 is the size for 10 from A001349
How to create file on Windows using WSL
Since WSL can access the Windows file system it is possible to direct the output from WSL commands to a Windows file, e.g.
touch /mnt/c/Users/Eric/graphs.txt
The touch step is not needed, but I use it to create an empty file first then verify that it is there on Windows to ensure I have typed the path correctly.
Here is an example that creates the graph edge list for A001349 in the users directory.
.geng -c 1 | .listg -e >> /mnt/c/Users/Eric/graphs.txt
.geng -c 2 | .listg -e >> /mnt/c/Users/Eric/graphs.txt
