Generate and Test accumulating valid answer for next test

Multi tool use
Multi tool use












3















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









share|improve this question

























  • Of interest: OEIS - Number of graphs on n labeled nodes - A006125

    – Guy Coder
    Dec 30 '18 at 21:25











  • Of interest: Combination calculator

    – Guy Coder
    Dec 30 '18 at 21:26











  • Of interest: collections of graphs - Did not need for this specific problem, but nice to know if you are working on graphs.

    – Guy Coder
    Dec 30 '18 at 21:27






  • 1





    Of interest: nauty and Traces - nauty and Traces are programs for computing automorphism groups of graphs and digraphs. Note about NAUTY

    – Guy Coder
    Dec 30 '18 at 21:29








  • 1





    Of iterest: The Stanford GraphBase - The Stanford GraphBase (SGB) is a collection of datasets and computer programs that generate and examine a wide variety of graphs and networks.” It was developed and published by Donald E. Knuth in 1993.

    – Guy Coder
    Dec 31 '18 at 13:27
















3















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









share|improve this question

























  • Of interest: OEIS - Number of graphs on n labeled nodes - A006125

    – Guy Coder
    Dec 30 '18 at 21:25











  • Of interest: Combination calculator

    – Guy Coder
    Dec 30 '18 at 21:26











  • Of interest: collections of graphs - Did not need for this specific problem, but nice to know if you are working on graphs.

    – Guy Coder
    Dec 30 '18 at 21:27






  • 1





    Of interest: nauty and Traces - nauty and Traces are programs for computing automorphism groups of graphs and digraphs. Note about NAUTY

    – Guy Coder
    Dec 30 '18 at 21:29








  • 1





    Of iterest: The Stanford GraphBase - The Stanford GraphBase (SGB) is a collection of datasets and computer programs that generate and examine a wide variety of graphs and networks.” It was developed and published by Donald E. Knuth in 1993.

    – Guy Coder
    Dec 31 '18 at 13:27














3












3








3








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









share|improve this question
















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






prolog graph-theory data-generation






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Jan 1 at 23:31







Guy Coder

















asked Dec 30 '18 at 20:44









Guy CoderGuy Coder

15.4k43983




15.4k43983













  • Of interest: OEIS - Number of graphs on n labeled nodes - A006125

    – Guy Coder
    Dec 30 '18 at 21:25











  • Of interest: Combination calculator

    – Guy Coder
    Dec 30 '18 at 21:26











  • Of interest: collections of graphs - Did not need for this specific problem, but nice to know if you are working on graphs.

    – Guy Coder
    Dec 30 '18 at 21:27






  • 1





    Of interest: nauty and Traces - nauty and Traces are programs for computing automorphism groups of graphs and digraphs. Note about NAUTY

    – Guy Coder
    Dec 30 '18 at 21:29








  • 1





    Of iterest: The Stanford GraphBase - The Stanford GraphBase (SGB) is a collection of datasets and computer programs that generate and examine a wide variety of graphs and networks.” It was developed and published by Donald E. Knuth in 1993.

    – Guy Coder
    Dec 31 '18 at 13:27



















  • Of interest: OEIS - Number of graphs on n labeled nodes - A006125

    – Guy Coder
    Dec 30 '18 at 21:25











  • Of interest: Combination calculator

    – Guy Coder
    Dec 30 '18 at 21:26











  • Of interest: collections of graphs - Did not need for this specific problem, but nice to know if you are working on graphs.

    – Guy Coder
    Dec 30 '18 at 21:27






  • 1





    Of interest: nauty and Traces - nauty and Traces are programs for computing automorphism groups of graphs and digraphs. Note about NAUTY

    – Guy Coder
    Dec 30 '18 at 21:29








  • 1





    Of iterest: The Stanford GraphBase - The Stanford GraphBase (SGB) is a collection of datasets and computer programs that generate and examine a wide variety of graphs and networks.” It was developed and published by Donald E. Knuth in 1993.

    – Guy Coder
    Dec 31 '18 at 13:27

















Of interest: OEIS - Number of graphs on n labeled nodes - A006125

– Guy Coder
Dec 30 '18 at 21:25





Of interest: OEIS - Number of graphs on n labeled nodes - A006125

– Guy Coder
Dec 30 '18 at 21:25













Of interest: Combination calculator

– Guy Coder
Dec 30 '18 at 21:26





Of interest: Combination calculator

– Guy Coder
Dec 30 '18 at 21:26













Of interest: collections of graphs - Did not need for this specific problem, but nice to know if you are working on graphs.

– Guy Coder
Dec 30 '18 at 21:27





Of interest: collections of graphs - Did not need for this specific problem, but nice to know if you are working on graphs.

– Guy Coder
Dec 30 '18 at 21:27




1




1





