Package de.saar.chorus.domgraph.chart

Class SplitComputer<E extends GraphBasedNonterminal>

java.lang.Object

de.saar.chorus.domgraph.chart.SplitComputer<E>

Direct Known Subclasses:

SubgraphSplitComputer

public abstract class SplitComputer<E extends GraphBasedNonterminal>
extends Object

A utility class for computing the split of a free root.

Author:

Alexander Koller

Field Summary

Fields

Modifier and Type	Field	Description
protected String	theRoot

Constructor Summary

Constructors

Constructor	Description
SplitComputer(DomGraph graph)

Method Summary

Modifier and Type	Method	Description
Split<E>	computeSplit(String root, E subgraph)	Compute the split induced by the free root of a subgraph.
protected abstract E	createEmptyNonterminal()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

theRoot

protected String theRoot

Constructor Details

SplitComputer

public SplitComputer(DomGraph graph)

Method Details

computeSplit

public Split<E> computeSplit(String root,
 E subgraph)

Compute the split induced by the free root of a subgraph. The method assumes that the given root is a node without incoming edges. It does _not_ assume that the root is actually free, but if it isn't, the method will return null.

The runtime of this method is O(m+n) for a subgraph with m edges and n nodes (it performs a single DFS through the graph).

Parameters:

root - a node without incoming edges

subgraph - a subgraph

Returns:

the split induced by this root, or null if the root is not the root of a free fragment

createEmptyNonterminal

protected abstract E createEmptyNonterminal()