package org.fenfire.util.lava; import org.fenfire.swamp.ConstGraph; import java.util.Set; import java.util.HashSet; import java.util.Iterator; /** This class contains utility methods for Swamp RDF graph traversal. */ public class Traversals { /** Signals a search collision. */ static class CollisionException extends Exception { } /** Tests whether a given nondirected property connects the two nodes given. The method is to run BFS from both nodes simultaneously and see whether they collide. */ public static boolean isConnected(Object a, Object property, Object b, ConstGraph g) { if(a == b) return true; // A node is always connected to itself Set visited1 = new HashSet(); Set visited2 = new HashSet(); Set active1 = new HashSet(); Set active2 = new HashSet(); // Initialize the searches active1.add(a); active2.add(b); while(!active1.isEmpty() && !active2.isEmpty()) { try { // Advance both searches from one active set to the next active1 = iterateActive(active1.iterator(), g, property, visited1, new HashSet(), visited2); active2 = iterateActive(active2.iterator(), g, property, visited2, new HashSet(), visited1); } catch (CollisionException _) { return true; // Collision means there is a connection } } // One of the searches died out, so there is no connection return false; } /** Iterates active nodes to get the next active set. */ static Set iterateActive(Iterator active, ConstGraph g, Object property, Set visited, Set activated, Set obstacles) throws CollisionException { while(active.hasNext()) { Object node = active.next(); iterateConns(g.findN_11X_Iter(node, property), visited, activated, obstacles); iterateConns(g.findN_X11_Iter(property, node), visited, activated, obstacles); } return activated; } /** Iterates connections from some node to visit new nodes. */ static void iterateConns(Iterator conns, Set visited, Set activated, Set obstacles) throws CollisionException { while(conns.hasNext()) { Object found = conns.next(); if(obstacles.contains(found)) throw new CollisionException(); if(!visited.contains(found)) { activated.add(found); visited.add(found); } } } }