de.up.ling.irtg.algebra.graph

Class SGraphBRDecompositionAutomatonBottomUp

java.lang.Object

de.up.ling.irtg.automata.TreeAutomaton<BoundaryRepresentation>

de.up.ling.irtg.algebra.graph.SGraphBRDecompositionAutomatonBottomUp

All Implemented Interfaces:

Intersectable<BoundaryRepresentation>, Serializable

public class SGraphBRDecompositionAutomatonBottomUp
extends TreeAutomaton<BoundaryRepresentation>

A bottom-up decomposition automaton for the s-graph algebra, using BoundaryRepresentations as states.

Author:

groschwitz

See Also:

Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from class de.up.ling.irtg.automata.TreeAutomaton

TreeAutomaton.BottomUpStateVisitor

Field Summary

Fields inherited from class de.up.ling.irtg.automata.TreeAutomaton

D, DEBUG_STORE

Constructor Summary

Constructors

Constructor and Description
SGraphBRDecompositionAutomatonBottomUp(SGraph completeGraph, GraphAlgebra algebra) Initializes a decomposition automaton for completeGraph with respect to algebra.

Method Summary

Modifier and Type	Method and Description
Iterable<Rule>	getRulesBottomUp(int labelId, int[] childStates) Finds automaton rules bottom-up for a given list of child states and a given parent label.
Iterable<Rule>	getRulesTopDown(int labelId, int parentState) Finds automaton rules top-down for a given parent state and label.
boolean	isBottomUpDeterministic() Determines whether the automaton is deterministic if read as a bottom-up automaton.
static void	main(String[] args) Writes the decomposition automata for a given corpus.
SiblingFinder	newSiblingFinder(int labelID) This returns an object that stores and finds possible partners for a given state given a rule label.
boolean	supportsBottomUpQueries()
boolean	supportsTopDownQueries()
String	toString() Computes a string representation of this automaton.
boolean	useSiblingFinder() Algorithms such as invhom check this function to decide whether their sibling finder variant should be used or not.
boolean	writeAutomatonRestricted(Writer writer) Writes all rules in this decomposition automaton, with one restriction: There are no rename operations on states only reachable via rename.
static void	writeDecompositionAutomata(String targetFolderPath, Corpus corpus, int startIndex, int stopIndex, int sourceCount, int maxNodes, int maxPerNodeCount, boolean onlyBolinas) Writes the decomposition automata for all specified graphs in the corpus, with one restriction: There are no rename operations on states only reachable via rename.

Methods inherited from class de.up.ling.irtg.automata.TreeAutomaton

accepts, acceptsRaw, analyze, asConcreteTreeAutomaton, asConcreteTreeAutomatonBottomUp, asConcreteTreeAutomatonWithStringStates, countTrees, createRule, createRule, createRule, createRule, createRule, createRule, determinize, determinize, dumpToFile, equals, evaluateInSemiring, evaluateInSemiring, evaluateInSemiringTopDown, foreachRuleBottomUpForSets, foreachRuleTopDown, foreachStateInBottomUpOrder, getAllLabels, getAllRulesTopDown, getAllStates, getFinalStates, getIdForState, getLabelsTopDown, getNumberOfRules, getNumberOfSeenStates, getRandomRuleTree, getRandomRuleTreeFromInside, getRandomTree, getRandomTreeFromInside, getReachableStates, getRulesBottomUp, getRulesBottomUp, getRuleSet, getRulesForRhsState, getRulesTopDown, getRuleTree, getSignature, getStateForId, getStateInterner, getStatesInBottomUpOrder, getStoredConstantsForID, getWeight, getWeightRaw, hasRuleWithPrefix, hasStoredConstants, homomorphism, inside, intersect, intersect, intersectBottomUp, intersectCondensed, intersectCondensed, intersectCondensed, intersectCondensedBottomUp, intersectCondensedBottomUp, intersectEarley, intersectViterbi, intersectViterbi, inverseCondensedHomomorphism, inverseHomomorphism, isCyclic, isEmpty, isStoring, language, languageIterable, languageIterator, languageIteratorRaw, languageRaw, makeAllRulesExplicit, normalizeRuleWeights, outside, processAllRulesBottomUp, processAllRulesTopDown, reduceTopDown, run, run, runRaw, setRulePrintingFilter, setSkipFail, setStoring, sortedLanguageIterator, toStringBottomUp, viterbi, viterbiRaw, write

Methods inherited from class java.lang.Object

getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

SGraphBRDecompositionAutomatonBottomUp

public SGraphBRDecompositionAutomatonBottomUp(SGraph completeGraph,
                                              GraphAlgebra algebra)

Initializes a decomposition automaton for completeGraph with respect to algebra.

Parameters:

completeGraph -

algebra -

Method Detail

getRulesBottomUp

public Iterable<Rule> getRulesBottomUp(int labelId,
                                       int[] childStates)

Description copied from class: TreeAutomaton

Finds automaton rules bottom-up for a given list of child states and a given parent label. The method returns a collection of rules that can be used to assign a state to the parent node. The parent label is a numeric symbol ID, which represents a terminal symbol according to the automaton's signature.

