de.up.ling.irtg.algebra.graph

Class GraphAlgebra

java.lang.Object

de.up.ling.irtg.algebra.Algebra<E>

de.up.ling.irtg.algebra.EvaluatingAlgebra<SGraph>

de.up.ling.irtg.algebra.graph.GraphAlgebra

All Implemented Interfaces:

Serializable

public class GraphAlgebra
extends EvaluatingAlgebra<SGraph>

The algebra of s-graphs. The values of this algebra are s-graphs, i.e. objects of class SGraph (which see). The algebra interprets the following operations (where G, G1, G2 are s-graphs, and a, b are source names):

• The operation merge(G1,G2), merges the two graphs using SGraph.merge(de.up.ling.irtg.algebra.graph.SGraph).
• The forget operation f_a(G) forgets the a-source of G. The resulting s-graph is like G, except that it does not have an a-source. The operation f_a_b forgets both a and b.
• The rename operation r_a_b(G) renames the a-source of G into b, using SGraph.renameSource(java.lang.String, java.lang.String). The operation r_a is an abbreviation for r_root_a.
• The swap operation s_a_b(G) renames the a-source of G into b and the b-source into a.
• The combined merge and rename operation merge_a_b(G1,G2), first applies the rename from a to b in G2 and then merges the result with G1.

Any other string is interpreted as a constant which denotes an s-graph. The strings are parsed using parseString(java.lang.String), i.e. they are expected to be in the extended ISI AMR format syntax.

Author:

koller

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field and Description
static String	OP_COMBINEDMERGE
static String	OP_FORGET
static String	OP_MERGE
static String	OP_RENAME
static String	OP_SWAP

Constructor Summary

Constructors

Constructor and Description
GraphAlgebra() Creates an empty graph algebra.
GraphAlgebra(Signature signature) Creates a graph algebra with the given signature.

Method Summary

Modifier and Type	Method and Description
TreeAutomaton	decompose(SGraph value) Returns a bottom-up or a top-down decomposition automaton for the s-graph value (which one can be set via setUseTopDownAutomaton, default is bottom-up).
TreeAutomaton	decompose(SGraph value, Class c) Given an SGraph, this returns the corresponding decomposition automaton of class c.
TreeAutomaton	decomposeTopDown(SGraph value)
SGraph	evaluate(String label, List<SGraph> childrenValues) Applies the operation with name "label" to the given arguments, and returns the result.
static GraphAlgebra	makeCompleteDecompositionAlgebra(SGraph graph, int nrSources) Creates a GraphAlgebra based on graph with nrSources many sources (named 1,..,nrSources).
static GraphAlgebra	makeIncompleteDecompositionAlgebra(SGraph graph, int nrSources) Creates a GraphAlgebra based on graph with nrSources many sources (named 1,..,nrSources).
SGraph	parseString(String representation) Parses a string into an s-graph, using IsiAmrParser.parse(java.io.Reader).
void	setUseTopDownAutomaton(boolean useTopDownAutomaton) Sets whether this algebra uses top-down or bottom-up decomposition automata.
static double	smatch(Object[] graphs, Object[] gold) Computes the smatch score of the two given arrays of graphs.
static double	smatch(SGraph graph, SGraph gold) Computes the smatch score of the two given graphs.
boolean	usesTopDownAutomaton() Describes whether this algebra uses top-down or bottom-up decomposition automata.
JComponent	visualize(SGraph graph) Returns a Swing component that visualizes an object of this algebra.
static void	writeIncompleteDecompositionIRTG(GraphAlgebra alg, SGraph graph, int nrSources, PrintWriter writer) Writes an IRTG grammar file based on graph with nrSources many sources (named 1,..,nrSources).
boolean	writeRestrictedAutomaton(SGraph value, Writer writer) Writes (nearly) all the rules in the decomposition automaton of the SGraph value (with respect to the signature in this algebra) into the Writer, and does not store the rules in memory.
static boolean	writeRestrictedDecompositionAutomaton(SGraph value, int sourceCount, Writer writer) Writes (nearly) all the rules in the decomposition automaton of the SGraph value (with respect to the incomplete decomposition algebra) into the Writer, and does not store the rules in memory.

Methods inherited from class de.up.ling.irtg.algebra.EvaluatingAlgebra

evaluate, getSignature

Methods inherited from class de.up.ling.irtg.algebra.Algebra

getAllAlgebraClasses, getClassOfValues, hasOptions, readOptions, representAsString, setOptions, writeOptions

Methods inherited from class java.lang.Object

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

Field Detail

OP_MERGE

public static final String OP_MERGE

See Also:

Constant Field Values

OP_COMBINEDMERGE

public static final String OP_COMBINEDMERGE

See Also:

Constant Field Values

OP_RENAME

public static final String OP_RENAME

See Also:

Constant Field Values

OP_SWAP

public static final String OP_SWAP

See Also:

Constant Field Values

OP_FORGET

public static final String OP_FORGET

See Also:

Constant Field Values

Constructor Detail

GraphAlgebra

public GraphAlgebra()

Creates an empty graph algebra.

GraphAlgebra

public GraphAlgebra(Signature signature)

Creates a graph algebra with the given signature.

Parameters:

signature -

Method Detail

usesTopDownAutomaton

public boolean usesTopDownAutomaton()

Describes whether this algebra uses top-down or bottom-up decomposition automata.

