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}