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                                            graphEdges.remove(e);
168                                            ie.remove();
169                                            edgePool.checkIn(e);
170                                    }
171                            } 
172                    } else {
173                            throw new SyntaxGraphException("Head node is not a root node or a terminal node.");
174                    }
175            }
176            
177            public Edge addSecondaryEdge(ComparableNode source, ComparableNode target) throws MaltChainedException {
178                    if (source == null || target == null) {
179                            throw new SyntaxGraphException("Head or dependent node is missing.");
180                    } else if (!target.isRoot()) {
181                            Edge e = edgePool.checkOut();
182                            e.setBelongsToGraph(this);
183                            e.setEdge((Node)source, (Node)target, Edge.SECONDARY_EDGE);
184                            graphEdges.add(e);
185                            return e;
186                    }
187                    return null;
188            }
189            
190            public void removeSecondaryEdge(ComparableNode source, ComparableNode target) throws MaltChainedException {
191                    if (source == null || target == null) {
192                            throw new SyntaxGraphException("Head or dependent node is missing.");
193                    } else if (!target.isRoot()) {
194                            Iterator<Edge> ie = ((Node)target).getIncomingEdgeIterator();
195                            while (ie.hasNext()) {
196                                    Edge e = ie.next();
197                                    if (e.getSource() == source) {
198                                            ie.remove();
199                                            graphEdges.remove(e);
200                                            edgePool.checkIn(e);
201                                    }
202                            }
203                    }
204            }
205            
206    //      public boolean hasLabeledDependency(int index, SymbolTable table) {
207    //              return (!getDependencyNode(index).isRoot() && getDependencyNode(index).getLabelCode(table) != null);
208    //      }
209    
210            public boolean hasLabeledDependency(int index) throws MaltChainedException {
211                    return (getDependencyNode(index).hasHead() && getDependencyNode(index).getHeadEdge().isLabeled());
212            }
213            
214            public boolean isConnected() {
215                    return (numberOfComponents == 1);
216            }
217            
218            public boolean isProjective() throws MaltChainedException {
219                    for (int i : terminalNodes.keySet()) {
220                            if (!terminalNodes.get(i).isProjective()) {
221                                    return false;
222                            }
223                    }
224                    return true;
225            }
226            
227            public boolean isTree() {
228                    return isConnected() && isSingleHeaded();
229            }
230            
231            public boolean isSingleHeaded() {
232                    for (int i : terminalNodes.keySet()) {
233                            if (!terminalNodes.get(i).hasAtMostOneHead()) {
234                                    return false;
235                            }
236                    }
237                    return true;
238            }
239            
240            public boolean isSingleHeadedConstraint() {
241                    return singleHeadedConstraint;
242            }
243    
244            public void setSingleHeadedConstraint(boolean singleHeadedConstraint) {
245                    this.singleHeadedConstraint = singleHeadedConstraint;
246            }
247            
248            public int nNonProjectiveEdges() throws MaltChainedException {
249                    int c = 0;
250                    for (int i : terminalNodes.keySet()) {
251                            if (!terminalNodes.get(i).isProjective()) {
252                                    c++;
253                            }
254                    }
255                    return c;
256            }
257            
258            public int nEdges() {
259                    return graphEdges.size();
260            }
261            
262            public SortedSet<Edge> getEdges() {
263                    return graphEdges;
264            }
265            
266            public SortedSet<Integer> getDependencyIndices() {
267                    SortedSet<Integer> indices = new TreeSet<Integer>(terminalNodes.keySet());
268                    indices.add(0);
269                    return indices;
270            }
271            
272            protected DependencyNode link(DependencyNode x, DependencyNode y) {
273                    if (x.getRank() > y.getRank()) {
274                            y.setComponent(x);
275                    } else {
276                            x.setComponent(y);
277                            if (x.getRank() == y.getRank()) {
278                                    y.setRank(y.getRank()+1);
279                            }
280                            return y;
281                    }
282                    return x;
283            }
284            
285            public void linkAllTreesToRoot() throws MaltChainedException {
286                    for (int i : terminalNodes.keySet()) {
287                            if (!terminalNodes.get(i).hasHead()) {
288                                    addDependencyEdge(root,terminalNodes.get(i));
289                            }
290                    }
291            }
292            
293            public LabelSet getDefaultRootEdgeLabels() throws MaltChainedException {
294                    if (rootLabels == null) {
295                            return null;
296                    }
297                    return rootLabels.getDefaultRootLabels();
298            }
299            
300            public String getDefaultRootEdgeLabelSymbol(SymbolTable table) throws MaltChainedException {
301                    if (rootLabels == null) {
302                            return null;
303                    }
304                    return rootLabels.getDefaultRootLabelSymbol(table);
305            }
306            
307            public int getDefaultRootEdgeLabelCode(SymbolTable table) throws MaltChainedException {
308                    if (rootLabels == null) {
309                            return -1;
310                    }
311                    return rootLabels.getDefaultRootLabelCode(table);
312            }
313            
314            public void setDefaultRootEdgeLabel(SymbolTable table, String defaultRootSymbol) throws MaltChainedException {
315                    if (rootLabels == null) {
316                            rootLabels = new RootLabels();
317                    }
318                    rootLabels.setDefaultRootLabel(table, defaultRootSymbol);
319            }
320            
321            public void setDefaultRootEdgeLabels(String rootLabelOption, SortedMap<String, SymbolTable> edgeSymbolTables) throws MaltChainedException {
322                    if (rootLabels == null) {
323                            rootLabels = new RootLabels();
324                    }
325                    rootLabels.setRootLabels(rootLabelOption, edgeSymbolTables);
326            }
327            
328            public void clear() throws MaltChainedException {
329                    edgePool.checkInAll();
330                    graphEdges.clear();
331                    root.clear();
332                    super.clear();
333                    numberOfComponents++;
334            }
335            
336            public DependencyNode getDependencyRoot() {
337                    return root;
338            }
339            
340            public String toString() {
341                    final StringBuilder sb = new StringBuilder();
342                    for (int index : terminalNodes.keySet()) {
343                            sb.append(terminalNodes.get(index).toString().trim());
344                            sb.append('\n');
345                    }
346                    sb.append('\n');
347                    return sb.toString();
348            }
349    }