001 package org.maltparser.core.syntaxgraph; 002 003 import java.util.Iterator; 004 import java.util.SortedMap; 005 import java.util.SortedSet; 006 import java.util.TreeSet; 007 008 import org.maltparser.core.exception.MaltChainedException; 009 import org.maltparser.core.pool.ObjectPoolList; 010 import org.maltparser.core.symbol.SymbolTable; 011 import org.maltparser.core.symbol.SymbolTableHandler; 012 import org.maltparser.core.syntaxgraph.edge.Edge; 013 import org.maltparser.core.syntaxgraph.edge.GraphEdge; 014 import org.maltparser.core.syntaxgraph.node.ComparableNode; 015 import org.maltparser.core.syntaxgraph.node.DependencyNode; 016 import org.maltparser.core.syntaxgraph.node.Node; 017 import org.maltparser.core.syntaxgraph.node.Root; 018 /** 019 * 020 * 021 * @author Johan Hall 022 */ 023 public class DependencyGraph extends Sentence implements DependencyStructure { 024 private final ObjectPoolList<Edge> edgePool; 025 private final SortedSet<Edge> graphEdges; 026 private Root root; 027 private boolean singleHeadedConstraint; 028 private RootLabels rootLabels; 029 030 public DependencyGraph(SymbolTableHandler symbolTables) throws MaltChainedException { 031 super(symbolTables); 032 setSingleHeadedConstraint(true); 033 root = new Root(); 034 root.setBelongsToGraph(this); 035 graphEdges = new TreeSet<Edge>(); 036 edgePool = new ObjectPoolList<Edge>() { 037 protected Edge create() { return new GraphEdge(); } 038 public void resetObject(Edge o) throws MaltChainedException { o.clear(); } 039 }; 040 clear(); 041 } 042 043 public DependencyNode addDependencyNode() throws MaltChainedException { 044 return addTokenNode(); 045 } 046 047 public DependencyNode addDependencyNode(int index) throws MaltChainedException { 048 if (index == 0) { 049 return root; 050 } 051 return addTokenNode(index); 052 } 053 054 public DependencyNode getDependencyNode(int index) throws MaltChainedException { 055 if (index == 0) { 056 return root; 057 } 058 return getTokenNode(index); 059 } 060 061 public int nDependencyNode() { 062 return nTokenNode() + 1; 063 } 064 065 public int getHighestDependencyNodeIndex() { 066 if (hasTokens()) { 067 return getHighestTokenIndex(); 068 } 069 return 0; 070 } 071 072 public Edge addDependencyEdge(int headIndex, int dependentIndex) throws MaltChainedException { 073 DependencyNode head = null; 074 DependencyNode dependent = null; 075 if (headIndex == 0) { 076 head = root; 077 } else if (headIndex > 0) { 078 head = getOrAddTerminalNode(headIndex); 079 } 080 081 if (dependentIndex > 0) { 082 dependent = getOrAddTerminalNode(dependentIndex); 083 } 084 return addDependencyEdge(head, dependent); 085 } 086 087 protected Edge addDependencyEdge(DependencyNode head, DependencyNode dependent) throws MaltChainedException { 088 if (head == null || dependent == null) { 089 throw new SyntaxGraphException("Head or dependent node is missing."); 090 } else if (!dependent.isRoot()) { 091 if (singleHeadedConstraint && dependent.hasHead()) { 092 return moveDependencyEdge(head, dependent); 093 } 094 DependencyNode hc = ((DependencyNode)head).findComponent(); 095 DependencyNode dc = ((DependencyNode)dependent).findComponent(); 096 if (hc != dc) { 097 link(hc, dc); 098 numberOfComponents--; 099 } 100 Edge e = edgePool.checkOut(); 101 e.setBelongsToGraph(this); 102 e.setEdge((Node)head, (Node)dependent, Edge.DEPENDENCY_EDGE); 103 graphEdges.add(e); 104 return e; 105 } else { 106 throw new SyntaxGraphException("Head node is not a root node or a terminal node."); 107 } 108 } 109 110 public Edge moveDependencyEdge(int newHeadIndex, int dependentIndex) throws MaltChainedException { 111 DependencyNode newHead = null; 112 DependencyNode dependent = null; 113 if (newHeadIndex == 0) { 114 newHead = root; 115 } else if (newHeadIndex > 0) { 116 newHead = terminalNodes.get(newHeadIndex); 117 } 118 119 if (dependentIndex > 0) { 120 dependent = terminalNodes.get(dependentIndex); 121 } 122 return moveDependencyEdge(newHead, dependent); 123 } 124 125 protected Edge moveDependencyEdge(DependencyNode newHead, DependencyNode dependent) throws MaltChainedException { 126 if (dependent == null || !dependent.hasHead()) { 127 return null; 128 } 129 Edge headEdge = dependent.getHeadEdge(); 130 LabelSet labels = checkOutNewLabelSet(); 131 for (SymbolTable table : headEdge.getLabelTypes()) { 132 labels.put(table, headEdge.getLabelCode(table)); 133 } 134 headEdge.clear(); 135 headEdge.setBelongsToGraph(this); 136 headEdge.setEdge((Node)newHead, (Node)dependent, Edge.DEPENDENCY_EDGE); 137 headEdge.addLabel(labels); 138 labels.clear(); 139 checkInLabelSet(labels); 140 return headEdge; 141 } 142 143 public void removeDependencyEdge(int headIndex, int dependentIndex) throws MaltChainedException { 144 Node head = null; 145 Node dependent = null; 146 if (headIndex == 0) { 147 head = root; 148 } else if (headIndex > 0) { 149 head = terminalNodes.get(headIndex); 150 } 151 152 if (dependentIndex > 0) { 153 dependent = terminalNodes.get(dependentIndex); 154 } 155 removeDependencyEdge(head, dependent); 156 } 157 158 protected void removeDependencyEdge(Node head, Node dependent) throws MaltChainedException { 159 if (head == null || dependent == null) { 160 throw new SyntaxGraphException("Head or dependent node is missing."); 161 } else if (!dependent.isRoot()) { 162 Iterator<Edge> ie = dependent.getIncomingEdgeIterator(); 163 164 while (ie.hasNext()) { 165 Edge e = ie.next(); 166 if (e.getSource() == head) { 167 ie.remove(); 168 e.clear(); 169 graphEdges.remove(e); 170 edgePool.checkIn(e); 171 } 172 } 173 } else { 174 throw new SyntaxGraphException("Head node is not a root node or a terminal node."); 175 } 176 } 177 178 public Edge addSecondaryEdge(ComparableNode source, ComparableNode target) throws MaltChainedException { 179 if (source == null || target == null) { 180 throw new SyntaxGraphException("Head or dependent node is missing."); 181 } else if (!target.isRoot()) { 182 Edge e = edgePool.checkOut(); 183 e.setBelongsToGraph(this); 184 e.setEdge((Node)source, (Node)target, Edge.SECONDARY_EDGE); 185 graphEdges.add(e); 186 return e; 187 } 188 return null; 189 } 190 191 public void removeSecondaryEdge(ComparableNode source, ComparableNode target) throws MaltChainedException { 192 if (source == null || target == null) { 193 throw new SyntaxGraphException("Head or dependent node is missing."); 194 } else if (!target.isRoot()) { 195 Iterator<Edge> ie = ((Node)target).getIncomingEdgeIterator(); 196 while (ie.hasNext()) { 197 Edge e = ie.next(); 198 if (e.getSource() == source) { 199 ie.remove(); 200 graphEdges.remove(e); 201 edgePool.checkIn(e); 202 } 203 } 204 } 205 } 206 207 // public boolean hasLabeledDependency(int index, SymbolTable table) { 208 // return (!getDependencyNode(index).isRoot() && getDependencyNode(index).getLabelCode(table) != null); 209 // } 210 211 public boolean hasLabeledDependency(int index) throws MaltChainedException { 212 return (getDependencyNode(index).hasHead() && getDependencyNode(index).getHeadEdge().isLabeled()); 213 } 214 215 public boolean isConnected() { 216 return (numberOfComponents == 1); 217 } 218 219 public boolean isProjective() throws MaltChainedException { 220 for (int i : terminalNodes.keySet()) { 221 if (!terminalNodes.get(i).isProjective()) { 222 return false; 223 } 224 } 225 return true; 226 } 227 228 public boolean isTree() { 229 return isConnected() && isSingleHeaded(); 230 } 231 232 public boolean isSingleHeaded() { 233 for (int i : terminalNodes.keySet()) { 234 if (!terminalNodes.get(i).hasAtMostOneHead()) { 235 return false; 236 } 237 } 238 return true; 239 } 240 241 public boolean isSingleHeadedConstraint() { 242 return singleHeadedConstraint; 243 } 244 245 public void setSingleHeadedConstraint(boolean singleHeadedConstraint) { 246 this.singleHeadedConstraint = singleHeadedConstraint; 247 } 248 249 public int nNonProjectiveEdges() throws MaltChainedException { 250 int c = 0; 251 for (int i : terminalNodes.keySet()) { 252 if (!terminalNodes.get(i).isProjective()) { 253 c++; 254 } 255 } 256 return c; 257 } 258 259 public int nEdges() { 260 return graphEdges.size(); 261 } 262 263 public SortedSet<Integer> getDependencyIndices() { 264 SortedSet<Integer> indices = new TreeSet<Integer>(terminalNodes.keySet()); 265 indices.add(0); 266 return indices; 267 } 268 269 protected DependencyNode link(DependencyNode x, DependencyNode y) { 270 if (x.getRank() > y.getRank()) { 271 y.setComponent(x); 272 } else { 273 x.setComponent(y); 274 if (x.getRank() == y.getRank()) { 275 y.setRank(y.getRank()+1); 276 } 277 return y; 278 } 279 return x; 280 } 281 282 public void linkAllTreesToRoot() throws MaltChainedException { 283 for (int i : terminalNodes.keySet()) { 284 if (!terminalNodes.get(i).hasHead()) { 285 addDependencyEdge(root,terminalNodes.get(i)); 286 } 287 } 288 } 289 290 public String getDefaultRootEdgeLabelSymbol(SymbolTable table) throws MaltChainedException { 291 if (rootLabels == null) { 292 return null; 293 } 294 return rootLabels.getDefaultRootLabelSymbol(table); 295 } 296 297 public int getDefaultRootEdgeLabelCode(SymbolTable table) throws MaltChainedException { 298 if (rootLabels == null) { 299 return -1; 300 } 301 return rootLabels.getDefaultRootLabelCode(table); 302 } 303 304 public void setDefaultRootEdgeLabel(SymbolTable table, String defaultRootSymbol) throws MaltChainedException { 305 if (rootLabels == null) { 306 rootLabels = new RootLabels(); 307 } 308 rootLabels.setDefaultRootLabel(table, defaultRootSymbol); 309 } 310 311 public void setDefaultRootEdgeLabels(String rootLabelOption, SortedMap<String, SymbolTable> edgeSymbolTables) throws MaltChainedException { 312 if (rootLabels == null) { 313 rootLabels = new RootLabels(); 314 } 315 rootLabels.setRootLabels(rootLabelOption, edgeSymbolTables); 316 } 317 318 public void clear() throws MaltChainedException { 319 edgePool.checkInAll(); 320 graphEdges.clear(); 321 root.clear(); 322 super.clear(); 323 numberOfComponents++; 324 } 325 326 public DependencyNode getDependencyRoot() { 327 return root; 328 } 329 330 public String toString() { 331 final StringBuilder sb = new StringBuilder(); 332 for (int index : terminalNodes.keySet()) { 333 sb.append(terminalNodes.get(index).toString().trim()); 334 sb.append('\n'); 335 } 336 sb.append('\n'); 337 return sb.toString(); 338 } 339 }