Generate and Test accumulating valid answer for next test

Multi tool use
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
|
show 21 more comments
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
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
|
show 21 more comments
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
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
prolog graph-theory data-generation
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
|
show 21 more comments
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
|
show 21 more comments
1 Answer
1
active
oldest
votes
In the SWI-Prolog you can store values in global vars:
- backtrackable
b
:b_setval
,b_getval
- 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 ).
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
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
In the SWI-Prolog you can store values in global vars:
- backtrackable
b
:b_setval
,b_getval
- 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 ).
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
add a comment |
In the SWI-Prolog you can store values in global vars:
- backtrackable
b
:b_setval
,b_getval
- 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 ).
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
add a comment |
In the SWI-Prolog you can store values in global vars:
- backtrackable
b
:b_setval
,b_getval
- 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 ).
In the SWI-Prolog you can store values in global vars:
- backtrackable
b
:b_setval
,b_getval
- 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 ).
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
add a comment |
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
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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