Of interest: nauty and Traces - nauty and Traces are programs for computing automorphism groups of graphs and digraphs. Note about NAUTY

– Guy Coder
Dec 30 '18 at 21:29







Of interest: nauty and Traces - nauty and Traces are programs for computing automorphism groups of graphs and digraphs. Note about NAUTY

– Guy Coder
Dec 30 '18 at 21:29






1




1





Of iterest: The Stanford GraphBase - The Stanford GraphBase (SGB) is a collection of datasets and computer programs that generate and examine a wide variety of graphs and networks.” It was developed and published by Donald E. Knuth in 1993.

– Guy Coder
Dec 31 '18 at 13:27





Of iterest: The Stanford GraphBase - The Stanford GraphBase (SGB) is a collection of datasets and computer programs that generate and examine a wide variety of graphs and networks.” It was developed and published by Donald E. Knuth in 1993.

– Guy Coder
Dec 31 '18 at 13:27












1 Answer
1






active

oldest

votes


















2














In the SWI-Prolog you can store values in global vars:




  1. backtrackable b: b_setval, b_getval

  2. not backtrackable nb: nb_setval, nb_getval


besides using dynamic predicates: assert/retract.



item(1).
item(1).
item(2).
item(3).
item(1).
item(7).
item(1).
item(4).


Solution 1 using regular list



gen_test(Item) :-
nb_setval(sofar, ),
item(Item), % generate
once(
(
nb_getval(sofar, SoFar),
(Item > 1, + member(Item, SoFar)), % test custom + on membership in earlier tests
nb_setval(sofar, [Item | SoFar])
)
;
true
),
fail; true.


Solution 2 using open list



 gen_test1(Item) :-
(
item(Item), % generate
Item > 1, lookup(Item, SoFar, ItemExists)),
ItemExists == true -> fail; true
);
append(SoFar, , SoFar ), % stubbing open list
nb_setval(sofar, Sofar).

lookup( I, [ I | _ ], true).
lookup( I, [ _ | L ], false) :-
var( L ); L == .
lookup( I, [ _ | L ] ItemExists ):-
lookup( I, L, ItemExists ).





share|improve this answer


























  • Of interest: Open Lists and Difference Lists

    – Guy Coder
    Jan 27 at 12:41











  • @GuyCoder excuse me I've killed all prologs on my computer, so I can do only menthal debugging a little while by now....>>For gen_test I added a , after (Item > 1, + member(Item, SoFar)) to get the code to load with consult/1 but upon running the result was false. I just guessed what the point; it needs to remove + before member/2. it;'s always succeded when openlists used

    – Anton Danilov
    Jan 27 at 16:28













  • @GuyCoder you simply needed tabling feature: table item/1. it should memoize non-duplicated goals. After each test you need to store results and cleanup table(s). it's near to 1st example with regular (proper) list.

    – Anton Danilov
    Jan 29 at 14:25











  • Of interest: SWI-Prolog Tabled execution (SLG resolution)

    – Guy Coder
    Jan 29 at 14:30






  • 1





    Of interest: SWI-Prolog Delimited continuations

    – Guy Coder
    Jan 29 at 14:38











Your Answer






StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53981280%2fgenerate-and-test-accumulating-valid-answer-for-next-test%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









2














In the SWI-Prolog you can store values in global vars:




  1. backtrackable b: b_setval, b_getval

  2. not backtrackable nb: nb_setval, nb_getval


besides using dynamic predicates: assert/retract.



item(1).
item(1).
item(2).
item(3).
item(1).
item(7).
item(1).
item(4).


Solution 1 using regular list



gen_test(Item) :-
nb_setval(sofar, ),
item(Item), % generate
once(
(
nb_getval(sofar, SoFar),
(Item > 1, + member(Item, SoFar)), % test custom + on membership in earlier tests
nb_setval(sofar, [Item | SoFar])
)
;
true
),
fail; true.


Solution 2 using open list



 gen_test1(Item) :-
(
item(Item), % generate
Item > 1, lookup(Item, SoFar, ItemExists)),
ItemExists == true -> fail; true
);
append(SoFar, , SoFar ), % stubbing open list
nb_setval(sofar, Sofar).

lookup( I, [ I | _ ], true).
lookup( I, [ _ | L ], false) :-
var( L ); L == .
lookup( I, [ _ | L ] ItemExists ):-
lookup( I, L, ItemExists ).





