/* Enumeration des chemins d'un graphe sans circuit */

/* Le graphe est donne' par le predicat "arc", ses sommets sont des
atomes */

chemin(0, Org, [Org]). /* "Org" comme "origine" */
chemin(R, Org, [Org|S]):- arc(Org, Next), RN is R-1,
					 chemin(RN, Next, S).
					 
lesChemins(R, Org, Liste) :- bagof(Ch, chemin(R, Org, Ch), Liste).

showChemins(R, Org) :- lesChemins(R, Org, Liste), lwrite(Liste).

lwrite([]) :- write('Et voila tout !').
lwrite([Ch|S]) :- write(Ch), nl, lwrite(S).
% mieux que  maplist(write, Liste) 

/* Premiere generation */

/* Le couple (a1, b1) a trois enfants a2, b2, c2 */
arc(a1, a2). arc(b1, a2). arc(a1, b2). arc(b1, b2).
arc(a1, c2). arc(b1, c2).
/* Le couple (x1, y1) en a deux x2, y2 */
arc(x1, x2). arc(y1, x2). arc(x1, y2). arc(y1, y2).
/* Le couple (u1, v1) en a deux u2, v2 */
arc(u1, u2). arc(v1, u2). arc(u1, v2). arc(v1, v2).
/* Le couple (z1, t1) en a un  t2 */
arc(z1, t2). arc(t1, t2). 

/* Deuxieme generation */

/* a2 avec y2 engendrent x3 et y3 */
arc(a2, x3). arc(y2, x3). arc(a2, y3).  arc(y2, y3).
/* b2 avec v2 engendrent u3 et v3 */
arc(b2, u3). arc(v2, u3). arc(b2, v3).  arc(v2, v3).
/* x2 avec c2 engendrent c3 et t3 */
arc(x2, c3). arc(c2, c3). arc(x2, t3). arc(c2, t3).
/* u2 avec t2 engendrent a3 et b3 */
arc(u2, a3). arc(t2, a3). arc(u2, b3).  arc(u2, b3).

/* Troisieme generation */

/* a3 avec y3 engendrent x4 et y4 */
arc(a3, x4). arc(y3, x4). arc(a3, y4).  arc(y3, y4).
/* b3 avec v3 engendrent u4 et v4 */
arc(b3, u4). arc(v3, u4). arc(b3, v4).  arc(v3, v4).
/* x3 avec c3 engendrent c4 et t4 */
arc(x3, c4). arc(c3, c4). arc(x3, t4). arc(c3, t4).
/* u3 avec t3 engendrent a4 et b4 */
arc(u3, a4). arc(t3, a4). arc(u3, b4).  arc(u3, b4).

/* Quatrieme generation */

/* a4 avec y4 engendrent x5 et y5 */
arc(a4, x5). arc(y4, x5). arc(a4, y5).  arc(y4, y5).
/* b4 avec v4 engendrent u5 et v5 */
arc(b4, u5). arc(v4, u5). arc(b4, v5).  arc(v4, v5).
/* x4 avec c4 engendrent c5 et t5 */
arc(x4, c5). arc(c4, c5). arc(x4, t5). arc(c4, t5).
/* u4 avec t4 engendrent a5 et b5 */
arc(u4, a5). arc(t4, a5). arc(u4, b5).  arc(u4, b5).

