%% loops.lp -- ASP version of solution to additional exercise on
%% basic loops.
%% Last Modified: 4/21/14
%% A path is called basic if it contains no repetions of loops.
%% Find all basic loops in a directed graph.
%% Hint: A path consisting of links of the form in(X,Y) is a basic loop iff
%% all its nodes are connected with each other.
#const n = 3.
node(1..n).
% Input graph (change at will):
edge(1,2).
edge(2,1).
edge(1,3).
edge(3,1).
% Definitions of nodes of a loop and the notion
% of connected nodes in terms of in(X,Y)
loop_node(X) :-
in(X,Y).
loop_node(X) :-
in(Y,X).
connected(X,Y) :-
in(X,Y).
connected(X,Y) :-
in(X,Z),
connected(Z,Y).
% Generate
in(X,Y) | -in(X,Y) :-
edge(X,Y).
% Test
:- loop_node(X),
loop_node(Y),
not connected(X,Y).
%% Output formating of clingo:
%#show in/2.
%% or use -pfilter=in as an inline option with dlv