edu.stanford.nlp.trees
Class TreeGraphNode

java.lang.Object
  java.util.AbstractCollection
      edu.stanford.nlp.trees.Tree
          edu.stanford.nlp.trees.TreeGraphNode

All Implemented Interfaces:

Label, Labeled, Scored, Serializable, Iterable, Collection

public class TreeGraphNode
extends Tree

A "treegraph" is a tree with additional directed, labeled arcs between arbitrary pairs of nodes. (So, it's a graph with a tree skeleton.) A TreeGraphNode represents any node in a treegraph. The additional labeled arcs are represented by using MapLabel labels at each node, which contain Maps from arc label strings to Sets of TreeGraphNodes. Each TreeGraphNode should contain a reference to a TreeGraph object, which is a container for the complete treegraph structure.

Author:

Bill MacCartney

See Also:

TreeGraph, Serialized Form

Field Summary

protected TreeGraphNode[]	children Children of this node.
protected MapLabel	label Label for this node.
protected TreeGraphNode	parent Parent of this node.
protected TreeGraph	tg The TreeGraph of which this node is part.
protected static TreeGraphNode[]	ZERO_TGN_CHILDREN A leaf node should have a zero-length array for its children.

Fields inherited from class edu.stanford.nlp.trees.Tree

ZEROCHILDREN

Constructor Summary

TreeGraphNode()
Create a new empty TreeGraphNode.

TreeGraphNode(Label label)
Create a new TreeGraphNode with the supplied label.

TreeGraphNode(Label label, List children)
Create a new TreeGraphNode with the supplied label and list of child nodes.

TreeGraphNode(Tree t, TreeGraphNode parent)
Create a new TreeGraphNode having the same tree structure and label values as an existing tree (but no shared storage).

Method Summary

boolean	addArc(Object arcLabel, TreeGraphNode node) Add a labeled arc from this node to the argument node.
Set	arcLabelsToNode(TreeGraphNode destNode) Finds all arcs between this node and destNode, and returns the Set of Objects which label those arcs.
Object	arcLabelToNode(TreeGraphNode destNode) Returns the label of a single arc between this node and destNode, or null if no such arc exists.
Tree[]	children() Returns an array of the children of this node.
Set	dependencies(Filter f, HeadFinder hf) Return a set of node-node dependencies, represented as Dependency objects, for the Tree.
boolean	equals(Object o) Implements equality for TreeGraphNodes.
static TreeFactory	factory() Return a TreeFactory that produces trees of type TreeGraphNode.
static TreeFactory	factory(LabelFactory lf) Return a TreeFactory that produces trees of type TreeGraphNode, with the Label made by the supplied LabelFactory.
TreeGraphNode	followArcToNode(Object arcLabel) Returns a single TreeGraphNode to which there exists an arc bearing the specified label from this node, or null if no such node exists.
Set	followArcToSet(Object arcLabel) Returns the Set of TreeGraphNodes to which there exist arcs bearing the specified label from this node, or null if no such nodes exist.
TreeGraphNode	headTagNode() Return the node containing the head tag for this node (or null if none), as recorded in this node's MapLabel.
TreeGraphNode	headWordNode() Return the node containing the head word for this node (or null if none), as recorded in this node's MapLabel.
TreeGraphNode	highestNodeWithSameHead()
protected int	index() Get the index for the current node.
protected void	indexNodes() Assign sequential integer indices (starting with 0) to all nodes of the subtree rooted at this TreeGraphNode.
Label	label() Returns the label associated with the current node, or null if there is no label.
static void	main(String[] args) Just for testing.
Tree	parent() Get the parent for the current node.
void	percolateHeads(HeadFinder hf) Uses the specified HeadFinder to determine the heads for this node and all its descendants, and to store references to the head word node and head tag node in this node's MapLabel and the MapLabels of all its descendants.
void	setChildren(Tree[] children) Sets the children of this TreeGraphNode.
protected void	setIndex(int index) Set the index for the current node.
void	setLabel(MapLabel label) Sets the label associated with the current node.
void	setParent(TreeGraphNode parent) Set the parent for the current node.
protected void	setTreeGraph(TreeGraph tg) Set pointer to the TreeGraph of which this node is a part.
String	toOneLineString() Returns a String representation of this node and its subtree as a one-line parenthesized list.
String	toPrettyString(int indentLevel) Returns a String representation of this node and its subtree with one node per line, indented according to indentLevel.
String	toString() Converts parse tree to string in Penn Treebank format.
TreeFactory	treeFactory() Returns a TreeFactory that produces TreeGraphNodes.
protected TreeGraph	treeGraph() Get the TreeGraph of which this node is a part.

Methods inherited from class edu.stanford.nlp.trees.Tree

addChild, addChild, ancestor, cCommands, constituents, constituents, deepCopy, deepCopy, deeperCopy, deeperCopy, dependencies, dependencies, dependencies, depth, dominates, dominationPath, firstChild, flatten, flatten, getChild, getChildrenAsList, getLeaves, getLeaves, getSpan, hashCode, headPreTerminal, headTerminal, indentedListPrint, indentedListPrint, indexOf, insertDtr, isLeaf, isPhrasal, isPrePreTerminal, isPreTerminal, isUnaryRewrite, iterator, joinNode, labelFactory, labels, lastChild, leftCharEdge, localTree, nodeString, numChildren, parent, pathNodeToNode, pennPrint, pennPrint, pennPrint, pennString, preTerminalYield, preTerminalYield, printLocalTree, printLocalTree, prune, prune, removeChild, rightCharEdge, score, setChild, setChildren, setFromString, setLabel, setLabels, setScore, setSpans, setValue, siblings, size, spliceOut, spliceOut, subTreeList, subTrees, subTrees, taggedDependencies, taggedDependencies, taggedDependencies, taggedDependencies, taggedYield, taggedYield, toStringBuffer, transform, transform, typedDependencies, typedDependenciesCollapsed, typedDependenciesCollapsed, upperMostUnary, value, valueOf, valueOf, yield, yield

Methods inherited from class java.util.AbstractCollection

add, addAll, clear, contains, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

label

protected MapLabel label

Label for this node.

parent

protected TreeGraphNode parent

Parent of this node.

children

protected TreeGraphNode[] children

Children of this node.

tg

protected TreeGraph tg

The TreeGraph of which this node is part.

ZERO_TGN_CHILDREN

protected static final TreeGraphNode[] ZERO_TGN_CHILDREN

A leaf node should have a zero-length array for its children. For efficiency, subclasses can use this array as a return value for children() for leaf nodes if desired. Should this be public instead?

Constructor Detail

TreeGraphNode

public TreeGraphNode()

Create a new empty TreeGraphNode.

TreeGraphNode

public TreeGraphNode(Label label)

Create a new TreeGraphNode with the supplied label.

Parameters:

label - the label for this node.

TreeGraphNode

public TreeGraphNode(Label label,
                     List children)

Create a new TreeGraphNode with the supplied label and list of child nodes.

Parameters:

label - the label for this node.

children - the list of child TreeGraphNodes for this node.

TreeGraphNode

public TreeGraphNode(Tree t,
                     TreeGraphNode parent)

Create a new TreeGraphNode having the same tree structure and label values as an existing tree (but no shared storage). Operates recursively to construct an entire subtree.

Parameters:

t - the tree to copy

parent - the parent node

Method Detail

equals

public boolean equals(Object o)

Implements equality for TreeGraphNodes. Unlike Trees, TreeGraphNodes should be considered equal only if they are ==.

Specified by:

equals in interface Collection

Overrides:

equals in class Tree

Parameters:

o - The object to compare with

Returns:

Whether two things are equal

label

public Label label()

Returns the label associated with the current node, or null if there is no label.

Specified by:

label in interface Labeled

Overrides:

label in class Tree

Returns:

the label of the node

setLabel

public void setLabel(MapLabel label)

Sets the label associated with the current node.

Parameters:

label - the new label to use.

index

protected int index()

Get the index for the current node.

setIndex

protected void setIndex(int index)

Set the index for the current node.

indexNodes

protected void indexNodes()

Assign sequential integer indices (starting with 0) to all nodes of the subtree rooted at this TreeGraphNode. The leaves are indexed first, from left to right. Then the internal nodes are indexed, using a pre-order tree traversal.

parent

public Tree parent()

Get the parent for the current node.

Overrides:

parent in class Tree

Returns:

The parent Tree node or null

See Also:

Tree.parent(Tree)

setParent

public void setParent(TreeGraphNode parent)

Set the parent for the current node.

children

public Tree[] children()

Returns an array of the children of this node.

Specified by:

children in class Tree

Returns:

The children of the node

See Also:

Tree.getChildrenAsList()

setChildren

public void setChildren(Tree[] children)

Sets the children of this TreeGraphNode. If given null, this method sets the node's children to the canonical zero-length Tree[] array.

Overrides:

setChildren in class Tree

Parameters:

children - an array of child trees

See Also:

Tree.setChildren(List)

treeGraph

protected TreeGraph treeGraph()

Get the TreeGraph of which this node is a part.

setTreeGraph

protected void setTreeGraph(TreeGraph tg)

Set pointer to the TreeGraph of which this node is a part. Operates recursively to set pointer for all descendants too.

addArc

public boolean addArc(Object arcLabel,
                      TreeGraphNode node)

Add a labeled arc from this node to the argument node.

Parameters:

arcLabel - the Object with which the new arc is to be labeled.

node - the TreeGraphNode to which the new arc should point.

Returns:

true iff the arc did not already exist.

followArcToSet

public Set followArcToSet(Object arcLabel)

Returns the Set of TreeGraphNodes to which there exist arcs bearing the specified label from this node, or null if no such nodes exist.

Parameters:

arcLabel - the Object which labels the arc(s) to be followed.

Returns:

a Set containing only and all the TreeGraphNodes to which there exist arcs bearing the specified label from this node.

followArcToNode

public TreeGraphNode followArcToNode(Object arcLabel)

Returns a single TreeGraphNode to which there exists an arc bearing the specified label from this node, or null if no such node exists. If more than one such node exists, this method will return an arbitrary node from among them; if this is a possibility, you might want to use followArcToSet instead.

Parameters:

arcLabel - a Object containing the label of the arc(s) to be followed

Returns:

a TreeGraphNodes to which there exists an arc bearing the specified label from this node

arcLabelsToNode

public Set arcLabelsToNode(TreeGraphNode destNode)

Finds all arcs between this node and destNode, and returns the Set of Objects which label those arcs. If no such arcs exist, returns an empty Set.

Parameters:

destNode - the destination node

Returns:

the Set of Objects which label arcs between this node and destNode

arcLabelToNode

public Object arcLabelToNode(TreeGraphNode destNode)

Returns the label of a single arc between this node and destNode, or null if no such arc exists. If more than one such arc exists, this method will return an arbitrary arc label from among them; if this is a possibility, you might want to use arcLabelsToNode instead.

Parameters:

destNode - the destination node

Returns:

the Set of Objects which label arcs between this node and destNode

percolateHeads

public void percolateHeads(HeadFinder hf)

Uses the specified HeadFinder to determine the heads for this node and all its descendants, and to store references to the head word node and head tag node in this node's MapLabel and the MapLabels of all its descendants.

Note that, in contrast to Tree.percolateHeads(), which assumes CategoryWordTag labels and therefore stores head words and head tags merely as Strings, this method stores references to the actual nodes. This mitigates potential problems in sentences which contain the same word more than once.

Overrides:

percolateHeads in class Tree

Parameters:

hf - The headfinding algorithm to use

dependencies

public Set dependencies(Filter f,
                        HeadFinder hf)

Return a set of node-node dependencies, represented as Dependency objects, for the Tree.

Overrides:

dependencies in class Tree

Parameters:

hf - The HeadFinder to use to identify the head of constituents. If this is null, then nodes are assumed to already be marked with their heads.

f - Dependencies are excluded for which the Dependency is not accepted by the Filter

Returns:

Set of dependencies (each a Dependency)

headWordNode

public TreeGraphNode headWordNode()

Return the node containing the head word for this node (or null if none), as recorded in this node's MapLabel. (In contrast to CategoryWordTag, we store head words and head tags as references to nodes, not merely as Strings.)

Returns:

the node containing the head word for this node

headTagNode

public TreeGraphNode headTagNode()

Return the node containing the head tag for this node (or null if none), as recorded in this node's MapLabel. (In contrast to CategoryWordTag, we store head words and head tags as references to nodes, not merely as Strings.)

Returns:

the node containing the head tag for this node

highestNodeWithSameHead

public TreeGraphNode highestNodeWithSameHead()

treeFactory

public TreeFactory treeFactory()

Returns a TreeFactory that produces TreeGraphNodes. The Label of this is examined, and providing it is not null, a LabelFactory which will produce that kind of Label is supplied to the TreeFactory. If the Label is null, a MapLabelFactory will be used. The factories returned on different calls are different: a new one is allocated each time.

Specified by:

treeFactory in class Tree

Returns:

a factory to produce treegraphs

factory

public static TreeFactory factory()

Return a TreeFactory that produces trees of type TreeGraphNode. The factory returned is always the same one (a singleton).

Returns:

a factory to produce treegraphs

factory

public static TreeFactory factory(LabelFactory lf)

Return a TreeFactory that produces trees of type TreeGraphNode, with the Label made by the supplied LabelFactory. The factory returned is a different one each time.

Parameters:

lf - The LabelFactory to use

Returns:

a factory to produce treegraphs

toPrettyString

public String toPrettyString(int indentLevel)

Returns a String representation of this node and its subtree with one node per line, indented according to indentLevel.

Parameters:

indentLevel - how many levels to indent (0 for root node)

Returns:

String representation of this subtree

toOneLineString

public String toOneLineString()

Returns a String representation of this node and its subtree as a one-line parenthesized list.

Returns:

String representation of this subtree

toString

public String toString()

Description copied from class: Tree

Converts parse tree to string in Penn Treebank format. Get efficiency by chaining a single StringBuffer through it all.

Specified by:

toString in interface Label

Overrides:

toString in class Tree

Returns:

the tree as a bracketed list on one line

main

public static void main(String[] args)

Just for testing.