    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 final 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                            final DependencyNode hc = ((DependencyNode)head).findComponent();
    095                            final 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                    final 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                            final 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    }