# Complete graph traversal algorithm in Prolog

Given a table, I want to explore all possible transition between the elements in the table. ex: for a table with size 3 [0,1,2], the output of the algorithm should be 0->1, 1->0, 0->2, 2->1, 1->2, 2->0. I guess this can be regarded as traversing a complete graph.

I have an implementation of an algorithm doing this in Python:

def test1(n):
theList=[]
theList.append(0)

for x in range(0,n+1):
for y in range(n,x+1,-1):
theList.append(y)
theList.append(x)

if x!=n:
theList.append(x+1)

for x in range(n,0,-1):
theList.append(x-1)
return theList


This code always start at element 0, and return a list of all the transitions.

But I need my algorithm i Prolog. So I have done an attempt to port the Python-code to Prolog. My main focus has been on writing readable and maintainable code. But I guess there is great room for improvement wrt. performance of the Prolog code:

:- use_module(library(clpfd)).
:- use_module(library(between)).
:- use_module(library(lists)).

dynappend( List, X ) :-
(
foreach( Item, List ),
param(X,T)
do
var( Item ), var(T) ->
Item = X ,
T = 1
;
true
).

s3(List,N):-
LSize is N*(N+1)+1,
length(List,LSize),

dynappend( List, 0 ),
(
for(X1, 0, N ),
param( N, List )
do
X1T is X1+2,
( between:numlist( X1T, N, YList ) -> true ; YList=[] ) ,
lists:reverse(YList,RYList),

(
foreach(Y, RYList ),
param( X1, List )
do
dynappend( List, Y ),
dynappend( List, X1 )
),

(   X1 #\= N -> X1T2 is X1+1, dynappend( List, X1T2 ) ;  true )
),
N1 is N-1,
numlist( 0, N1, XList ),
lists:reverse(XList,RXList),
(
foreach(X2, RXList ),
param(List)
do
dynappend( List, X2 )
).


Running the code:

| ?- s3(L, 2).
L = [0,2,0,1,2,1,0] ?
yes


Any suggestions for improvements of the Prolog code?

• if you get the habit to use 'yield' in Python, you will end with much more Prolog like code, very similar to what @Mat shows – CapelliC Jul 25 '13 at 9:30
• If someone suggests that a question belongs to codereview.SE please flag/ask a moderator to move it next time. Make a comment to move the question if you can't see the flag button and someone else will flag it. Posting the same question on both sites isn't considered good. Just wait a bit. – Aseem Bansal Jul 31 '13 at 14:31

Consider describing what a transition is:

list_transition(List, (E1->E2)) :-
select(E1, List, Rest),
member(E2, Rest).


Example query:

?- list_transition([0,1,2], T).
T = (0->1) ;
T = (0->2) ;
T = (1->0) ;
T = (1->2) ;
T = (2->0) ;
T = (2->1) ;
false.


And to get all transitions:

?- findall(T, list_transition([0,1,2], T), Transitions).
Transitions = [ (0->1), (0->2), (1->0), (1->2), (2->0), (2->1)].