share|improve this answer


























  • Of interest: Open Lists and Difference Lists

    – Guy Coder
    Jan 27 at 12:41











  • @GuyCoder excuse me I've killed all prologs on my computer, so I can do only menthal debugging a little while by now....>>For gen_test I added a , after (Item > 1, + member(Item, SoFar)) to get the code to load with consult/1 but upon running the result was false. I just guessed what the point; it needs to remove + before member/2. it;'s always succeded when openlists used

    – Anton Danilov
    Jan 27 at 16:28













  • @GuyCoder you simply needed tabling feature: table item/1. it should memoize non-duplicated goals. After each test you need to store results and cleanup table(s). it's near to 1st example with regular (proper) list.

    – Anton Danilov
    Jan 29 at 14:25











  • Of interest: SWI-Prolog Tabled execution (SLG resolution)

    – Guy Coder
    Jan 29 at 14:30






  • 1





    Of interest: SWI-Prolog Delimited continuations

    – Guy Coder
    Jan 29 at 14:38
















2














In the SWI-Prolog you can store values in global vars:




  1. backtrackable b: b_setval, b_getval

  2. not backtrackable nb: nb_setval, nb_getval


besides using dynamic predicates: assert/retract.



item(1).
item(1).
item(2).
item(3).
item(1).
item(7).
item(1).
item(4).


Solution 1 using regular list



gen_test(Item) :-
nb_setval(sofar, ),
item(Item), % generate
once(
(
nb_getval(sofar, SoFar),
(Item > 1, + member(Item, SoFar)), % test custom + on membership in earlier tests
nb_setval(sofar, [Item | SoFar])
)
;
true
),
fail; true.


Solution 2 using open list



 gen_test1(Item) :-
(
item(Item), % generate
Item > 1, lookup(Item, SoFar, ItemExists)),
ItemExists == true -> fail; true
);
append(SoFar, , SoFar ), % stubbing open list
nb_setval(sofar, Sofar).

lookup( I, [ I | _ ], true).
lookup( I, [ _ | L ], false) :-
var( L ); L == .
lookup( I, [ _ | L ] ItemExists ):-
lookup( I, L, ItemExists ).





share|improve this answer


























  • Of interest: Open Lists and Difference Lists

    – Guy Coder
    Jan 27 at 12:41











  • @GuyCoder excuse me I've killed all prologs on my computer, so I can do only menthal debugging a little while by now....>>For gen_test I added a , after (Item > 1, + member(Item, SoFar)) to get the code to load with consult/1 but upon running the result was false. I just guessed what the point; it needs to remove + before member/2. it;'s always succeded when openlists used

    – Anton Danilov
    Jan 27 at 16:28













  • @GuyCoder you simply needed tabling feature: table item/1. it should memoize non-duplicated goals. After each test you need to store results and cleanup table(s). it's near to 1st example with regular (proper) list.

    – Anton Danilov
    Jan 29 at 14:25











  • Of interest: SWI-Prolog Tabled execution (SLG resolution)

    – Guy Coder
    Jan 29 at 14:30






  • 1





    Of interest: SWI-Prolog Delimited continuations

    – Guy Coder
    Jan 29 at 14:38














2












2








2







In the SWI-Prolog you can store values in global vars:




  1. backtrackable b: b_setval, b_getval

  2. not backtrackable nb: nb_setval, nb_getval


besides using dynamic predicates: assert/retract.



item(1).
item(1).
item(2).
item(3).
item(1).
item(7).
item(1).
item(4).


Solution 1 using regular list



gen_test(Item) :-
nb_setval(sofar, ),
item(Item), % generate
once(
(
nb_getval(sofar, SoFar),
(Item > 1, + member(Item, SoFar)), % test custom + on membership in earlier tests
nb_setval(sofar, [Item | SoFar])
)
;
true
),
fail; true.


Solution 2 using open list



 gen_test1(Item) :-
(
item(Item), % generate
Item > 1, lookup(Item, SoFar, ItemExists)),
ItemExists == true -> fail; true
);
append(SoFar, , SoFar ), % stubbing open list
nb_setval(sofar, Sofar).

lookup( I, [ I | _ ], true).
lookup( I, [ _ | L ], false) :-
var( L ); L == .
lookup( I, [ _ | L ] ItemExists ):-
lookup( I, L, ItemExists ).





share|improve this answer















In the SWI-Prolog you can store values in global vars:




  1. backtrackable b: b_setval, b_getval

  2. not backtrackable nb: nb_setval, nb_getval


besides using dynamic predicates: assert/retract.



item(1).
item(1).
item(2).
item(3).
item(1).
item(7).
item(1).
item(4).


Solution 1 using regular list



gen_test(Item) :-
nb_setval(sofar, ),
item(Item), % generate
once(
(
nb_getval(sofar, SoFar),
(Item > 1, + member(Item, SoFar)), % test custom + on membership in earlier tests
nb_setval(sofar, [Item | SoFar])
)
;
true
),
fail; true.


Solution 2 using open list



 gen_test1(Item) :-
(
item(Item), % generate
Item > 1, lookup(Item, SoFar, ItemExists)),
ItemExists == true -> fail; true
);
append(SoFar, , SoFar ), % stubbing open list
nb_setval(sofar, Sofar).

