Package de.saar.chorus.domgraph.chart

Class ChartSolver<E extends GraphBasedNonterminal>

java.lang.Object

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

public class ChartSolver<E extends GraphBasedNonterminal>
extends Object

A solver for compact weakly normal dominance graphs. This solver computes a Chart as described in Koller & Thater (2005), "The evolution of dominance constraint solvers", ACL-05 Workshop on Software. It can be seen as an implementation of the Bodirsky et al. 2005 graph solver.

The solver successively computes the splits corresponding to the free fragments of the subgraphs of the dominance graph, and adds them to the chart. It assumes that the input dominance graph has only dominance edges into roots or from roots to holes; this can be achieved e.g. by calling the DomGraph.preprocess() method first.

The solver relies on an object of a subclass of SplitSource to provide the splits of a subgraph. By default, it uses an object of the class CompleteSplitSource, which computes all splits of this subgraph. Alternatively, you can provide a split source which only adds a certain subset of all splits to the chart.

Notice that the role of this class is only to fill the chart. The actual solved forms can later be extracted from the chart using a SolvedFormIterator object.

Author:

Alexander Koller

Method Summary

Modifier and Type	Method	Description
static boolean	solve(DomGraph graph, ConcreteRegularTreeGrammar<SubgraphNonterminal> chart)	Solves the given dominance graph using a CompleteSplitSource.
static <E extends GraphBasedNonterminal> boolean	solve(DomGraph graph, ConcreteRegularTreeGrammar<E> chart, SplitSource<E> splitsource)	Solves the given dominance graph using a specific split source.

Methods inherited from class java.lang.Object

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

Method Details

solve

public static <E extends GraphBasedNonterminal>
boolean solve(DomGraph graph,
 ConcreteRegularTreeGrammar<E> chart,
 SplitSource<E> splitsource)
       throws SolverNotApplicableException

Solves the given dominance graph using a specific split source. This method will determine whether the given dominance graph is solvable or not. It will also fill the given chart with the splits that are necessary to later enumerate solved forms of the dominance graph. It will use the given split source in order to compute the splits for each subgraph.

The solver throws an SolverNotApplicableException if the dominance graph doesn't belong to a fragment that the solver understands. Currently the only restriction is that the graph must not contain empty fragments. However, the solver makes certain assumptions about the form of the dominance edges that can be achieved by calling DomGraph.preprocess() on it first.

Parameters:

graph - an arbitrary dominance graph

chart - a chart which will be filled with the splits of this graph

splitsource - a split source

Returns:

true if the graph is solvable, false otherwise

Throws:

SolverNotApplicableException

solve

public static boolean solve(DomGraph graph,
 ConcreteRegularTreeGrammar<SubgraphNonterminal> chart)
                     throws SolverNotApplicableException

Solves the given dominance graph using a CompleteSplitSource. This method will create a new CompleteSplitSource object for the graph and then call #solve(DomGraph, Chart, SplitSource).

Throws:

SolverNotApplicableException

See Also:

• #solve(DomGraph, Chart, SplitSource)