PROLOG - printing every graph component's nodes

Question

I'm absolute newbie in Prolog and I'm struggling with this task:

"There is given a discontinuous graph on the input. Write Prolog program which on the output prints lists of every nodes of each graph component.:

Discontinuous graph on the input is represented by it's edges for example like this:

e(1,2).
e(2,4).
e(2,5).
e(3,6).
e(3,7).
e(7,8).

That means this particular graph have two components and on the output should be something like this:

[1,2,4,5],
[3,6,7,8].

I found on the net solution for similar problem - printing all graph nodes (http://www.tek-tips.com/viewthread.cfm?qid=1602084), but I can't even figure out how to modify this to apply it on my task to print each component of a discontinuous graph separately.

Thanks for any idea.

Try thinking of an algorithm, expressing it in ways that suit logic programming, try to write some clauses and then ask for help. — Tudor Berariu

CapelliC CapelliC · Accepted Answer · 2015-01-12T00:38:35

connected_components(Cs) :-
    findall([X,Y], e(X,Y), Pairs),
    connect(Pairs, Cs).

connect(Ls, Cs) :-
    select(A, Ls, Rs),
    select(B, Rs, Ts),
    /* check if A & B can be merged in a list */
    !, connect([U|Ts], Cs).
connect(Cs, Cs).

My idea it's to start with all lists, then loop keep merging while there is some element sharing. It's a fixpoint computation. In Prolog, such code can be very compact, using library(lists).

I've 'hidden' two set operations calls (and 1 inequality), where you see the pseudocode /* check etc */ Hope you are interested in discovering such calls in the above library.

The output:

?- connected_components(Cs).
Cs = [[6, 3, 7, 8], [1, 4, 2, 5]].

PROLOG - printing every graph component's nodes

1 Answers