Specified by:

getRulesBottomUp in class TreeAutomaton<BoundaryRepresentation>

Returns:

isBottomUpDeterministic

public boolean isBottomUpDeterministic()

Description copied from class: TreeAutomaton

Determines whether the automaton is deterministic if read as a bottom-up automaton.

Specified by:

isBottomUpDeterministic in class TreeAutomaton<BoundaryRepresentation>

Returns:

supportsTopDownQueries

public boolean supportsTopDownQueries()

Overrides:

supportsTopDownQueries in class TreeAutomaton<BoundaryRepresentation>

supportsBottomUpQueries

public boolean supportsBottomUpQueries()

Overrides:

supportsBottomUpQueries in class TreeAutomaton<BoundaryRepresentation>

getRulesTopDown

public Iterable<Rule> getRulesTopDown(int labelId,
                                      int parentState)

Description copied from class: TreeAutomaton

Finds automaton rules top-down for a given parent state and label. The method returns a collection of rules that can be used to assign states to the children. The parent label is a numeric symbol ID, which represents a terminal symbol according to the automaton's signature.

Note that not every method of TreeAutomaton is safely available in your implementation of getRulesTopDown. Most notably, you can't use the default implementation of TreeAutomaton.getAllStates(), because that method makes all rules of the automaton explicit and calls TreeAutomaton.getRulesTopDown(int, int) in the process, leading to an infinite recursion.

Specified by:

getRulesTopDown in class TreeAutomaton<BoundaryRepresentation>

Returns:

newSiblingFinder

public SiblingFinder newSiblingFinder(int labelID)

Description copied from class: TreeAutomaton

This returns an object that stores and finds possible partners for a given state given a rule label. (see i.e. automata.condensed.PMFactoryRestrictive.) Default implementation returns all previously entered potential siblings, override and use automaton-specific indexing for faster parsing.

Overrides:

newSiblingFinder in class TreeAutomaton<BoundaryRepresentation>

Returns:

useSiblingFinder

public boolean useSiblingFinder()

Description copied from class: TreeAutomaton

Algorithms such as invhom check this function to decide whether their sibling finder variant should be used or not. Override this to return true, if your automaton has a non-trivial sibling finder implementation you want to use.

Overrides:

useSiblingFinder in class TreeAutomaton<BoundaryRepresentation>

Returns:

writeAutomatonRestricted

public boolean writeAutomatonRestricted(Writer writer)
                                 throws Exception

Writes all rules in this decomposition automaton, with one restriction: 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 (this is different from previous implementations).

Parameters:

writer -

Returns:

Throws:

Exception

toString

public String toString()

Description copied from class: TreeAutomaton

Computes a string representation of this automaton. This method elaborates the rules of the automaton in a top-down fashion, starting with the final states and working from parents to children. TODO *** this is no longer true!

Overrides:

toString in class TreeAutomaton<BoundaryRepresentation>

writeDecompositionAutomata

public static void writeDecompositionAutomata(String targetFolderPath,
                                              Corpus corpus,
                                              int startIndex,
                                              int stopIndex,
                                              int sourceCount,
                                              int maxNodes,
                                              int maxPerNodeCount,
                                              boolean onlyBolinas)
                                       throws Exception

Writes the decomposition automata for all specified graphs in the corpus, with one restriction: 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 (this is different from previous implementations). Output files are formatted CORPUSID_NODECOUNTnodes.rtg

Parameters:

targetFolderPath - The folder into which the automata are written.

corpus - The corpus to parse. The graph interpretation must be labeled "graph".

startIndex - At which index to start (graphs are ordered by node count)

stopIndex - At which index to stop (graphs are ordered by node count)

sourceCount - How many sources to use in decomposition.

maxNodes - A hard cap on the number of nodes allowed per graph (violating graphs are not parsed). 0 for no restriction.

maxPerNodeCount - If for a node count n this is less then the number of graphs with n nodes, then maxPerNodeCount many are chosen randomly.

onlyBolinas - Whether only graphs expressible in the Bolinas format should be examined.

Throws:

Exception

main

public static void main(String[] args)
                 throws Exception

Writes the decomposition automata for a given corpus. Calls writeDecompositionAutomata with the given arguments. Call without arguments to receive help. Takes eight arguments: 1. The path to the the corpus. It should have "graph" and "string" interpretations. 2. How many sources to use in decomposition. 3. At which index to start (inclusive, graphs are ordered by node count) 4. At which index to stop (exclusive, graphs are ordered by node count) Here indices are 0-based. 5. A hard cap on the number of nodes allowed per graph (violating graphs are not parsed). 0 for no restriction. 6. A parameter k. If for a node count n, k is less then the number of graphs with n nodes, then k are chosen randomly. 7. targetFolderPath: The folder into which the automata are written. 8. 'onlyBolinas' or 'all', depending on whether only graphs expressible in the Bolinas format should be examined.

Parameters:

args -

Throws:

Exception