[rules-users] Re: transitive closure

[Paul Fodor]

On Thu, Jul 3, 2008 at 3:56 PM, Paul Fodor <paul.i.fodor at gmail.com> wrote:
> Dear Sir,
>
> I am new to Drools and I want to ask how can I implement the classical
> transitive closure in Drools. For instance we have a bunch of facts
> edge/2 and the transitive closure:
>
> reach(X,Y):- edge(X,Y).
> reach(X,Y):- edge(X,Z),reach(Z,Y).

My current version looks like the following, but it never terminates.
It re-derives reach(c,c) forever.

TransitiveClosure.drl :
package org.drools.examples

import org.drools.examples.TransitiveClosureExample.Edge;
import org.drools.examples.TransitiveClosureExample.Reach;

rule "reachDirect"
    salience 10
    when
        e : Edge(s1 : source, t1 : target)
        not( Reach(source == s1, target == t1) )
    then
        insertLogical( new Reach(e.getSource(),e.getTarget()) );
        System.out.println( "Reach " + e.getSource() + "," + e.getTarget() );
end

rule "reachIndirect"
    salience 10
    when
        e : Edge(s1 : source, t1 : target)
        r : Reach(t2 : target, source == t1 )
        not( Reach(source == s1, target == t2) )
    then
        insertLogical( new Reach(e.getSource(),r.getTarget()) );
        System.out.println( "Reach " + e.getSource() + "," + r.getTarget() );
end

TransitiveClosureExample.java :

package org.drools.examples;
import java.io.InputStreamReader;
import org.drools.RuleBase;
import org.drools.RuleBaseFactory;
import org.drools.StatefulSession;
import org.drools.audit.WorkingMemoryFileLogger;
import org.drools.compiler.PackageBuilder;
import org.drools.compiler.PackageBuilderConfiguration;

public class TransitiveClosureExample {
    public static void main(final String[] args) throws Exception {
        PackageBuilderConfiguration conf = new PackageBuilderConfiguration();
        final PackageBuilder builder = new PackageBuilder( conf );
        builder.addPackageFromDrl( new InputStreamReader(
TransitiveClosureExample.class.getResourceAsStream(
"TransitiveClosure.drl" ) ) );
        final RuleBase ruleBase = RuleBaseFactory.newRuleBase();
        ruleBase.addPackage( builder.getPackage() );
        final StatefulSession session = ruleBase.newStatefulSession();
        final WorkingMemoryFileLogger logger = new
WorkingMemoryFileLogger( session );
        logger.setFileName( "log/transitiveClosure" );

        final Edge edgeAB = new Edge( "a","b" );
        final Edge edgeBC = new Edge( "b","c" );
        final Edge edgeCD = new Edge( "c","d" );

        session.insert( edgeAB );
        session.insert( edgeBC );
        session.insert( edgeCD );

        session.fireAllRules();
        logger.writeToDisk();
        session.dispose();
    }

    public static class Edge {
        private String source;
        private String target;
        public Edge() {}
        public Edge(String source, String target) {
            super();
            this.source = source;
            this.target = target;
        }
        public String getSource() {
            return source;
        }
        public String getTarget() {
            return source;
        }
    }

    public static class Reach {
        private String source;
        private String target;
        public Reach() {}
        public Reach(String source, String target) {
            super();
            this.source = source;
            this.target = target;
        }
        public void setSource(String source) {
            this.source = source;
        }
        public String getSource() {
            return source;
        }
        public void setTarget(String target) {
            this.target = target;
        }
        public String getTarget() {
            return target;
        }
    }
}

Any sugestion?

Regards,
 Paul Fodor