001/** 002 * Copyright (C) 2007 - 2016, Jens Lehmann 003 * 004 * This file is part of DL-Learner. 005 * 006 * DL-Learner is free software; you can redistribute it and/or modify 007 * it under the terms of the GNU General Public License as published by 008 * the Free Software Foundation; either version 3 of the License, or 009 * (at your option) any later version. 010 * 011 * DL-Learner is distributed in the hope that it will be useful, 012 * but WITHOUT ANY WARRANTY; without even the implied warranty of 013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 014 * GNU General Public License for more details. 015 * 016 * You should have received a copy of the GNU General Public License 017 * along with this program. If not, see <http://www.gnu.org/licenses/>. 018 */ 019package org.dllearner.algorithms.qtl.operations.lcs; 020 021import com.google.common.collect.Sets; 022import org.apache.jena.graph.Node; 023import org.apache.jena.graph.NodeFactory; 024import org.apache.jena.graph.Triple; 025 026import java.util.HashMap; 027import java.util.HashSet; 028import java.util.Map; 029import java.util.Set; 030 031/** 032 * Computes the Least Common Subsumer for given rooted RDF graphs. 033 * @author Lorenz Buehmann 034 * 035 */ 036public class LCS { 037 038 private Map<Set<Node>, RootedRDFGraph> cache = new HashMap<>(); 039 040 public RootedRDFGraph computeLCS(RootedRDFGraph g1, RootedRDFGraph g2) { 041 042 Set<Node> pair = Sets.newHashSet(g1.getRoot(), g2.getRoot()); 043 044 if(cache.containsKey(pair)) { 045 return cache.get(pair); 046 } else { 047 Node x; 048 049 if(g1.getRoot().equals(g2.getRoot())) { 050// x = g1.getRoot(); 051 return g1; 052 } else { 053 // create fresh blank node 054 x = NodeFactory.createBlankNode(); 055 056 // a new set of triples 057 Set<Triple> triples = new HashSet<>(); 058 059 // add to result to avoid recomputation 060 RootedRDFGraph g = new RootedRDFGraph(x, triples); 061 cache.put(pair, g); 062 063 for (Triple t1 : g1.getTriples()) { 064 for (Triple t2 : g2.getTriples()) { 065// Node y = computeLCS(t1.getPredicate(), t2.getPredicate()); 066// Node z = computeLCS(t1.getObject(), t2.getObject()); 067// 068// // add triple <x,y,z> 069// Triple t = Triple.create(x, y, z); 070// triples.add(t); 071 } 072 } 073 return g; 074 } 075 } 076 077 078 } 079 080 private Set<Triple> connectedTriples(Node node, Set<Triple> triples) { 081 Set<Triple> connectedTriples = new HashSet<>(); 082 083 for (Triple triple : triples) { 084 if(isRDFConnected(node, triple, triples)) { 085 connectedTriples.add(triple); 086 } 087 } 088 089 return connectedTriples; 090 } 091 092 /** 093 * Check if there is an RDF-path from source to target. 094 * 095 * @param source the source node 096 * @param target the target node 097 * @param triples the set of triples in the graph 098 * @return whether both nodes are RDF-connected by the given set of triples, i.e. if there is an RDF-path from 099 * source to target. 100 */ 101 public static boolean isRDFConnected(Node source, Node target, Set<Triple> triples) { 102 // trivial case: node is always RDF-connected to itself 103 if(source.equals(target)) { 104 return true; 105 } 106 107 // other case: 108 for (Triple t : triples) { 109 if(t.subjectMatches(source) && 110 (isRDFConnected(t.getPredicate(), target, triples) || 111 isRDFConnected(t.getObject(), target, triples)) 112 ) { 113 return true; 114 } 115 } 116 return false; 117 } 118 119 /* 120 * Check if there is a path from s to the triple, i.e. 121 */ 122 private boolean isRDFConnected(Node node, Triple triple, Set<Triple> triples) { 123 return isRDFConnected(node, triple.getPredicate(), triples) || 124 isRDFConnected(node, triple.getObject(), triples); 125 } 126 127 128 /** 129 * A set of triples with a given node (IRI or blank node) declared to be the root in the 130 * corresponding RDF graph. 131 * @author Lorenz Buehmann 132 * 133 */ 134 static class RootedRDFGraph { 135 private Set<Triple> triples; 136 private Node root; 137 138 public RootedRDFGraph(Node root, Set<Triple> triples) { 139 this.root = root; 140 this.triples = triples; 141 } 142 143 public Node getRoot() { 144 return root; 145 } 146 147 public Set<Triple> getTriples() { 148 return triples; 149 } 150 151 /* (non-Javadoc) 152 * @see java.lang.Object#toString() 153 */ 154 @Override 155 public String toString() { 156 return root + "" + triples; 157 } 158 } 159 160}