lookup( I, [ I | _ ], true).
lookup( I, [ _ | L ], false) :-
var( L ); L == .
lookup( I, [ _ | L ] ItemExists ):-
lookup( I, L, ItemExists ).






share|improve this answer














share|improve this answer



share|improve this answer








edited Jan 29 at 14:52

























answered Jan 22 at 13:20









Anton DanilovAnton Danilov

731618




731618













  • Of interest: Open Lists and Difference Lists

    – Guy Coder
    Jan 27 at 12:41











  • @GuyCoder excuse me I've killed all prologs on my computer, so I can do only menthal debugging a little while by now....>>For gen_test I added a , after (Item > 1, + member(Item, SoFar)) to get the code to load with consult/1 but upon running the result was false. I just guessed what the point; it needs to remove + before member/2. it;'s always succeded when openlists used

    – Anton Danilov
    Jan 27 at 16:28













  • @GuyCoder you simply needed tabling feature: table item/1. it should memoize non-duplicated goals. After each test you need to store results and cleanup table(s). it's near to 1st example with regular (proper) list.

    – Anton Danilov
    Jan 29 at 14:25











  • Of interest: SWI-Prolog Tabled execution (SLG resolution)

    – Guy Coder
    Jan 29 at 14:30






  • 1





    Of interest: SWI-Prolog Delimited continuations

    – Guy Coder
    Jan 29 at 14:38



















  • Of interest: Open Lists and Difference Lists

    – Guy Coder
    Jan 27 at 12:41











  • @GuyCoder excuse me I've killed all prologs on my computer, so I can do only menthal debugging a little while by now....>>For gen_test I added a , after (Item > 1, + member(Item, SoFar)) to get the code to load with consult/1 but upon running the result was false. I just guessed what the point; it needs to remove + before member/2. it;'s always succeded when openlists used

    – Anton Danilov
    Jan 27 at 16:28













  • @GuyCoder you simply needed tabling feature: table item/1. it should memoize non-duplicated goals. After each test you need to store results and cleanup table(s). it's near to 1st example with regular (proper) list.

    – Anton Danilov
    Jan 29 at 14:25











  • Of interest: SWI-Prolog Tabled execution (SLG resolution)

    – Guy Coder
    Jan 29 at 14:30






  • 1





    Of interest: SWI-Prolog Delimited continuations

    – Guy Coder
    Jan 29 at 14:38

















Of interest: Open Lists and Difference Lists

– Guy Coder
Jan 27 at 12:41





Of interest: Open Lists and Difference Lists

– Guy Coder
Jan 27 at 12:41













@GuyCoder excuse me I've killed all prologs on my computer, so I can do only menthal debugging a little while by now....>>For gen_test I added a , after (Item > 1, + member(Item, SoFar)) to get the code to load with consult/1 but upon running the result was false. I just guessed what the point; it needs to remove + before member/2. it;'s always succeded when openlists used

– Anton Danilov
Jan 27 at 16:28







@GuyCoder excuse me I've killed all prologs on my computer, so I can do only menthal debugging a little while by now....>>For gen_test I added a , after (Item > 1, + member(Item, SoFar)) to get the code to load with consult/1 but upon running the result was false. I just guessed what the point; it needs to remove + before member/2. it;'s always succeded when openlists used

– Anton Danilov
Jan 27 at 16:28















@GuyCoder you simply needed tabling feature: table item/1. it should memoize non-duplicated goals. After each test you need to store results and cleanup table(s). it's near to 1st example with regular (proper) list.

– Anton Danilov
Jan 29 at 14:25





@GuyCoder you simply needed tabling feature: table item/1. it should memoize non-duplicated goals. After each test you need to store results and cleanup table(s). it's near to 1st example with regular (proper) list.

– Anton Danilov
Jan 29 at 14:25













Of interest: SWI-Prolog Tabled execution (SLG resolution)

– Guy Coder
Jan 29 at 14:30





Of interest: SWI-Prolog Tabled execution (SLG resolution)

– Guy Coder
Jan 29 at 14:30




1




1





Of interest: SWI-Prolog Delimited continuations

– Guy Coder
Jan 29 at 14:38





Of interest: SWI-Prolog Delimited continuations

– Guy Coder
Jan 29 at 14:38


















draft saved

draft discarded




















































Thanks for contributing an answer to Stack Overflow!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53981280%2fgenerate-and-test-accumulating-valid-answer-for-next-test%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







xYMlVjOFupn qWz17l,k8VhAUEZ,gyI,h5TkF542kw4vj
XInWrV8vEFeOIcRa,MBv,aH qTG Cnmi,JC1IjbxPkzNHE1Q8q

Popular posts from this blog

Monofisismo

Angular Downloading a file using contenturl with Basic Authentication

Olmecas