001package org.maltparser.core.lw.graph;
002
003import java.util.ArrayList;
004import java.util.Collections;
005import java.util.HashSet;
006import java.util.Iterator;
007import java.util.List;
008import java.util.Map;
009import java.util.Set;
010import java.util.SortedMap;
011import java.util.SortedSet;
012import java.util.TreeMap;
013import java.util.TreeSet;
014
015import org.maltparser.concurrent.graph.dataformat.ColumnDescription;
016import org.maltparser.core.exception.MaltChainedException;
017import org.maltparser.core.helper.HashMap;
018import org.maltparser.core.symbol.SymbolTable;
019import org.maltparser.core.symbol.SymbolTableHandler;
020import org.maltparser.core.syntaxgraph.DependencyStructure;
021import org.maltparser.core.syntaxgraph.LabelSet;
022import org.maltparser.core.syntaxgraph.LabeledStructure;
023import org.maltparser.core.syntaxgraph.edge.Edge;
024import org.maltparser.core.syntaxgraph.node.ComparableNode;
025import org.maltparser.core.syntaxgraph.node.DependencyNode;
026import org.maltparser.core.syntaxgraph.node.Node;
027
028/**
029* A lightweight version of org.maltparser.core.syntaxgraph.node.{Token,Root}
030* 
031* @author Johan Hall
032*/
033public final class LWNode implements DependencyNode, Node {
034        private final LWDependencyGraph graph;
035        private int index;
036//      private final SortedMap<Integer, String> labels;
037        private final Map<Integer, String> labels;
038        private Edge headEdge;
039        
040        protected LWNode(LWNode node) throws LWGraphException {
041                this(node.graph, node);
042        }
043        
044        protected LWNode(LWDependencyGraph _graph, LWNode node) throws LWGraphException {
045                if (_graph == null) {
046                        throw new LWGraphException("The graph node must belong to a dependency graph.");
047                }
048                this.graph = _graph;
049                this.index = node.index;
050//              this.labels = new TreeMap<Integer, String>(node.labels);
051                this.labels = new HashMap<Integer, String>(node.labels);
052                this.headEdge = node.headEdge;
053        }
054        
055        protected LWNode(LWDependencyGraph _graph, int _index) throws LWGraphException {
056                if (_graph == null) {
057                        throw new LWGraphException("The graph node must belong to a dependency graph.");
058                }
059                if (_index < 0) {
060                        throw new LWGraphException("Not allowed to have negative node index");
061                }
062                this.graph = _graph;
063                this.index = _index;
064//              this.labels = new TreeMap<Integer, String>();
065                this.labels = new HashMap<Integer, String>();
066                this.headEdge = null;
067        }
068        
069//      public void setHeadIndex(int _headIndex) throws LWGraphException {
070//              if (this.index == 0 && _headIndex != -1) {
071//                      throw new LWGraphException("Not allowed to add head to a root node.");
072//              }
073//              if (this.index == _headIndex) {
074//                      throw new LWGraphException("Not allowed to add head to itself");
075//              }
076//              this.headIndex = _headIndex;
077//      }
078//      
079//      public void removeHeadIndex() throws LWGraphException {
080//              this.headIndex = -1;
081//              for (Integer i : labels.keySet()) {
082//                      if (graph.getDataFormat().getColumnDescription(i).getCategory() == ColumnDescription.DEPENDENCY_EDGE_LABEL) {
083//                              this.labels.remove(i);
084//                      }
085//              }
086//      }
087        
088        protected DependencyStructure getGraph() {
089                return graph;
090        }
091        
092        public int getIndex() {
093                return this.index;
094        }
095        
096        @Override
097        public void setIndex(int index) throws MaltChainedException {
098                this.index = index;
099        }
100
101        public String getLabel(int columnPosition) {
102                if (labels.containsKey(columnPosition)) {
103                        return labels.get(columnPosition);
104                } else if (graph.getDataFormat().getColumnDescription(columnPosition).getCategory() == ColumnDescription.IGNORE) {
105                        return graph.getDataFormat().getColumnDescription(columnPosition).getDefaultOutput();
106                }
107                return "";
108        }
109        
110        public String getLabel(String columnName) {
111                ColumnDescription column = graph.getDataFormat().getColumnDescription(columnName);
112                if (column != null) {
113                        return getLabel(column.getPosition());
114                }
115                return "";
116        }
117        
118        public String getLabel(ColumnDescription column) {
119                return getLabel(column.getPosition());
120        }
121        
122        public boolean hasLabel(int columnPosition) {
123                return labels.containsKey(columnPosition);
124        }
125        
126        public boolean hasLabel(String columnName) {
127                ColumnDescription column = graph.getDataFormat().getColumnDescription(columnName);
128                if (column != null) {
129                        return hasLabel(column.getPosition());
130                }
131                return false;
132        }
133        
134        public boolean hasLabel(ColumnDescription column) {
135                return labels.containsKey(column.getPosition());
136        }
137        
138        public boolean isLabeled() {
139                for (Integer key : labels.keySet()) {
140                        if (graph.getDataFormat().getColumnDescription(key).getCategory() == ColumnDescription.INPUT) {
141                                return true;
142                        }
143                }
144                return false;
145        }
146        
147        public boolean isHeadLabeled() {
148                if (headEdge == null) {
149                        return false;
150                }
151                return headEdge.isLabeled();
152        }
153        
154        public int getHeadIndex() {
155                if (headEdge == null) {
156                        return -1;
157                }
158                return headEdge.getSource().getIndex();
159        }
160        
161        public SortedMap<ColumnDescription, String> getLabels() {
162                SortedMap<ColumnDescription, String> nodeLabels = Collections.synchronizedSortedMap(new TreeMap<ColumnDescription, String>());
163                for (Integer key : labels.keySet()) {
164                        nodeLabels.put(graph.getDataFormat().getColumnDescription(key), labels.get(key));
165                }
166                return nodeLabels;
167        }
168        
169//      public SortedMap<ColumnDescription, String> getEdgeLabels() {
170//              SortedMap<ColumnDescription, String> edgeLabels = Collections.synchronizedSortedMap(new TreeMap<ColumnDescription, String>());
171//              for (Integer key : labels.keySet()) {
172//                      if (graph.getDataFormat().getColumnDescription(key).getCategory() == ColumnDescription.DEPENDENCY_EDGE_LABEL) {
173//                              edgeLabels.put(graph.getDataFormat().getColumnDescription(key), labels.get(key));
174//                      }
175//              }
176//              return edgeLabels;
177//      }
178        
179        public DependencyNode getPredecessor() {
180                return index > 1 ? graph.getNode(index - 1) : null;
181        }
182        
183        public DependencyNode getSuccessor() {
184                return graph.getNode(index + 1);
185        }
186        
187        public boolean isRoot() {
188                return index == 0;
189        }
190        
191        public boolean hasAtMostOneHead() {
192                return true;
193        }
194        
195        public boolean hasHead() {
196                return headEdge != null;
197        }
198        
199        public boolean hasDependent() {
200                return graph.hasDependent(index);
201        }
202        
203        public boolean hasLeftDependent() {
204                return graph.hasLeftDependent(index);
205        }
206        
207        public boolean hasRightDependent() {
208                return graph.hasRightDependent(index);
209        }
210        
211        public SortedSet<DependencyNode> getHeads() {
212                SortedSet<DependencyNode> heads = Collections.synchronizedSortedSet(new TreeSet<DependencyNode>());
213                DependencyNode head = getHead();
214                if (head != null) {
215                        heads.add(head);
216                }
217                return heads; 
218        }
219        
220        public DependencyNode getHead() {
221                if (headEdge == null) {
222                        return null;
223                }
224                return graph.getNode(getHeadIndex());
225        }
226
227        public DependencyNode getLeftDependent(int leftDependentIndex) {        
228                List<DependencyNode> leftDependents = graph.getListOfLeftDependents(index);
229                if (leftDependentIndex >= 0 && leftDependentIndex < leftDependents.size()) {
230                        return leftDependents.get(leftDependentIndex);
231                }
232                return null;
233        }
234
235        public int getLeftDependentCount() {
236                return graph.getListOfLeftDependents(index).size();
237        }
238
239        public SortedSet<DependencyNode> getLeftDependents() {
240                return graph.getSortedSetOfLeftDependents(index);
241        }
242
243        public List<DependencyNode> getListOfLeftDependents() {
244                return graph.getListOfLeftDependents(index);
245        }
246        
247        public DependencyNode getLeftSibling() {
248                if (headEdge == null) {
249                        return null;
250                }
251                
252                int nodeDepedentPosition = 0;
253                List<DependencyNode> headDependents = getHead().getListOfDependents();
254                for (int i = 0; i < headDependents.size(); i++) {
255                        if (headDependents.get(i).getIndex() == index) {
256                                nodeDepedentPosition = i;
257                                break;
258                        }
259                }
260                
261                return (nodeDepedentPosition > 0) ? headDependents.get(nodeDepedentPosition - 1) : null;
262        }
263
264        public DependencyNode getSameSideLeftSibling() {
265                if (headEdge == null) {
266                        return null;
267                }
268                
269                List<DependencyNode> headDependents;
270                if (index < getHeadIndex()) {
271                        headDependents = getHead().getListOfLeftDependents();
272                } else { //(index > headIndex)
273                        headDependents = getHead().getListOfRightDependents();
274                }
275                int nodeDepedentPosition = 0;
276                for (int i = 0; i < headDependents.size(); i++) {
277                        if (headDependents.get(i).getIndex() == index) {
278                                nodeDepedentPosition = i;
279                                break;
280                        }
281                }
282                return (nodeDepedentPosition > 0) ? headDependents.get(nodeDepedentPosition - 1) : null;
283        }
284
285        public DependencyNode getClosestLeftDependent() {
286                List<DependencyNode> leftDependents = graph.getListOfLeftDependents(index);
287                return (leftDependents.size() > 0) ? leftDependents.get(leftDependents.size() - 1) : null;
288        }
289        
290        public DependencyNode getLeftmostDependent() {
291                List<DependencyNode> leftDependents = graph.getListOfLeftDependents(index);
292                return (leftDependents.size() > 0) ? leftDependents.get(0) : null;
293        }
294        
295        public DependencyNode getRightDependent(int rightDependentIndex) {      
296                List<DependencyNode> rightDependents = graph.getListOfRightDependents(index);
297                if (rightDependentIndex >= 0 && rightDependentIndex < rightDependents.size()) {
298                        return rightDependents.get(rightDependents.size() - 1 - rightDependentIndex);
299                }
300                return null;
301        }
302        
303        public int getRightDependentCount() {
304                return graph.getListOfRightDependents(index).size();
305        }
306
307        public SortedSet<DependencyNode> getRightDependents() {
308                return graph.getSortedSetOfRightDependents(index);
309        }
310
311        public List<DependencyNode> getListOfRightDependents() {
312                return graph.getListOfRightDependents(index);
313        }
314        
315        public DependencyNode getRightSibling() {
316                if (headEdge == null) {
317                        return null;
318                }
319                
320                List<DependencyNode> headDependents = getHead().getListOfDependents();
321                int nodeDepedentPosition = headDependents.size() - 1;
322                for (int i = headDependents.size() - 1; i >= 0 ; i--) {
323                        if (headDependents.get(i).getIndex() == index) {
324                                nodeDepedentPosition = i;
325                                break;
326                        }
327                }
328                
329                return (nodeDepedentPosition < headDependents.size() - 1) ? headDependents.get(nodeDepedentPosition + 1) : null;
330        }
331
332        public DependencyNode getSameSideRightSibling() {
333                if (headEdge == null) {
334                        return null;
335                }
336                
337                List<DependencyNode> headDependents;
338                if (index < getHeadIndex()) {
339                        headDependents = getHead().getListOfLeftDependents();
340                } else {
341                        headDependents = getHead().getListOfRightDependents();
342                }
343                int nodeDepedentPosition = headDependents.size() - 1;
344                for (int i = headDependents.size() - 1; i >= 0 ; i--) {
345                        if (headDependents.get(i).getIndex() == index) {
346                                nodeDepedentPosition = i;
347                                break;
348                        }
349                }
350                
351                return (nodeDepedentPosition < headDependents.size() - 1) ? headDependents.get(nodeDepedentPosition + 1) : null;        
352        }
353
354        public DependencyNode getClosestRightDependent() {
355                List<DependencyNode> rightDependents = graph.getListOfRightDependents(index);
356                return (rightDependents.size() > 0) ? rightDependents.get(0) : null;
357        }
358        
359        public DependencyNode getRightmostDependent(){
360                List<DependencyNode> rightDependents = graph.getListOfRightDependents(index);
361                return (rightDependents.size() > 0) ? rightDependents.get(rightDependents.size() - 1) : null;
362        }
363        
364        public SortedSet<DependencyNode> getDependents() {
365                return graph.getSortedSetOfDependents(index);
366        }
367        
368        public List<DependencyNode> getListOfDependents() {
369                return graph.getListOfDependents(index);
370        }
371        
372        public int getInDegree() {
373                if (hasHead()) {
374                        return 1;
375                }
376                return 0;
377        }
378        
379        public int getOutDegree() {
380                return graph.getListOfDependents(index).size();
381        }
382        
383        public DependencyNode getAncestor() throws MaltChainedException {
384                if (!this.hasHead()) {
385                        return this;
386                }
387                
388                DependencyNode tmp = this;
389                while (tmp.hasHead()) {
390                        tmp = tmp.getHead();
391                }
392                return tmp;
393        }
394        
395        public DependencyNode getProperAncestor() throws MaltChainedException {
396                if (!this.hasHead()) {
397                        return null;
398                }
399                
400                DependencyNode tmp = this;
401                while (tmp.hasHead() && !tmp.isRoot()) {
402                        tmp = tmp.getHead();
403                }
404                return tmp;
405        }
406        
407        public boolean hasAncestorInside(int left, int right) throws MaltChainedException {
408                if (index == 0) {
409                        return false;
410                }
411                DependencyNode tmp = this;
412                if (tmp.getHead() != null) {
413                        tmp = tmp.getHead();
414                        if (tmp.getIndex() >= left && tmp.getIndex() <= right) {
415                                return true;
416                        }
417                }
418                return false;
419        }
420        
421        public boolean isProjective() throws MaltChainedException {
422                int headIndex = getHeadIndex();
423                if (headIndex > 0) {
424                        final DependencyNode head = getHead();
425                        if (headIndex < index) {
426                                DependencyNode terminals = head;
427                                DependencyNode tmp = null;
428                                while (true) {
429                                        if (terminals == null || terminals.getSuccessor() == null) {
430                                                return false;
431                                        }
432                                        if (terminals.getSuccessor() == this) {
433                                                break;
434                                        }
435                                        tmp = terminals = terminals.getSuccessor();
436                                        while (tmp != this && tmp != head) {
437                                                if (!tmp.hasHead()) {
438                                                        return false;
439                                                }
440                                                tmp = tmp.getHead();
441                                        }
442                                }
443                        } else {
444                                DependencyNode terminals = this;
445                                DependencyNode tmp = null;
446                                while (true) {
447                                        if (terminals == null || terminals.getSuccessor() == null) {
448                                                return false;
449                                        }
450                                        if (terminals.getSuccessor() == head) {
451                                                break;
452                                        }
453                                        tmp = terminals = terminals.getSuccessor();
454                                        while (tmp != this && tmp != head) {
455                                                if (!tmp.hasHead()) {
456                                                        return false;
457                                                }
458                                                tmp = tmp.getHead();
459                                        }
460                                }
461                        }
462                }
463                return true;
464        }
465        
466        public int getDependencyNodeDepth() throws MaltChainedException {
467                DependencyNode tmp = this;
468                int depth = 0;
469                while (tmp.hasHead()) {
470                        depth++;
471                        tmp = tmp.getHead();
472                }
473                return depth;
474        }
475
476        @Override
477        public int getCompareToIndex() {
478                return index;
479        }
480
481        @Override
482        public ComparableNode getLeftmostProperDescendant() throws MaltChainedException {
483                ComparableNode candidate = null;
484                List<DependencyNode> dependents = graph.getListOfDependents(index);
485                for (int i = 0; i < dependents.size(); i++) {
486                        final DependencyNode dep = dependents.get(i);
487                        if (candidate == null || dep.getIndex() < candidate.getIndex()) {
488                                candidate = dep;
489                        }
490                        final ComparableNode tmp = dep.getLeftmostProperDescendant();
491                        if (tmp == null) {
492                                continue;
493                        }
494                        if (candidate == null || tmp.getIndex() < candidate.getIndex()) {
495                                candidate = tmp;
496                        }
497                        if (candidate.getIndex() == 1) {
498                                return candidate;
499                        }
500                }
501                return candidate;
502        }
503
504        @Override
505        public ComparableNode getRightmostProperDescendant() throws MaltChainedException {
506                ComparableNode candidate = null;
507                List<DependencyNode> dependents = graph.getListOfDependents(index);
508                for (int i = 0; i < dependents.size(); i++) {
509                        final DependencyNode dep = dependents.get(i);
510                        if (candidate == null || dep.getIndex() > candidate.getIndex()) {
511                                candidate = dep;
512                        }
513                        final ComparableNode tmp = dep.getRightmostProperDescendant();
514                        if (tmp == null) {
515                                continue;
516                        }
517                        if (candidate == null || tmp.getIndex() > candidate.getIndex()) {
518                                candidate = tmp;
519                        }
520                }
521                return candidate;
522        }
523        @Override
524        public int getLeftmostProperDescendantIndex() throws MaltChainedException {
525                ComparableNode node = getLeftmostProperDescendant();
526                return (node != null)?node.getIndex():-1;
527        }
528        @Override
529        public int getRightmostProperDescendantIndex() throws MaltChainedException {
530                ComparableNode node = getRightmostProperDescendant();
531                return (node != null)?node.getIndex():-1;
532        }
533
534        @Override
535        public ComparableNode getLeftmostDescendant() throws MaltChainedException {
536                ComparableNode candidate = this;
537                List<DependencyNode> dependents = graph.getListOfDependents(index);
538                for (int i = 0; i < dependents.size(); i++) {
539                        final DependencyNode dep = dependents.get(i);
540                        if (dep.getIndex() < candidate.getIndex()) {
541                                candidate = dep;
542                        }
543                        final ComparableNode tmp = dep.getLeftmostDescendant();
544                        if (tmp == null) {
545                                continue;
546                        }
547                        if (tmp.getIndex() < candidate.getIndex()) {
548                                candidate = tmp;
549                        }
550                        if (candidate.getIndex() == 1) {
551                                return candidate;
552                        }
553                }
554                return candidate;
555        }
556
557        @Override
558        public ComparableNode getRightmostDescendant() throws MaltChainedException {
559                ComparableNode candidate = this;
560                List<DependencyNode> dependents = graph.getListOfDependents(index);
561                for (int i = 0; i < dependents.size(); i++) {
562                        final DependencyNode dep = dependents.get(i);
563                        if (dep.getIndex() > candidate.getIndex() ) {
564                                candidate = dep;
565                        }
566                        final ComparableNode tmp = dep.getRightmostDescendant();
567                        if (tmp == null) {
568                                continue;
569                        }
570                        if (tmp.getIndex() > candidate.getIndex() ) {
571                                candidate = tmp;
572                        }
573                }
574                return candidate;
575        }
576
577        @Override
578        public int getLeftmostDescendantIndex() throws MaltChainedException {
579                ComparableNode node = getLeftmostDescendant();
580                return (node != null)?node.getIndex():this.getIndex();
581        }
582        @Override
583        public int getRightmostDescendantIndex() throws MaltChainedException {
584                ComparableNode node = getRightmostDescendant();
585                return (node != null)?node.getIndex():this.getIndex();
586        }
587
588        @Override
589        public SortedSet<Edge> getIncomingSecondaryEdges() throws MaltChainedException {
590                throw new LWGraphException("Not implemented in the light-weight dependency graph package");
591        }
592
593        @Override
594        public SortedSet<Edge> getOutgoingSecondaryEdges() throws MaltChainedException {
595                throw new LWGraphException("Not implemented in the light-weight dependency graph package");
596        }
597        
598        @Override
599        public Set<Edge> getHeadEdges()  {
600                SortedSet<Edge> edges = Collections.synchronizedSortedSet(new TreeSet<Edge>());
601                if (hasHead()) {
602                        edges.add(headEdge);
603                }
604                return edges;
605        }
606
607        @Override
608        public Edge getHeadEdge() {
609                if (!hasHead()) {
610                        return null;
611                }
612                return headEdge;
613        }
614        
615        @Override
616        public void addHeadEdgeLabel(SymbolTable table, String symbol)
617                        throws MaltChainedException {
618                if (headEdge != null) {
619                        headEdge.addLabel(table, symbol);
620                }
621        }
622
623        @Override
624        public void addHeadEdgeLabel(SymbolTable table, int code) throws MaltChainedException {
625                if (headEdge != null) {
626                        headEdge.addLabel(table, code);
627                }
628        }
629
630        @Override
631        public void addHeadEdgeLabel(LabelSet labelSet) throws MaltChainedException {
632                if (headEdge != null) {
633                        headEdge.addLabel(labelSet);
634                }
635        }
636
637        @Override
638        public boolean hasHeadEdgeLabel(SymbolTable table)
639                        throws MaltChainedException {
640                if (headEdge != null) {
641                        return headEdge.hasLabel(table);
642                }
643                return false;
644        }
645
646        @Override
647        public String getHeadEdgeLabelSymbol(SymbolTable table) throws MaltChainedException {
648                if (headEdge != null) {
649                        return headEdge.getLabelSymbol(table);
650                }
651                return null;
652        }
653
654        @Override
655        public int getHeadEdgeLabelCode(SymbolTable table)
656                        throws MaltChainedException {
657                if (headEdge != null) {
658                        return headEdge.getLabelCode(table);
659                }
660                return 0;
661        }
662
663        @Override
664        public Set<SymbolTable> getHeadEdgeLabelTypes() throws MaltChainedException {
665                if (headEdge != null) {
666                        return headEdge.getLabelTypes();
667                }
668                return new HashSet<SymbolTable>();
669        }
670
671        @Override
672        public LabelSet getHeadEdgeLabelSet() throws MaltChainedException {
673                if (headEdge != null) {
674                        return headEdge.getLabelSet();
675                }
676                return new LabelSet();
677        }
678
679        
680        @Override
681        public void addIncomingEdge(Edge in) throws MaltChainedException {
682                headEdge = in;
683        }
684
685        @Override
686        public void addOutgoingEdge(Edge out) throws MaltChainedException {
687                throw new LWGraphException("Not implemented in the light-weight dependency graph package");
688                
689        }
690
691        @Override
692        public void removeIncomingEdge(Edge in) throws MaltChainedException {
693                if (headEdge.equals(in)) {
694                        headEdge = null;
695                }
696        }
697
698        @Override
699        public void removeOutgoingEdge(Edge out) throws MaltChainedException {
700                throw new LWGraphException("Not implemented in the light-weight dependency graph package");
701        }
702
703        @Override
704        public Iterator<Edge> getIncomingEdgeIterator() {
705                return getHeadEdges().iterator();
706        }
707
708        @Override
709        public Iterator<Edge> getOutgoingEdgeIterator() {
710                List<DependencyNode> dependents = getListOfDependents();
711                List<Edge> outEdges = new ArrayList<Edge>(dependents.size());
712                for (int i = 0; i < dependents.size(); i++) {
713                        try {
714                                outEdges.add(dependents.get(i).getHeadEdge());
715                        } catch (MaltChainedException e) {
716                                e.printStackTrace();
717                        }
718                }
719                return outEdges.iterator();
720        }
721
722        @Override
723        public void setRank(int r) {}
724
725        @Override
726        public DependencyNode getComponent() {
727                return null;
728        }
729
730        @Override
731        public void setComponent(DependencyNode x) {}
732
733        public DependencyNode findComponent() {
734                return graph.findComponent(index);
735        }
736        
737        public int getRank() {
738                return graph.getRank(index);
739        }
740        
741        public boolean isHeadEdgeLabeled() {
742                if (headEdge != null) {
743                        return headEdge.isLabeled();
744                }
745                return false;
746        }
747        
748        public int nHeadEdgeLabels() {
749                if (headEdge != null) {
750                        return headEdge.nLabels();
751                }
752                return 0;
753        }
754        
755        public void addColumnLabels(String[] columnLabels) throws MaltChainedException {
756                this.addColumnLabels(columnLabels, true);
757        }
758        
759        public void addColumnLabels(String[] columnLabels, boolean addEdges) throws MaltChainedException {
760                if (addEdges == true) {
761                        SortedMap<ColumnDescription,String> edgeLabels = new TreeMap<ColumnDescription,String>();
762                        int tmpHeadIndex = -1;
763                        if (columnLabels != null) {
764                                for (int i = 0; i < columnLabels.length; i++) {
765                                        ColumnDescription column = graph.getDataFormat().getColumnDescription(i);
766                                        if (column.getCategory() == ColumnDescription.HEAD) {
767                                                tmpHeadIndex = Integer.parseInt(columnLabels[i]);
768                                        } else if (column.getCategory() == ColumnDescription.INPUT) {
769                                                addLabel(graph.getSymbolTables().addSymbolTable(column.getName()), columnLabels[i]);
770                                        } else if (column.getCategory() == ColumnDescription.DEPENDENCY_EDGE_LABEL) {
771                                                edgeLabels.put(column, columnLabels[i]);
772                                        }
773                                }
774                        }
775                        if (tmpHeadIndex == -1) {
776                                this.headEdge = null;
777                        } else {
778                                if (tmpHeadIndex < -1) {
779                                        throw new LWGraphException("Not allowed to have head index less than -1.");
780                                }
781                                if (this.index == 0 && tmpHeadIndex != -1) {
782                                        throw new LWGraphException("Not allowed to add head to a root node.");
783                                }
784                                if (this.index == tmpHeadIndex) {
785                                        throw new LWGraphException("Not allowed to add head to itself");
786                                }
787                                this.headEdge = new LWEdge(this.graph.getNode(tmpHeadIndex), this, edgeLabels);
788                        }
789                } else {
790                        if (columnLabels != null) {
791                                for (int i = 0; i < columnLabels.length; i++) {
792                                        ColumnDescription column = graph.getDataFormat().getColumnDescription(i);
793                                        if (column.getCategory() == ColumnDescription.INPUT) {
794                                                addLabel(graph.getSymbolTables().addSymbolTable(column.getName()), columnLabels[i]);
795                                        } 
796                                }
797                        }
798                        this.headEdge = null;
799                }
800        }
801        
802        /**
803         * Adds a label (a string value) to the symbol table and to the graph element. 
804         * 
805         * @param table the symbol table
806         * @param symbol a label symbol
807         * @throws MaltChainedException
808         */
809        public void addLabel(SymbolTable table, String symbol) throws MaltChainedException {
810                ColumnDescription column = graph.getDataFormat().getColumnDescription(table.getName());
811                table.addSymbol(symbol);
812                labels.put(column.getPosition(), symbol);
813        }
814        
815        /**
816         * Adds a label (an integer value) to the symbol table and to the graph element.
817         * 
818         * @param table the symbol table
819         * @param code a label code
820         * @throws MaltChainedException
821         */
822        public void addLabel(SymbolTable table, int code) throws MaltChainedException {
823                addLabel(table, table.getSymbolCodeToString(code));
824        }
825        
826        /**
827         * Adds the labels of the label set to the label set of the graph element.
828         * 
829         * @param labels a label set.
830         * @throws MaltChainedException
831         */
832        public void addLabel(LabelSet labels) throws MaltChainedException {
833                for (SymbolTable table : labels.keySet()) {
834                        addLabel(table, labels.get(table));
835                }
836        }
837        
838        /**
839         * Returns <i>true</i> if the graph element has a label for the symbol table, otherwise <i>false</i>.
840         * 
841         * @param table the symbol table
842         * @return <i>true</i> if the graph element has a label for the symbol table, otherwise <i>false</i>.
843         * @throws MaltChainedException
844         */
845        public boolean hasLabel(SymbolTable table) throws MaltChainedException {
846                ColumnDescription column = graph.getDataFormat().getColumnDescription(table.getName());
847                return labels.containsKey(column.getPosition());
848        }
849        
850        /**
851         * Returns the label symbol(a string representation) of the symbol table if it exists, otherwise 
852         * an exception is thrown.
853         * 
854         * @param table the symbol table
855         * @return the label (a string representation) of the symbol table if it exists.
856         * @throws MaltChainedException
857         */
858        public String getLabelSymbol(SymbolTable table) throws MaltChainedException {
859                ColumnDescription column = graph.getDataFormat().getColumnDescription(table.getName());
860                return labels.get(column.getPosition());
861        }
862        
863        /**
864         * Returns the label code (an integer representation) of the symbol table if it exists, otherwise 
865         * an exception is thrown.
866         * 
867         * @param table the symbol table
868         * @return the label code (an integer representation) of the symbol table if it exists
869         * @throws MaltChainedException
870         */
871        public int getLabelCode(SymbolTable table) throws MaltChainedException {
872                ColumnDescription column = graph.getDataFormat().getColumnDescription(table.getName());
873                return table.getSymbolStringToCode(labels.get(column.getPosition()));
874        }
875        
876        /**
877         * Returns the number of labels of the graph element.
878         * 
879         * @return the number of labels of the graph element.
880         */
881        public int nLabels() {
882                return labels.size();
883        }
884        
885        /**
886         * Returns a set of symbol tables (labeling functions or label types) that labels the graph element.
887         * 
888         * @return a set of symbol tables (labeling functions or label types)
889         */
890        public Set<SymbolTable> getLabelTypes() {
891                Set<SymbolTable> labelTypes = new HashSet<SymbolTable>();
892                SymbolTableHandler symbolTableHandler = getBelongsToGraph().getSymbolTables();
893                SortedSet<ColumnDescription> selectedColumns = graph.getDataFormat().getSelectedColumnDescriptions(labels.keySet());
894                for (ColumnDescription column : selectedColumns) {
895                        try {
896                                labelTypes.add(symbolTableHandler.getSymbolTable(column.getName()));
897                        } catch (MaltChainedException e) {
898                                e.printStackTrace();
899                        }
900                }
901                return labelTypes;
902        }
903        
904        /**
905         * Returns the label set.
906         * 
907         * @return the label set.
908         */
909        public LabelSet getLabelSet() {
910                SymbolTableHandler symbolTableHandler = getBelongsToGraph().getSymbolTables();
911                LabelSet labelSet = new LabelSet();
912                SortedSet<ColumnDescription> selectedColumns = graph.getDataFormat().getSelectedColumnDescriptions(labels.keySet());
913                for (ColumnDescription column : selectedColumns) {
914                        try {
915                                SymbolTable table = symbolTableHandler.getSymbolTable(column.getName());
916                                int code = table.getSymbolStringToCode(labels.get(column.getPosition()));
917                                labelSet.put(table, code);
918                        } catch (MaltChainedException e) {
919                                e.printStackTrace();
920                        }
921                }
922                return labelSet;
923        }
924        
925        public void removeLabel(SymbolTable table) throws MaltChainedException {
926                ColumnDescription column = graph.getDataFormat().getColumnDescription(table.getName());
927                labels.remove(column.getPosition());
928        }
929        
930        public void removeLabels() throws MaltChainedException {
931                labels.clear();
932        }
933        
934        /**
935         * Returns the graph (structure) in which the graph element belongs to. 
936         * 
937         * @return the graph (structure) in which the graph element belongs to. 
938         */
939        public LabeledStructure getBelongsToGraph()  {
940                return graph;
941        }
942        
943        public void setBelongsToGraph(LabeledStructure belongsToGraph)  {}
944        
945
946        /**
947         * Resets the graph element.
948         * 
949         * @throws MaltChainedException
950         */
951        public void clear() throws MaltChainedException {
952                labels.clear();
953        }
954        
955        @Override
956        public int compareTo(ComparableNode that) {
957                final int BEFORE = -1;
958            final int EQUAL = 0;
959            final int AFTER = 1;
960            if (this == that) return EQUAL;
961            if (this.index < that.getIndex()) return BEFORE;
962            if (this.index > that.getIndex()) return AFTER;
963            return EQUAL;
964        }
965
966        @Override
967        public int hashCode() {
968                final int prime = 31;
969                int result = 1;
970                result = prime * result
971                                + ((headEdge == null) ? 0 : headEdge.hashCode());
972                result = prime * result + index;
973                result = prime * result + ((labels == null) ? 0 : labels.hashCode());
974                return result;
975        }
976
977        @Override
978        public boolean equals(Object obj) {
979                if (this == obj)
980                        return true;
981                if (obj == null)
982                        return false;
983                if (getClass() != obj.getClass())
984                        return false;
985                LWNode other = (LWNode) obj;
986                if (headEdge == null) {
987                        if (other.headEdge != null)
988                                return false;
989                } else if (!headEdge.equals(other.headEdge))
990                        return false;
991                if (index != other.index)
992                        return false;
993                if (labels == null) {
994                        if (other.labels != null)
995                                return false;
996                } else if (!labels.equals(other.labels))
997                        return false;
998                return true;
999        }
1000
1001        public String toString() {
1002                final StringBuilder sb = new StringBuilder();
1003                for (int i = 0; i < graph.getDataFormat().numberOfColumns(); i++) {
1004                        ColumnDescription column = graph.getDataFormat().getColumnDescription(i);
1005                        if (!column.isInternal()) {
1006                                if (column.getCategory() == ColumnDescription.HEAD) {
1007                                        sb.append(getHeadIndex());
1008                                } else if (column.getCategory() == ColumnDescription.INPUT) {
1009                                        sb.append(labels.get(column.getPosition()));
1010                                } else if (column.getCategory() == ColumnDescription.DEPENDENCY_EDGE_LABEL) {
1011                                        if (headEdge != null) {
1012                                                sb.append(((LWEdge)headEdge).getLabel(column));
1013                                        } else {
1014                                                sb.append(column.getDefaultOutput());
1015                                        }
1016                                } else if (column.getCategory() == ColumnDescription.IGNORE) {
1017                                        sb.append(column.getDefaultOutput());
1018                                }
1019                                sb.append('\t');
1020                        }
1021                }
1022                sb.setLength((sb.length() > 0)?sb.length()-1:0);
1023                return sb.toString();
1024        }
1025}