% P94 (**) Generate K-regular simple graphs with N nodes. % % In a K-regular graph all nodes have a degree of K. % k_regular(K,N,Graph) :- Graph is a K-regular simple graph with N nodes. % The graph is in graph-term form. The nodes are identified by numbers 1..N. % All solutions can be generated via backtracking. % (+,+,?) (int,int,graph(nodes,edges)) % % Note: The predicate generates the Nodes list and a list of terms u(V,F) % which indicates, for each node V, the number F of unused (or free) edges. % For example: with N=5, K=3 the algorithm starts with Nodes=[1,2,3,4,5] % and UList=[u(1,3),u(2,3),u(3,3),u(4,3),u(5,3)]. k_regular(K,N,graph(Nodes,Edges)) :- range(1,N,Nodes), % generate Nodes list maplist(mku(K),Nodes,UList), % generate initial UList k_reg(UList,0,Edges). mku(K,V,u(V,K)). % k_reg(UList,MinY,Edges) :- Edges is a list of e(X,Y) terms where u(X,UX) % is the first element in UList and u(Y,UY) is another element of UList, % with Y > MinY. Both UX and UY, which indicate the number of free edges % of X and Y, respectively, must be greater than 0. They are both reduced % by 1 for the recursion if the edge e(X,Y) is chosen. % (+,+,-) (ulist,int,elist) k_reg([],_,[]). k_reg([u(_,0)|Us],_,Edges) :- !, k_reg(Us,0,Edges). % no more unused edges k_reg([u(1,UX)|Us],MinY,[e(1,Y)|Edges]) :- UX > 0, % special case X = 1 pick(Us,Y,MinY,Us1), !, % pick a Y UX1 is UX - 1, % reduce number of unused edges k_reg([u(1,UX1)|Us1],Y,Edges). k_reg([u(X,UX)|Us],MinY,[e(X,Y)|Edges]) :- X > 1, UX > 0, pick(Us,Y,MinY,Us1), % pick a Y UX1 is UX - 1, % reduce number of unused edges k_reg([u(X,UX1)|Us1],Y,Edges). % pick(UList_in,Y,MinY,UList_out) :- there is an element u(Y,UY) in UList_in, % Y is greater than MinY, and UY > 0. UList_out is obtained from UList_in % by reducing UY by 1 in the term u(Y,_). This predicate delivers all % possible values of Y via backtracking. % (+,-,+,-) (ulist,int,int,ulist) pick([u(Y,UY)|Us],Y,MinY,[u(Y,UY1)|Us]) :- Y > MinY, UY > 0, UY1 is UY - 1. pick([U|Us],Y,MinY,[U|Us1]) :- pick(Us,Y,MinY,Us1). % range(X,Y,Ls) :- Ls is the list of the integer numbers from X to Y. % (+,+,?) (int,int,int_list) range(B,B,[B]). range(A,B,[A|L]) :- A < B, A1 is A + 1, range(A1,B,L). :- dynamic solution/1. % all_k_regular(K,N,Gs) :- Gs is the list of all (non-isomorphic) % K-regular graphs with N nodes. % (+,+,-) (int,int,list_of_graphs) % Note: The predicate prints each new solution as a progress report. % Use tell('/dev/null') to switch off the printing if you don't like it. all_k_regular(K,N,_) :- retractall(solution(_)), k_regular(K,N,Graph), no_iso_solution(Graph), write(Graph), nl, assert(solution(Graph)), fail. all_k_regular(_,_,Graphs) :- findall(G,solution(G),Graphs). :- ensure_loaded(p85). % load isomorphic/2 % no_iso_solution(Graph) :- there is no graph G in the solution/1 data base % predicate which is isomorphic to Graph no_iso_solution(Graph) :- solution(G), isomorphic(Graph,G), !, fail. no_iso_solution(_). % The rest of this program constructs a table of K-regular simple graphs % with N nodes for N up to a maximum N and sensible values of K. % Example: ?- table(6). table(Max) :- nl, write('K-regular simple graphs with N nodes'), nl, table(3,Max). table(N,Max) :- N =< Max, !, table(2,N,Max), N1 is N + 1, table(N1,Max). table(_,_) :- nl. table(K,N,Max) :- K < N, !, tell('/dev/null'), statistics(inferences,I1), all_k_regular(K,N,Gs), length(Gs,NSol), statistics(inferences,I2), NInf is I2 - I1, told, plural(NSol,Pl), writef('\nN = %w K = %w %w solution%w (%w inferences)\n',[N,K,NSol,Pl,NInf]), checklist(print_graph,Gs), K1 is K + 1, table(K1,N,Max). table(_,_,_) :- nl. plural(X,' ') :- X < 2, !. plural(_,'s'). :- ensure_loaded(p80). % conversion human_gterm/2 print_graph(G) :- human_gterm(HF,G), write(HF), nl.