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    }