Returns:

setUseTopDownAutomaton

public void setUseTopDownAutomaton(boolean useTopDownAutomaton)

Sets whether this algebra uses top-down or bottom-up decomposition automata.

Parameters:

useTopDownAutomaton -

decompose

public TreeAutomaton decompose(SGraph value)

Returns a bottom-up or a top-down decomposition automaton for the s-graph value (which one can be set via setUseTopDownAutomaton, default is bottom-up).

Overrides:

decompose in class EvaluatingAlgebra<SGraph>

Parameters:

value -

Returns:

decompose

public TreeAutomaton decompose(SGraph value,
                               Class c)

Given an SGraph, this returns the corresponding decomposition automaton of class c.

Parameters:

value -

c -

Returns:

decomposeTopDown

public TreeAutomaton decomposeTopDown(SGraph value)

writeRestrictedAutomaton

public boolean writeRestrictedAutomaton(SGraph value,
                                        Writer writer)
                                 throws Exception

Writes (nearly) all the rules in the decomposition automaton of the SGraph value (with respect to the signature in this algebra) into the Writer, and does not store the rules in memory. Iterates through the rules in bottom up order. To avoid cycles, there are no rename operations on states only reachable via rename. Rules of the form c-> m(a, b) and c-> m(b,a) are both written into the writer.

Parameters:

value -

writer -

Returns:

Throws:

Exception

writeRestrictedDecompositionAutomaton

public static boolean writeRestrictedDecompositionAutomaton(SGraph value,
                                                            int sourceCount,
                                                            Writer writer)
                                                     throws Exception

Writes (nearly) all the rules in the decomposition automaton of the SGraph value (with respect to the incomplete decomposition algebra) into the Writer, and does not store the rules in memory. Iterates through the rules in bottom up order. To avoid cycles, there are no rename operations on states only reachable via rename. Rules of the form c-> m(a, b) and c-> m(b,a) are both written into the writer.

Parameters:

value -

sourceCount -

writer -

Returns:

Throws:

Exception

evaluate

public SGraph evaluate(String label,
                       List<SGraph> childrenValues)

Description copied from class: EvaluatingAlgebra

Applies the operation with name "label" to the given arguments, and returns the result.

Returns:

parseString

public SGraph parseString(String representation)
                   throws ParserException

Parses a string into an s-graph, using IsiAmrParser.parse(java.io.Reader).

Specified by:

parseString in class EvaluatingAlgebra<SGraph>

Parameters:

representation -

Returns:

Throws:

ParserException

visualize

public JComponent visualize(SGraph graph)

Returns a Swing component that visualizes an object of this algebra. The graph is visualized using the JGraph graph drawing library.

Overrides:

visualize in class Algebra<SGraph>

Parameters:

graph -

Returns:

See Also:

TikzSgraphOutputCodec

smatch

public static double smatch(SGraph graph,
                            SGraph gold)
                     throws IOException

Computes the smatch score of the two given graphs. Uses the python implementation from ISI (), the python file must be in the current working directory.

Parameters:

graph -

gold -

Returns:

Throws:

IOException

smatch

public static double smatch(Object[] graphs,
                            Object[] gold)
                     throws IOException

Computes the smatch score of the two given arrays of graphs. Uses the python implementation from ISI (), the python file must be in the current working directory.

Parameters:

graphs -

gold -

Returns:

Throws:

IOException

makeCompleteDecompositionAlgebra

public static GraphAlgebra makeCompleteDecompositionAlgebra(SGraph graph,
                                                            int nrSources)
                                                     throws Exception

Creates a GraphAlgebra based on graph with nrSources many sources (named 1,..,nrSources). The resulting algebra contains as constants all atomic subgraphs (single edges, and single labled nodes), with all possible source combinations. Further, the merge operation and all possible versions of forget and rename. It is encouraged to use makeIncompleteDecompositionAlgebra instead, since its result is equally expressive and smaller (due to less spurious constants).

Parameters:

graph -

nrSources -

Returns:

Throws:

Exception

makeIncompleteDecompositionAlgebra

public static GraphAlgebra makeIncompleteDecompositionAlgebra(SGraph graph,
                                                              int nrSources)
                                                       throws Exception

Creates a GraphAlgebra based on graph with nrSources many sources (named 1,..,nrSources). The resulting algebra contains as constants all atomic subgraphs (single edges, and single labled nodes), but only one source is used for nodes, and one more source for edges (both possibilities to name the vertices incident to the edge with these two sources are included). Further, the merge operation and all possible versions of forget and rename.

Parameters:

graph -

nrSources -

Returns:

Throws:

Exception

writeIncompleteDecompositionIRTG

public static void writeIncompleteDecompositionIRTG(GraphAlgebra alg,
                                                    SGraph graph,
                                                    int nrSources,
                                                    PrintWriter writer)
                                             throws Exception

Writes an IRTG grammar file based on graph with nrSources many sources (named 1,..,nrSources). The resulting irtg represents a GraphAlgebra which contains as constants all atomic subgraphs (single edges, and single labled nodes), but only one source is used for nodes, and one more source for edges (both possibilities to name the vertices incident to the edge with these two sources are included). Further, the merge operation and all possible versions of forget and rename. The one final state is S, the one nonfinal state is X.

Parameters:

alg - empty GraphAlgebra, carries the result.

graph -

nrSources -

Throws:

Exception