From 9ce65c5a963b03ee97fe9cb6c5aa65a3c04a80a8 Mon Sep 17 00:00:00 2001 From: yzhou Date: Tue, 21 Apr 2015 10:34:27 +0100 Subject: initial version --- .../cs/pagoda/constraints/PredicateDependency.java | 235 +++++++++++++++++++++ 1 file changed, 235 insertions(+) create mode 100644 src/uk/ac/ox/cs/pagoda/constraints/PredicateDependency.java (limited to 'src/uk/ac/ox/cs/pagoda/constraints/PredicateDependency.java') diff --git a/src/uk/ac/ox/cs/pagoda/constraints/PredicateDependency.java b/src/uk/ac/ox/cs/pagoda/constraints/PredicateDependency.java new file mode 100644 index 0000000..b201918 --- /dev/null +++ b/src/uk/ac/ox/cs/pagoda/constraints/PredicateDependency.java @@ -0,0 +1,235 @@ +package uk.ac.ox.cs.pagoda.constraints; + +import java.util.Collection; +import java.util.HashMap; +import java.util.HashSet; +import java.util.LinkedList; +import java.util.Map; +import java.util.Queue; +import java.util.Set; + +import org.semanticweb.HermiT.model.AnnotatedEquality; +import org.semanticweb.HermiT.model.AtLeastConcept; +import org.semanticweb.HermiT.model.AtLeastDataRange; +import org.semanticweb.HermiT.model.Atom; +import org.semanticweb.HermiT.model.AtomicConcept; +import org.semanticweb.HermiT.model.AtomicNegationConcept; +import org.semanticweb.HermiT.model.AtomicRole; +import org.semanticweb.HermiT.model.DLClause; +import org.semanticweb.HermiT.model.DLPredicate; +import org.semanticweb.HermiT.model.Equality; +import org.semanticweb.HermiT.model.Inequality; +import org.semanticweb.HermiT.model.InverseRole; + +import uk.ac.ox.cs.pagoda.rules.OverApproxExist; +import uk.ac.ox.cs.pagoda.util.Namespace; +import uk.ac.ox.cs.pagoda.util.Utility; + + +public class PredicateDependency extends DependencyGraph { + + Collection m_clauses; + Map> edgeLabels = new HashMap>(); + + public PredicateDependency(Collection clauses) { + m_clauses = clauses; + build(); + } + + @Override + protected void build() { + update(m_clauses); + + addLink(equality, AtomicConcept.NOTHING); + addLink(inequality, AtomicConcept.NOTHING); + } + + private void addEdgeLabel(DLPredicate body, DLPredicate head, DLClause clause) { + PredicatePair key = new PredicatePair(body, head); + LinkedList value; + if ((value = edgeLabels.get(key)) == null) + edgeLabels.put(key, value = new LinkedList()); + value.add(clause); + } + + private void addLinks4Negation(AtomicConcept c, DLClause clause) { + addLink(c, AtomicConcept.NOTHING); + addEdgeLabel(c, AtomicConcept.NOTHING, clause); + String iri = c.getIRI(); + addLink(c = AtomicConcept.create(iri.substring(0, iri.length() - 4)), AtomicConcept.NOTHING); + addEdgeLabel(c, AtomicConcept.NOTHING, clause); + } + + public Set collectPredicate(Atom[] atoms) { + Set predicates = new HashSet(); + for (Atom atom: atoms) + predicates.addAll(getAtomicPredicates(atom.getDLPredicate())); + return predicates; + } + + private static final DLPredicate equality = AtomicRole.create(Namespace.EQUALITY); + private static final DLPredicate inequality = AtomicRole.create(Namespace.INEQUALITY); + + private Set getAtomicPredicates(DLPredicate predicate) { + Set predicates = new HashSet(); + if (predicate instanceof AtLeastConcept) + predicates.addAll(getAtomicPredicates((AtLeastConcept) predicate)); + else { + if ((predicate = getAtomicPredicate(predicate)) != null) + predicates.add(predicate); + } + return predicates; + } + + private Set getAtomicPredicates(AtLeastConcept alc) { + Set set = new HashSet(); + if (alc.getOnRole() instanceof AtomicRole) + set.add((AtomicRole) alc.getOnRole()); + else + set.add(((InverseRole) alc.getOnRole()).getInverseOf()); + + if (alc.getToConcept() instanceof AtomicConcept) + if (alc.getToConcept().equals(AtomicConcept.THING)); + else set.add((AtomicConcept) alc.getToConcept()); + else + set.add(OverApproxExist.getNegationConcept(((AtomicNegationConcept) alc.getToConcept()).getNegatedAtomicConcept())); + return set; + } + + private DLPredicate getAtomicPredicate(DLPredicate p) { + if (p instanceof Equality || p instanceof AnnotatedEquality) + return equality; + if (p instanceof Inequality) + return inequality; + if (p instanceof AtomicConcept) + if (p.equals(AtomicConcept.THING)) + return null; + else return p; + if (p instanceof AtomicRole) + return p; + if (p instanceof AtLeastDataRange) { + AtLeastDataRange aldr = (AtLeastDataRange) p; + if (aldr.getOnRole() instanceof AtomicRole) + return (AtomicRole) aldr.getOnRole(); + else + return ((InverseRole) aldr.getOnRole()).getInverseOf(); + } + Utility.logDebug("Unknown DLPredicate in PredicateDependency: " + p); + return null; + } + + public Set pathTo(DLPredicate p) { + Set rules = new HashSet(); + Set visited = new HashSet(); + + Queue queue = new LinkedList(); + queue.add(p); + visited.add(p); + + Set edge; + Collection clauses; + + while (!queue.isEmpty()) { + if ((edge = reverseEdges.get(p = queue.poll())) != null) { + for (DLPredicate pred: edge) { + if (!visited.contains(pred)) { + queue.add(pred); + visited.add(pred); + } + clauses = edgeLabelsBetween(pred, p); + if (clauses != null) rules.addAll(clauses); + } + } + } + return rules; + } + + private LinkedList edgeLabelsBetween(DLPredicate p, DLPredicate q) { + PredicatePair pair = new PredicatePair(p, q); + return edgeLabels.get(pair); + } + + Set reachableToBottom = null; + + public Set pathToBottom(DLPredicate p) { + if (reachableToBottom == null) { + reachableToBottom = getAncesters(AtomicConcept.NOTHING); + reachableToBottom.add(AtomicConcept.NOTHING); + } + + Set rules = new HashSet(); + Set visited = new HashSet(); + + Queue queue = new LinkedList(); + queue.add(p); + visited.add(p); + + Set edge; + Collection clauses; + + while (!queue.isEmpty()) { + if ((edge = edges.get(p = queue.poll())) != null) { + for (DLPredicate next: edge) + if (reachableToBottom.contains(next)) { + if (!visited.contains(next)) { + queue.add(next); + visited.add(next); + } + clauses = edgeLabelsBetween(p, next); + if (clauses != null) rules.addAll(clauses); + } + } + } + return rules; + } + + public void update(Collection clauses) { + Set headPredicates, bodyPredicates; + + for (DLClause clause: clauses) { + headPredicates = collectPredicate(clause.getHeadAtoms()); + bodyPredicates = collectPredicate(clause.getBodyAtoms()); + + for (DLPredicate body: bodyPredicates) + for (DLPredicate head: headPredicates) { + addLink(body, head); + addEdgeLabel(body, head, clause); + + if (body instanceof AtomicConcept && body.toString().contains("_neg")) + addLinks4Negation((AtomicConcept) body, clause); + if (head instanceof AtomicConcept && head.toString().contains("_neg")) + addLinks4Negation((AtomicConcept) head, clause); + } + + for (DLPredicate body: bodyPredicates) + addLink(equality, body); + + for (DLPredicate head: headPredicates) + addLink(equality, head); + } + } + +} + +class PredicatePair { + + DLPredicate p, q; + + public PredicatePair(DLPredicate p, DLPredicate q) { + this.p = p; this.q = q; + } + + public int hashCode() { + return p.hashCode() * 1997 + q.hashCode(); + } + + public boolean equals(Object o) { + if (!(o instanceof PredicatePair)) return false; + PredicatePair thatPair = (PredicatePair) o; + return p.equals(thatPair.p) && q.equals(thatPair.q); + } + + public String toString() { + return "<" + p.toString() + "," + q.toString() + ">"; + } +} -- cgit v1.2.3