Ruleset { public boolean pathExists(Rule r1, Rule r2) { if (r1 == null || r2 == null) { return false; } Set<Rule> forwardFrontier = new HashSet<>(); Set<Rule> backwardFrontier = new HashSet<>(); Set<Rule> visitedForward = new HashSet<>(); Set<Rule> visitedBackward = new HashSet<>(); forwardFrontier.addAll(getSuccessorsOf(r1)); backwardFrontier.add(r2); while (!forwardFrontier.isEmpty() && !backwardFrontier.isEmpty()) { Set<Rule> currentGoals = new HashSet<>(backwardFrontier); for (Rule goal : currentGoals) { if (forwardFrontier.contains(goal)) { return true; } else { visitedBackward.add(goal); backwardFrontier.addAll(getPredecessorsOf(goal)); } } backwardFrontier.removeAll(visitedBackward); Set<Rule> currentSources = new HashSet<>(forwardFrontier); for (Rule source : currentSources) { if (backwardFrontier.contains(source)) { return true; } else { visitedForward.add(source); forwardFrontier.addAll(getSuccessorsOf(source)); } } forwardFrontier.removeAll(visitedForward); } return false; } Ruleset(Collection<Rule> rules); Set<Rule> getRules(); Collection<Rule> getSuccessorsOf(Rule precedingRule); Collection<Rule> getPredecessorsOf(Rule dependentRule); boolean pathExists(Rule r1, Rule r2);  }
@Test public void testIndirectDependencies() { StatementPattern genericSP = new StatementPattern(new Var("a"), new Var("b"), new Var("c")); StatementPattern typeSP = new StatementPattern(new Var("x"), c(RDF.TYPE), new Var("t")); StatementPattern scoSP = new StatementPattern(new Var("x"), c(RDFS.SUBCLASSOF), new Var("y")); StatementPattern spoSP = new StatementPattern(new Var("x"), c(RDFS.SUBPROPERTYOF), new Var("y")); Rule typeTriggersAny = new TestRule( Sets.newHashSet(typeSP), Sets.newHashSet(genericSP, typeSP, scoSP)); Rule subclassTriggersType = new TestRule( Sets.newHashSet(scoSP), Sets.newHashSet(genericSP, typeSP)); Rule anyTriggersNothing = new TestRule( Sets.newHashSet(genericSP), Sets.newHashSet()); Rule typeTriggersSubprop = new TestRule( Sets.newHashSet(typeSP), Sets.newHashSet(genericSP, spoSP)); Set<Rule> allRules = Sets.newHashSet(anyTriggersNothing, subclassTriggersType, typeTriggersAny, typeTriggersSubprop); Ruleset ruleset = new Ruleset(allRules); Assert.assertTrue(ruleset.pathExists(typeTriggersAny, typeTriggersAny)); Assert.assertTrue(ruleset.pathExists(typeTriggersAny, subclassTriggersType)); Assert.assertTrue(ruleset.pathExists(typeTriggersAny, anyTriggersNothing)); Assert.assertTrue(ruleset.pathExists(typeTriggersAny, typeTriggersSubprop)); Assert.assertTrue(ruleset.pathExists(subclassTriggersType, typeTriggersAny)); Assert.assertTrue(ruleset.pathExists(subclassTriggersType, subclassTriggersType)); Assert.assertTrue(ruleset.pathExists(subclassTriggersType, anyTriggersNothing)); Assert.assertTrue(ruleset.pathExists(subclassTriggersType, typeTriggersSubprop)); Assert.assertFalse(ruleset.pathExists(anyTriggersNothing, typeTriggersAny)); Assert.assertFalse(ruleset.pathExists(anyTriggersNothing, subclassTriggersType)); Assert.assertFalse(ruleset.pathExists(anyTriggersNothing, anyTriggersNothing)); Assert.assertFalse(ruleset.pathExists(anyTriggersNothing, typeTriggersSubprop)); Assert.assertFalse(ruleset.pathExists(typeTriggersSubprop, typeTriggersAny)); Assert.assertFalse(ruleset.pathExists(typeTriggersSubprop, subclassTriggersType)); Assert.assertTrue(ruleset.pathExists(typeTriggersSubprop, anyTriggersNothing)); Assert.assertFalse(ruleset.pathExists(typeTriggersSubprop, typeTriggersSubprop)); }