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.datastructures.impl; 020 021import java.io.IOException; 022import java.io.ObjectInputStream; 023import java.io.ObjectOutputStream; 024import java.io.Serializable; 025import java.util.*; 026import java.util.Map.Entry; 027import java.util.function.Function; 028import java.util.regex.Matcher; 029import java.util.regex.Pattern; 030 031import org.apache.jena.vocabulary.RDF; 032import org.dllearner.algorithms.qtl.QueryTreeUtils; 033import org.dllearner.algorithms.qtl.datastructures.NodeInv; 034import org.dllearner.algorithms.qtl.datastructures.impl.QueryTreeImpl.NodeType; 035import org.dllearner.algorithms.qtl.util.NodeComparatorInv; 036import org.dllearner.algorithms.qtl.util.PrefixCCPrefixMapping; 037 038import com.google.common.collect.ComparisonChain; 039import org.apache.jena.datatypes.BaseDatatype; 040import org.apache.jena.datatypes.RDFDatatype; 041import org.apache.jena.datatypes.xsd.XSDDatatype; 042import org.apache.jena.graph.Node; 043import org.apache.jena.graph.NodeFactory; 044import org.apache.jena.graph.Node_URI; 045import org.apache.jena.rdf.model.Literal; 046import org.apache.jena.shared.PrefixMapping; 047import org.apache.jena.sparql.serializer.SerializationContext; 048import org.apache.jena.sparql.util.FmtUtils; 049import org.apache.jena.sparql.util.NodeComparator; 050 051/** 052 * @author Lorenz Buehmann 053 * 054 */ 055public class RDFResourceTree extends GenericTree<Node, RDFResourceTree> implements Serializable, Comparable<RDFResourceTree>{ 056 057 public enum Rendering { 058 INDENTED, BRACES 059 } 060 061 private int id; 062 063 public static final Node DEFAULT_VAR_NODE = NodeFactory.createVariable(""); 064 public static final Node DEFAULT_LITERAL_NODE = NodeFactory.createLiteral("DEF"); 065 066 // a datatype which only exists if node is literal 067 private RDFDatatype datatype; 068 069 private Map<RDFResourceTree, Node> child2Edge = new IdentityHashMap<>();//HashMap<>(); 070 private NavigableMap<Node, List<RDFResourceTree>> edge2Children = new TreeMap<>(new NodeComparatorInv()); 071 072 private Node anchorVar; 073 public void setAnchorVar(Node anchorVar) { 074 this.anchorVar = anchorVar; 075 } 076 public Node getAnchorVar() { 077 return anchorVar; 078 } 079 public boolean hasAnchor() { 080 return anchorVar != null; 081 } 082 public boolean hasAnchor(Node node) { 083 Objects.requireNonNull(node); 084 return node.matches(anchorVar); 085 } 086// private TreeMultimap<Node, RDFResourceTree> edge2Children = TreeMultimap.create( 087// new NodeComparator(), Ordering.arbitrary()); 088 089 090 public static RDFResourceTree newVarNode() { 091 return new RDFResourceTree(); 092 } 093 094 public static RDFResourceTree newLiteralNode() { 095 return new RDFResourceTree(DEFAULT_LITERAL_NODE); 096 } 097 098 099 /** 100 * Creates an empty resource tree with a default variable as label. 101 */ 102 public RDFResourceTree() { 103 this(0, DEFAULT_VAR_NODE); 104 } 105 106 /** 107 * Creates an empty resource tree with a default variable as label and the given ID. 108 */ 109 public RDFResourceTree(int id) { 110 this(id, DEFAULT_VAR_NODE); 111 } 112 113 public RDFResourceTree(int id, Node data) { 114 super(data); 115 this.id = id; 116 if(data.isBlank()) { 117 this.data = DEFAULT_VAR_NODE; 118 } 119 } 120 121 public RDFResourceTree(Node data) { 122 this(0, data); 123 } 124 125 /** 126 * Create empty literal node with given datatype. 127 * @param datatype the datatype 128 */ 129 public RDFResourceTree(RDFDatatype datatype) { 130 this(0, datatype); 131 } 132 133 /** 134 * Create empty literal node with given ID and datatype. 135 * @param id the ID 136 * @param datatype the datatype 137 */ 138 public RDFResourceTree(int id, RDFDatatype datatype) { 139 super(DEFAULT_LITERAL_NODE); 140 this.id = id; 141 this.datatype = datatype; 142 } 143 144 /** 145 * Create literal node with given ID, datatype and a set of literal values. 146 * @param id the ID 147 * @param datatype the datatype 148 * @param literals the literal values 149 */ 150 public RDFResourceTree(int id, RDFDatatype datatype, Set<Literal> literals) { 151 super(DEFAULT_LITERAL_NODE); 152 this.id = id; 153 this.datatype = datatype; 154 } 155 156 /** 157 * Copy constructor that copies 158 * - node label 159 * - children recursively 160 * - datatype (if literal node) 161 * - anchor var (if exists) 162 * @param tree 163 */ 164 public RDFResourceTree(RDFResourceTree tree) { 165 this(tree, true); 166 } 167 168 /** 169 * Copy constructor that copies 170 * - node label 171 * - datatype (if literal node) 172 * - anchor var (if exists) 173 * 174 * Children are recursivly copied only if enabled. 175 * 176 * @param tree the tree 177 * @param withChildren whether to copy also the children recursively 178 */ 179 public RDFResourceTree(RDFResourceTree tree, boolean withChildren) { 180 super(tree.getData()); 181 this.id = getID(); 182 183 setDatatype(tree.getDatatype()); 184 setAnchorVar(tree.getAnchorVar()); 185 186 if(withChildren) { 187 for (Entry<Node, List<RDFResourceTree>> entry : tree.edge2Children.entrySet()) { 188 Node edge = entry.getKey(); 189 List<RDFResourceTree> children = entry.getValue(); 190 191 for (RDFResourceTree child : children) { 192 addChild(new RDFResourceTree(child), edge); 193 } 194 } 195 } 196 } 197 198 /** 199 * @return the ID of the tree 200 */ 201 public int getID() { 202 return id; 203 } 204 205 public void setId(int id) { 206 this.id = id; 207 } 208 209 public void addChild(RDFResourceTree child, Node edge) { 210 super.addChild(child); 211 List<RDFResourceTree> childrenForEdge = edge2Children.computeIfAbsent(edge, k -> new ArrayList<>()); 212 childrenForEdge.add(child); 213 214 child2Edge.put(child, edge); 215 } 216 217 public void addChildren(List<RDFResourceTree> children, Node edge) { 218 super.addChildren(children); 219 List<RDFResourceTree> childrenForEdge = edge2Children.computeIfAbsent(edge, k -> new ArrayList<>()); 220 childrenForEdge.addAll(children); 221 } 222 223 public void addChildAt(int index, RDFResourceTree child, Node_URI edge) throws IndexOutOfBoundsException { 224 super.addChildAt(index, child); 225 child.setParent(this); 226 } 227 228 public void removeChild(RDFResourceTree child, Node edge) { 229 super.removeChild(child); 230 231 List<RDFResourceTree> childrenForEdge = edge2Children.get(edge); 232 if(childrenForEdge != null) { 233 childrenForEdge.remove(child); 234 235 // if there are no other children for the given edge, remove whole edge 236 if(childrenForEdge.isEmpty()) { 237 edge2Children.remove(edge); 238 } 239 } 240 241 child2Edge.remove(child); 242 } 243 244 public void replaceChild(RDFResourceTree oldChild, RDFResourceTree newChild, Node edge) { 245 removeChild(oldChild, edge); 246 addChild(newChild, edge); 247 } 248 249 @Override 250 public List<RDFResourceTree> getChildren() { 251 return super.getChildren(); 252 } 253 254 /** 255 * @param edge the edge 256 * @return all children for the specified edge, or <code>null</code> if 257 * there is no child for the edge 258 */ 259 public List<RDFResourceTree> getChildren(Node edge) { 260 return edge2Children.get(edge); 261 } 262 263 264 /** 265 * Returns the edge from the current node to the given child node. 266 * 267 * @param child the child node 268 * @return the edge 269 */ 270 public Node getEdgeToChild(RDFResourceTree child) { 271 return child2Edge.get(child); 272 } 273 274 /** 275 * Returns the edge from the parent node to the current node. If the current node is the root node, i.e. 276 * there is no parent, it will return <code>null</code> instead. 277 * 278 * @return the edge from the parent 279 */ 280 public Node getEdgeToParent() { 281 RDFResourceTree parent = getParent(); 282 if(parent != null) { 283 return parent.getEdgeToChild(this); 284 } 285 return null; 286 } 287 288 /** 289 * @param edge 290 * the edge from the root node to the possible child nodes 291 * @return TRUE if there is at least one child connected by the given edge, 292 * otherwise FALSE 293 */ 294 public boolean hasChildren(Node edge) { 295 return edge2Children.get(edge) != null; 296 } 297 298 /** 299 * @return all distinct outgoing edges. 300 */ 301 public SortedSet<Node> getEdges() { 302 return edge2Children.navigableKeySet(); 303 } 304 305 /** 306 * @return all distinct outgoing edges to children of the given node type 307 */ 308 public SortedSet<Node> getEdges(NodeType nodeType) { 309 SortedSet<Node> edges = new TreeSet<>(new NodeComparator()); 310 for (Entry<Node, List<RDFResourceTree>> entry : edge2Children.entrySet()) { 311 Node edge = entry.getKey(); 312 List<RDFResourceTree> children = entry.getValue(); 313 314 for (RDFResourceTree child : children) { 315 if ((nodeType == NodeType.LITERAL && child.isLiteralNode()) 316 || (nodeType == NodeType.RESOURCE && child.isResourceNode())) { 317 edges.add(edge); 318 break; 319 } 320 } 321 } 322 return edges; 323 } 324 325 public boolean isResourceNode() { 326 return data.isURI(); 327 } 328 329 public boolean isClassNode() { 330 return !isRoot() && getEdgeToParent().equals(RDF.type.asNode()); 331 } 332 333 public boolean isLiteralNode() { 334 return data.isLiteral(); 335 } 336 337 public boolean isLiteralValueNode() { 338 return data.isLiteral() && !data.equals(DEFAULT_LITERAL_NODE); 339 } 340 341 public boolean isVarNode() { 342 return data.isVariable(); 343 } 344 345 public boolean isObjectPropertyEdge(Node edge) { 346 return !edge2Children.get(edge).iterator().next().isLiteralNode(); 347 } 348 349 public boolean isDataPropertyEdge(Node edge) { 350 return edge2Children.get(edge).iterator().next().isLiteralNode(); 351 } 352 353 /** 354 * @return the datatype if node is literal node 355 */ 356 public RDFDatatype getDatatype() { 357 return datatype; 358 } 359 360 public String getStringRepresentation() { 361 return getStringRepresentation(false, null, null, PrefixCCPrefixMapping.Full); 362 } 363 364 public String getStringRepresentation(Rendering syntax) { 365 return getStringRepresentation(false, syntax, null, PrefixCCPrefixMapping.Full); 366 } 367 368 public String getStringRepresentation(String baseIRI) { 369 return getStringRepresentation(false, null, baseIRI, PrefixCCPrefixMapping.Full); 370 } 371 372 public String getStringRepresentation(String baseIRI, PrefixMapping pm) { 373 return getStringRepresentation(false, null, baseIRI, pm); 374 } 375 376 public String getStringRepresentation(Rendering syntax, String baseIRI, PrefixMapping pm) { 377 return getStringRepresentation(false, syntax, baseIRI, pm); 378 } 379 380 /** 381 * Prints the query tree and shows children of resources only if enabled. 382 * 383 * @param stopIfChildIsResourceNode do not show children of nodes that are resources 384 * @return the query tree 385 */ 386 public String getStringRepresentation(boolean stopIfChildIsResourceNode) { 387 return getStringRepresentation(stopIfChildIsResourceNode, null, null, PrefixCCPrefixMapping.Full); 388 } 389 390 /** 391 * Prints the query tree and shows children of resources only if enabled. 392 * 393 * @param stopIfChildIsResourceNode if a child node is not a variable, children will not be rendered 394 * @param syntax the syntax used for rendering 395 * @param baseIRI the base IRI 396 * @param pm the prefix mapping 397 * @return a rendered string representation of the tree 398 */ 399 public String getStringRepresentation(boolean stopIfChildIsResourceNode, Rendering syntax, String baseIRI, PrefixMapping pm) { 400 return getStringRepresentation(stopIfChildIsResourceNode, syntax, baseIRI, pm, false); 401 } 402 403 /** 404 * Prints the query tree and shows children of resources only if enabled. 405 * 406 * @param stopIfChildIsResourceNode if a child node is not a variable, children will not be rendered 407 * @param syntax the syntax used for rendering 408 * @param baseIRI the base IRI 409 * @param pm the prefix mapping 410 * @param showID show the IDs of the nodes 411 * @return a rendered string representation of the tree 412 */ 413 public String getStringRepresentation(boolean stopIfChildIsResourceNode, Rendering syntax, String baseIRI, PrefixMapping pm, boolean showID) { 414 StringBuilder sb = new StringBuilder(); 415 416 SerializationContext context = new SerializationContext(pm); 417 context.setBaseIRI(baseIRI); 418 419 if(syntax == Rendering.BRACES) { 420 buildTreeString(sb, stopIfChildIsResourceNode, 0, context); 421 } else { 422 buildTreeStringIndented(sb, stopIfChildIsResourceNode, 1, context, showID); 423 } 424 425 return "TREE [\n" + sb.toString() + "]"; 426 } 427 428 private void buildTreeString(StringBuilder sb, boolean stopIfChildIsResourceNode, int depth, SerializationContext context) { 429 430 // render current node 431 String ren; 432 if(isLiteralNode() && !isLiteralValueNode()) { 433 ren = "?^^" + FmtUtils.stringForNode(NodeFactory.createURI(this.getDatatype().getURI()), context); 434 } else { 435 ren = FmtUtils.stringForNode(this.getData(), context); 436 } 437 sb.append(ren);//.append("\n"); 438 439 // render edges + children 440 if (isRoot() || !isResourceNode() || (isResourceNode() && !stopIfChildIsResourceNode)) { 441 for(Node edge : getEdges()) { 442 for (RDFResourceTree child : getChildren(edge)) { 443 sb.append("("); 444 if (edge != null) { 445 sb.append(FmtUtils.stringForNode(edge, context)); 446 sb.append("("); 447 } 448 child.buildTreeString(sb, stopIfChildIsResourceNode, depth + 1, context); 449 sb.append(")"); 450 sb.append(")"); 451// sb.append("\n"); 452 } 453 } 454 } 455 } 456 457 private void buildTreeStringIndented(StringBuilder sb, boolean stopIfChildIsResourceNode, int depth, SerializationContext context, boolean showID) { 458 459 // render current node 460 String ren; 461 if(isLiteralNode() && !isLiteralValueNode() && getDatatype() != null) { 462 ren = "?^^" + FmtUtils.stringForNode(NodeFactory.createURI(this.getDatatype().getURI()), context); 463 } else { 464 ren = FmtUtils.stringForNode(this.getData(), context); 465 } 466 if(getAnchorVar() != null) { 467 ren += " (" + getAnchorVar() + ")"; 468 } 469 if(showID) { 470 ren += " (" + getID() + ")"; 471 } 472 sb.append(ren).append("\n"); 473 474 // render edges + children 475 if (isRoot() || !isResourceNode() || (isResourceNode() && !stopIfChildIsResourceNode)) { 476 for(Node edge : getEdges()) { 477 for (RDFResourceTree child : getChildren(edge)) { 478 for (int i = 0; i < depth; i++) { 479 sb.append("\t"); 480 } 481 if (edge != null) { 482// sb.append(" "); 483 sb.append(FmtUtils.stringForNode(edge, context)); 484 if(edge instanceof NodeInv) { 485 sb.append(" <--- "); 486 } else { 487 sb.append(" ---> "); 488 } 489 490 } 491 child.buildTreeStringIndented(sb, stopIfChildIsResourceNode, depth + 1, context, showID); 492 } 493 } 494 } 495 } 496 497 @Override 498 public boolean equals(Object o) { 499 if (this == o) return true; 500 if (o == null || getClass() != o.getClass()) return false; 501 if (!super.equals(o)) return false; 502 503 RDFResourceTree that = (RDFResourceTree) o; 504 505 return (this.isResourceNode() || this.isLiteralValueNode()) && this.getData().equals(that.getData()); 506 } 507 508 @Override 509 public int hashCode() { 510 int result = super.hashCode(); 511 result = 31 * result + id; 512 return result; 513 } 514 515 /** 516 * @param datatype the datatype to set 517 */ 518 public void setDatatype(RDFDatatype datatype) { 519 this.datatype = datatype; 520 } 521 522 /** 523 * Serialize this instance. 524 * 525 * @param out Target to which this instance is written. 526 * @throws IOException Thrown if exception occurs during serialization. 527 */ 528 private void writeObject(final ObjectOutputStream out) throws IOException { 529 // ID 530 out.writeInt(this.id); 531 532 // datatype 533 out.writeObject(datatype == null ? "" : this.datatype.getURI()); 534 535 // data 536 out.writeObject(this.data.toString()); 537 538 // edge + children 539 SortedSet<Node> edges = getEdges(); 540 if(edges.isEmpty()) { 541 out.writeObject(null); 542 } 543 for (Node edge : edges) { 544 List<RDFResourceTree> children = getChildren(edge); 545 out.writeObject(edge.toString()); 546 out.writeObject(children); 547 } 548 out.writeObject(null); 549 } 550 551 private void readObject(ObjectInputStream ois) throws ClassNotFoundException, IOException { 552 child2Edge = new HashMap<>(); 553 edge2Children = new TreeMap<>(new NodeComparator()); 554 555 // ID 556 int id = ois.readInt(); 557 558 // datatype 559 String datatypeURI = (String) ois.readObject(); 560 if(datatypeURI != null) { 561 if(datatypeURI.equals(XSDDatatype.XSD)) { 562 setDatatype(new XSDDatatype(datatypeURI)); 563 } else { 564 setDatatype(new BaseDatatype(datatypeURI)); 565 } 566 } 567 568 // data 569 String dataString = (String) ois.readObject(); 570 Node data; 571 if(dataString.equals(RDFResourceTree.DEFAULT_VAR_NODE.toString())) { 572 data = RDFResourceTree.DEFAULT_VAR_NODE; 573 } else if(dataString.equals(RDFResourceTree.DEFAULT_LITERAL_NODE.toString())) { 574 data = RDFResourceTree.DEFAULT_LITERAL_NODE; 575 } else { 576 data = NodeFactory.createURI(dataString); 577 } 578 setData(data); 579 580 // edge + children 581 Object edgeObject; 582 while((edgeObject = ois.readObject()) != null) { 583 Node edge = NodeFactory.createURI((String) edgeObject); 584 List<RDFResourceTree> children = (List<RDFResourceTree>) ois.readObject(); 585 for (RDFResourceTree child : children) { 586 addChild(child, edge); 587 } 588 } 589 590 } 591 592 /* (non-Javadoc) 593 * @see java.lang.Comparable#compareTo(java.lang.Object) 594 */ 595 @Override 596 public int compareTo(RDFResourceTree other) { 597 return ComparisonChain.start(). 598 compare(this.getData(), other.getData(), new NodeComparator()). // root node 599 compare(this.getNumberOfChildren(), other.getNumberOfChildren()). // number of direct children 600 compare(QueryTreeUtils.toOWLClassExpression(this), QueryTreeUtils.toOWLClassExpression(other)). // class expression representation 601 result(); 602 } 603 604// static class NodeRenderer implements Function<Node, String>{ 605// @Override 606// public String apply(Node node) { 607// return null; 608// } 609// } 610// 611// static class TreeRenderer { 612// 613// private Function<Node, String> nodeRenderer; 614// 615// public String render(RDFResourceTree tree) { 616// 617// } 618// 619// 620// } 621}