%% s_loops.sp -- SPARC 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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% sorts #node = [1..n]. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% predicates edge(#node,#node). in(#node,#node). loop_node(#node). connected(#node,#node). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% rules % 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).