001package org.maltparser.parser.algorithm.planar;
002
003import java.util.Stack;
004
005import org.maltparser.core.exception.MaltChainedException;
006import org.maltparser.core.propagation.PropagationManager;
007import org.maltparser.core.syntaxgraph.DependencyStructure;
008import org.maltparser.core.syntaxgraph.edge.Edge;
009import org.maltparser.core.syntaxgraph.node.DependencyNode;
010import org.maltparser.parser.ParserConfiguration;
011import org.maltparser.parser.TransitionSystem;
012import org.maltparser.parser.history.GuideUserHistory;
013import org.maltparser.parser.history.action.ComplexDecisionAction;
014import org.maltparser.parser.history.action.GuideUserAction;
015import org.maltparser.parser.transition.TransitionTable;
016/**
017 * @author Carlos Gomez Rodriguez
018 *
019 */
020public class Planar extends TransitionSystem {
021        protected static final int SHIFT = 1;
022        protected static final int REDUCE = 2;
023        protected static final int RIGHTARC = 3;
024        protected static final int LEFTARC = 4;
025        
026        public Planar(PropagationManager propagationManager) throws MaltChainedException {
027                super(propagationManager);
028        }
029        
030        public void apply(GuideUserAction currentAction, ParserConfiguration config) throws MaltChainedException {
031                PlanarConfig planarConfig = (PlanarConfig)config;
032                Stack<DependencyNode> stack = planarConfig.getStack();
033                Stack<DependencyNode> input = planarConfig.getInput();
034                currentAction.getAction(actionContainers);
035                Edge e = null;
036                switch (transActionContainer.getActionCode()) {
037                case LEFTARC:
038                        e = planarConfig.getDependencyStructure().addDependencyEdge(input.peek().getIndex(), stack.peek().getIndex());
039                        addEdgeLabels(e);
040                        break;
041                case RIGHTARC:
042                        e = planarConfig.getDependencyStructure().addDependencyEdge(stack.peek().getIndex(), input.peek().getIndex());
043                        addEdgeLabels(e);
044                        break;
045                case REDUCE:
046                        stack.pop();
047                        break;
048                default: //SHIFT
049                        stack.push(input.pop()); 
050                        break;
051                }
052        }
053        
054        public GuideUserAction getDeterministicAction(GuideUserHistory history, ParserConfiguration config) throws MaltChainedException {
055                PlanarConfig planarConfig = (PlanarConfig)config;
056                if (planarConfig.getRootHandling() != PlanarConfig.NORMAL && planarConfig.getStack().peek().isRoot()) {
057                        return updateActionContainers(history, Planar.SHIFT, null);
058                }
059                return null;
060        }
061        
062        protected void addAvailableTransitionToTable(TransitionTable ttable) throws MaltChainedException {
063                ttable.addTransition(SHIFT, "SH", false, null);
064                ttable.addTransition(REDUCE, "RE", false, null);
065                ttable.addTransition(RIGHTARC, "RA", true, null);
066                ttable.addTransition(LEFTARC, "LA", true, null);
067        }
068        
069        protected void initWithDefaultTransitions(GuideUserHistory history) throws MaltChainedException {
070                GuideUserAction currentAction = new ComplexDecisionAction(history);
071                
072                transActionContainer.setAction(SHIFT);
073                transActionContainer.setAction(REDUCE);
074                for (int i = 0; i < arcLabelActionContainers.length; i++) {
075                        arcLabelActionContainers[i].setAction(-1);
076                }
077                currentAction.addAction(actionContainers);
078        }
079        
080        public String getName() {
081                return "planar arc-eager";
082        }
083
084        public boolean permissible(GuideUserAction currentAction, ParserConfiguration config) throws MaltChainedException {
085                currentAction.getAction(actionContainers);
086                int trans = transActionContainer.getActionCode();
087                PlanarConfig planarConfig = (PlanarConfig)config;
088                DependencyNode stackPeek = planarConfig.getStack().peek();
089                DependencyNode inputPeek = planarConfig.getInput().peek();
090                DependencyStructure dg = planarConfig.getDependencyGraph();
091                //int rootHandling = planarConfig.getRootHandling();
092                boolean singleHeadConstraint = planarConfig.requiresSingleHead();
093                boolean noCoveredRootsConstraint = planarConfig.requiresNoCoveredRoots();
094                boolean acyclicityConstraint = planarConfig.requiresAcyclicity();
095                boolean connectednessConstraintOnReduce = planarConfig.requiresConnectednessCheckOnReduce();
096                boolean connectednessConstraintOnShift = planarConfig.requiresConnectednessCheckOnShift();
097                if ((trans == LEFTARC || trans == RIGHTARC) && !isActionContainersLabeled()) {
098                        return false;
099                }
100                //if ((trans == LEFTARC || trans == REDUCE) && stackPeek.isRoot()) { 
101                //      return false;
102                //}
103                if (trans == LEFTARC) {
104                        //avoid making root child of something
105                        if ( stackPeek.isRoot() ) 
106                                return false;
107                        //enforce single-head constraint if present
108                        if ( stackPeek.hasHead() && singleHeadConstraint ) 
109                                return false;
110                        //avoid two links being created from and to the same node
111                        if ( stackPeek.hasHead() && dg.getTokenNode(stackPeek.getIndex()).getHead().getIndex() == inputPeek.getIndex() )
112                                return false;
113                        //enforce acyclicity constraint if present
114                        if ( acyclicityConstraint && stackPeek.findComponent().getIndex() == inputPeek.findComponent().getIndex() )
115                                return false;
116                }
117                if (trans == RIGHTARC) {
118                        //enforce single-head constraint if present
119                        if ( inputPeek.hasHead() && singleHeadConstraint )
120                                return false;
121                        //avoid two links being created from and to the same node
122                        if ( inputPeek.hasHead() && dg.getTokenNode(inputPeek.getIndex()).getHead().getIndex() == stackPeek.getIndex() )
123                                return false;
124                        //enforce acyclicity constraint if present
125                        if ( acyclicityConstraint && stackPeek.findComponent().getIndex() == inputPeek.findComponent().getIndex() )
126                                return false;
127                }
128                if (trans == REDUCE) {
129                        //do not reduce the dummy root
130                        if ( stackPeek.isRoot() ) 
131                                return false;
132                        //enforce no-covered-roots constraint if present
133                        if ( !stackPeek.hasHead() && noCoveredRootsConstraint )
134                                return false;
135                        //TODO does this line still make sense? (from Nivre arc-eager)
136                        //if ( !stackPeek.hasHead() && rootHandling == PlanarConfig.STRICT ) 
137                        //      return false;
138                        //enforce connectedness constraint if present
139                        if ( connectednessConstraintOnReduce )
140                        {
141                                boolean path1 = ( stackPeek.findComponent().getIndex() == inputPeek.findComponent().getIndex() );
142                                boolean path2;
143                                if ( planarConfig.getStack().size() < 2 ) path2=false;
144                                else
145                                {
146                                        DependencyNode stackPrev = planarConfig.getStack().get(planarConfig.getStack().size()-2);
147                                        path2 = stackPrev.findComponent().getIndex() == stackPeek.findComponent().getIndex();
148                                }
149                                return path1 || path2;
150                        }
151                }
152                if ( trans == SHIFT )
153                {
154                        if ( connectednessConstraintOnShift && planarConfig.getInput().size() == 1 ) //last word
155                        {
156                                boolean path = ( planarConfig.getDependencyGraph().getTokenNode(1).findComponent().getIndex() == inputPeek.findComponent().getIndex() ); //require connection to 1st
157                                return path;
158                        }
159                }
160                return true;
161        }
162        
163        public GuideUserAction defaultAction(GuideUserHistory history, ParserConfiguration configuration) throws MaltChainedException {
164                return updateActionContainers(history, Planar.SHIFT, null);
165        }
166}