package org.maltparserx.core.syntaxgraph;
import java.util.Iterator;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.TreeSet;
import org.maltparserx.core.exception.MaltChainedException;
import org.maltparserx.core.pool.ObjectPoolList;
import org.maltparserx.core.symbol.SymbolTable;
import org.maltparserx.core.symbol.SymbolTableHandler;
import org.maltparserx.core.syntaxgraph.edge.Edge;
import org.maltparserx.core.syntaxgraph.edge.GraphEdge;
import org.maltparserx.core.syntaxgraph.node.ComparableNode;
import org.maltparserx.core.syntaxgraph.node.DependencyNode;
import org.maltparserx.core.syntaxgraph.node.Node;
import org.maltparserx.core.syntaxgraph.node.Root;
/**
*
*
* @author Johan Hall
*/
public class DependencyGraph extends Sentence implements DependencyStructure {
private final ObjectPoolList<Edge> edgePool;
private final SortedSet<Edge> graphEdges;
private final Root root;
private boolean singleHeadedConstraint;
private RootLabels rootLabels;
public DependencyGraph(SymbolTableHandler symbolTables) throws MaltChainedException {
super(symbolTables);
setSingleHeadedConstraint(true);
root = new Root();
root.setBelongsToGraph(this);
graphEdges = new TreeSet<Edge>();
edgePool = new ObjectPoolList<Edge>() {
protected Edge create() { return new GraphEdge(); }
public void resetObject(Edge o) throws MaltChainedException { o.clear(); }
};
clear();
}
public DependencyNode addDependencyNode() throws MaltChainedException {
return addTokenNode();
}
public DependencyNode addDependencyNode(int index) throws MaltChainedException {
if (index == 0) {
return root;
}
return addTokenNode(index);
}
public DependencyNode getDependencyNode(int index) throws MaltChainedException {
if (index == 0) {
return root;
}
return getTokenNode(index);
}
public int nDependencyNode() {
return nTokenNode() + 1;
}
public int getHighestDependencyNodeIndex() {
if (hasTokens()) {
return getHighestTokenIndex();
}
return 0;
}
public Edge addDependencyEdge(int headIndex, int dependentIndex) throws MaltChainedException {
DependencyNode head = null;
DependencyNode dependent = null;
if (headIndex == 0) {
head = root;
} else { // if (headIndex > 0) {
head = getOrAddTerminalNode(headIndex);
}
if (dependentIndex > 0) {
dependent = getOrAddTerminalNode(dependentIndex);
}
return addDependencyEdge(head, dependent);
}
protected Edge addDependencyEdge(DependencyNode head, DependencyNode dependent) throws MaltChainedException {
if (head == null || dependent == null) {
throw new SyntaxGraphException("Head or dependent node is missing.");
} else if (!dependent.isRoot()) {
if (singleHeadedConstraint && dependent.hasHead()) {
return moveDependencyEdge(head, dependent);
}
final DependencyNode hc = ((DependencyNode)head).findComponent();
final DependencyNode dc = ((DependencyNode)dependent).findComponent();
if (hc != dc) {
link(hc, dc);
numberOfComponents--;
}
Edge e = edgePool.checkOut();
e.setBelongsToGraph(this);
e.setEdge((Node)head, (Node)dependent, Edge.DEPENDENCY_EDGE);
graphEdges.add(e);
return e;
} else {
throw new SyntaxGraphException("Head node is not a root node or a terminal node.");
}
}
public Edge moveDependencyEdge(int newHeadIndex, int dependentIndex) throws MaltChainedException {
DependencyNode newHead = null;
DependencyNode dependent = null;
if (newHeadIndex == 0) {
newHead = root;
} else if (newHeadIndex > 0) {
newHead = terminalNodes.get(newHeadIndex);
}
if (dependentIndex > 0) {
dependent = terminalNodes.get(dependentIndex);
}
return moveDependencyEdge(newHead, dependent);
}
protected Edge moveDependencyEdge(DependencyNode newHead, DependencyNode dependent) throws MaltChainedException {
if (dependent == null || !dependent.hasHead()) {
return null;
}
Edge headEdge = dependent.getHeadEdge();
final LabelSet labels = checkOutNewLabelSet();
for (SymbolTable table : headEdge.getLabelTypes()) {
labels.put(table, headEdge.getLabelCode(table));
}
headEdge.clear();
headEdge.setBelongsToGraph(this);
headEdge.setEdge((Node)newHead, (Node)dependent, Edge.DEPENDENCY_EDGE);
headEdge.addLabel(labels);
labels.clear();
checkInLabelSet(labels);
return headEdge;
}
public void removeDependencyEdge(int headIndex, int dependentIndex) throws MaltChainedException {
Node head = null;
Node dependent = null;
if (headIndex == 0) {
head = root;
} else if (headIndex > 0) {
head = terminalNodes.get(headIndex);
}
if (dependentIndex > 0) {
dependent = terminalNodes.get(dependentIndex);
}
removeDependencyEdge(head, dependent);
}
protected void removeDependencyEdge(Node head, Node dependent) throws MaltChainedException {
if (head == null || dependent == null) {
throw new SyntaxGraphException("Head or dependent node is missing.");
} else if (!dependent.isRoot()) {
Iterator<Edge> ie = dependent.getIncomingEdgeIterator();
while (ie.hasNext()) {
Edge e = ie.next();
if (e.getSource() == head) {
graphEdges.remove(e);
ie.remove();
edgePool.checkIn(e);
}
}
} else {
throw new SyntaxGraphException("Head node is not a root node or a terminal node.");
}
}
public Edge addSecondaryEdge(ComparableNode source, ComparableNode target) throws MaltChainedException {
if (source == null || target == null) {
throw new SyntaxGraphException("Head or dependent node is missing.");
} else if (!target.isRoot()) {
Edge e = edgePool.checkOut();
e.setBelongsToGraph(this);
e.setEdge((Node)source, (Node)target, Edge.SECONDARY_EDGE);
graphEdges.add(e);
return e;
}
return null;
}
public void removeSecondaryEdge(ComparableNode source, ComparableNode target) throws MaltChainedException {
if (source == null || target == null) {
throw new SyntaxGraphException("Head or dependent node is missing.");
} else if (!target.isRoot()) {
final Iterator<Edge> ie = ((Node)target).getIncomingEdgeIterator();
while (ie.hasNext()) {
Edge e = ie.next();
if (e.getSource() == source) {
ie.remove();
graphEdges.remove(e);
edgePool.checkIn(e);
}
}
}
}
// public boolean hasLabeledDependency(int index, SymbolTable table) {
// return (!getDependencyNode(index).isRoot() && getDependencyNode(index).getLabelCode(table) != null);
// }
public boolean hasLabeledDependency(int index) throws MaltChainedException {
return (getDependencyNode(index).hasHead() && getDependencyNode(index).getHeadEdge().isLabeled());
}
public boolean isConnected() {
return (numberOfComponents == 1);
}
public boolean isProjective() throws MaltChainedException {
for (int i : terminalNodes.keySet()) {
if (!terminalNodes.get(i).isProjective()) {
return false;
}
}
return true;
}
public boolean isTree() {
return isConnected() && isSingleHeaded();
}
public boolean isSingleHeaded() {
for (int i : terminalNodes.keySet()) {
if (!terminalNodes.get(i).hasAtMostOneHead()) {
return false;
}
}
return true;
}
public boolean isSingleHeadedConstraint() {
return singleHeadedConstraint;
}
public void setSingleHeadedConstraint(boolean singleHeadedConstraint) {
this.singleHeadedConstraint = singleHeadedConstraint;
}
public int nNonProjectiveEdges() throws MaltChainedException {
int c = 0;
for (int i : terminalNodes.keySet()) {
if (!terminalNodes.get(i).isProjective()) {
c++;
}
}
return c;
}
public int nEdges() {
return graphEdges.size();
}
public SortedSet<Edge> getEdges() {
return graphEdges;
}
public SortedSet<Integer> getDependencyIndices() {
SortedSet<Integer> indices = new TreeSet<Integer>(terminalNodes.keySet());
indices.add(0);
return indices;
}
protected DependencyNode link(DependencyNode x, DependencyNode y) {
if (x.getRank() > y.getRank()) {
y.setComponent(x);
} else {
x.setComponent(y);
if (x.getRank() == y.getRank()) {
y.setRank(y.getRank()+1);
}
return y;
}
return x;
}
public void linkAllTreesToRoot() throws MaltChainedException {
for (int i : terminalNodes.keySet()) {
if (!terminalNodes.get(i).hasHead()) {
addDependencyEdge(root,terminalNodes.get(i));
}
}
}
public LabelSet getDefaultRootEdgeLabels() throws MaltChainedException {
if (rootLabels == null) {
return null;
}
return rootLabels.getDefaultRootLabels();
}
public String getDefaultRootEdgeLabelSymbol(SymbolTable table) throws MaltChainedException {
if (rootLabels == null) {
return null;
}
return rootLabels.getDefaultRootLabelSymbol(table);
}
public int getDefaultRootEdgeLabelCode(SymbolTable table) throws MaltChainedException {
if (rootLabels == null) {
return -1;
}
return rootLabels.getDefaultRootLabelCode(table);
}
public void setDefaultRootEdgeLabel(SymbolTable table, String defaultRootSymbol) throws MaltChainedException {
if (rootLabels == null) {
rootLabels = new RootLabels();
}
rootLabels.setDefaultRootLabel(table, defaultRootSymbol);
}
public void setDefaultRootEdgeLabels(String rootLabelOption, SortedMap<String, SymbolTable> edgeSymbolTables) throws MaltChainedException {
if (rootLabels == null) {
rootLabels = new RootLabels();
}
rootLabels.setRootLabels(rootLabelOption, edgeSymbolTables);
}
public void clear() throws MaltChainedException {
edgePool.checkInAll();
graphEdges.clear();
root.clear();
super.clear();
numberOfComponents++;
}
public DependencyNode getDependencyRoot() {
return root;
}
public String toString() {
final StringBuilder sb = new StringBuilder();
for (int index : terminalNodes.keySet()) {
sb.append(terminalNodes.get(index).toString().trim());
sb.append('\n');
}
sb.append('\n');
return sb.toString();
}
}