edu.stanford.nlp.fsm

Class TransducerGraph

java.lang.Object

edu.stanford.nlp.fsm.TransducerGraph

All Implemented Interfaces:

java.lang.Cloneable

public class TransducerGraph
extends java.lang.Object
implements java.lang.Cloneable

TransducerGraph represents a deterministic finite state automaton without epsilon transitions.

Version:

11/02/03

Author:

Teg Grenager

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	TransducerGraph.Arc<NODE,IN,OUT> An arc in a finite state transducer.
static interface	TransducerGraph.ArcProcessor
static interface	TransducerGraph.GraphProcessor
static class	TransducerGraph.InputSplittingProcessor
static interface	TransducerGraph.NodeProcessor
static class	TransducerGraph.NodeProcessorWrappingArcProcessor
static class	TransducerGraph.NormalizingGraphProcessor
static class	TransducerGraph.ObjectToSetNodeProcessor
static class	TransducerGraph.OutputCombiningProcessor
static class	TransducerGraph.SetToStringNodeProcessor

Field Summary

Fields

Modifier and Type	Field and Description
static java.lang.String	EPSILON_INPUT

Constructor Summary

Constructors

Constructor and Description
TransducerGraph()
TransducerGraph(java.util.Set<TransducerGraph.Arc> newArcs) Uses the Arcs newArcs.
TransducerGraph(java.util.Set<TransducerGraph.Arc> newArcs, java.lang.Object startNode, java.util.Set endNodes, TransducerGraph.ArcProcessor arcProcessor, TransducerGraph.NodeProcessor nodeProcessor)
TransducerGraph(TransducerGraph other)
TransducerGraph(TransducerGraph other, TransducerGraph.ArcProcessor arcProcessor)
TransducerGraph(TransducerGraph other, TransducerGraph.NodeProcessor nodeProcessor)

Method Summary

Modifier and Type	Method and Description
boolean	addArc(java.lang.Object source, java.lang.Object target, java.lang.Object input, java.lang.Object output)
protected boolean	addArc(TransducerGraph.Arc a)
static void	addOnePathToGraph(java.util.List path, double count, int markovOrder, TransducerGraph graph)
java.lang.String	asDOTString()
boolean	canAddArc(java.lang.Object source, java.lang.Object target, java.lang.Object input, java.lang.Object output)
TransducerGraph	clone()
static <T> TransducerGraph	createGraphFromPaths(ClassicCounter<java.util.List<T>> pathCounter, int markovOrder)
static TransducerGraph	createGraphFromPaths(java.util.List paths, int markovOrder) If markovOrder is zero, we always transition back to the start state If markovOrder is negative, we assume that it is infinite
static TransducerGraph	createRandomGraph(int numPaths, int pathLengthMean, double pathLengthVariance, int numInputs, java.util.List<java.util.List<java.lang.String>> pathList) For testing only.
static java.util.List	createRandomPaths(int numPaths, int pathLengthMean, double pathLengthVariance, int numInputs)
void	depthFirstSearch(boolean forward, java.lang.StringBuilder b)
TransducerGraph.Arc	getArc(java.lang.Object source, java.lang.Object target) Slow implementation.
TransducerGraph.Arc	getArcBySourceAndInput(java.lang.Object node, java.lang.Object input) Can only be one because automaton is deterministic.
java.util.Set<TransducerGraph.Arc>	getArcs()
java.util.Set<TransducerGraph.Arc>	getArcsByInput(java.lang.Object node) Returns a Set of type TransducerGraph.Arc.
java.util.Set<TransducerGraph.Arc>	getArcsBySource(java.lang.Object node) Returns a Set of type TransducerGraph.Arc.
java.util.Set<TransducerGraph.Arc>	getArcsByTarget(java.lang.Object node) Returns a Set of type TransducerGraph.Arc.
java.util.Set<TransducerGraph.Arc>	getArcsByTargetAndInput(java.lang.Object node, java.lang.Object input) Returns a Set of type TransducerGraph.Arc.
java.util.Set	getEndNodes()
java.util.Set	getInputs()
java.util.Set	getNodes() Just does union of keysets of maps.
double	getOutputOfPathInGraph(java.util.List path) For testing only.
java.util.List<java.lang.Double>	getPathOutputs(java.util.List<java.util.List<java.lang.String>> pathList) For testing only.
java.lang.Object	getStartNode()
double	inFlow(java.lang.Object node)
static void	main(java.lang.String[] args) For testing only.
double	outFlow(java.lang.Object node)
boolean	removeArc(TransducerGraph.Arc a)
java.util.List	sampleUniformPathFromGraph() for testing only.
void	setDeterminism(boolean checkDeterminism)
void	setEndNode(java.lang.Object o)
void	setStartNode(java.lang.Object o)
static boolean	testGraphPaths(TransducerGraph sourceGraph, TransducerGraph testGraph, int numPaths)
java.lang.String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

EPSILON_INPUT

public static final java.lang.String EPSILON_INPUT

See Also:

Constant Field Values

Constructor Detail

TransducerGraph

public TransducerGraph()

TransducerGraph

public TransducerGraph(TransducerGraph other)

TransducerGraph

public TransducerGraph(TransducerGraph other,
                       TransducerGraph.ArcProcessor arcProcessor)

TransducerGraph

public TransducerGraph(TransducerGraph other,
                       TransducerGraph.NodeProcessor nodeProcessor)

TransducerGraph

public TransducerGraph(java.util.Set<TransducerGraph.Arc> newArcs,
                       java.lang.Object startNode,
                       java.util.Set endNodes,
                       TransducerGraph.ArcProcessor arcProcessor,
                       TransducerGraph.NodeProcessor nodeProcessor)

TransducerGraph

public TransducerGraph(java.util.Set<TransducerGraph.Arc> newArcs)

Uses the Arcs newArcs.

Method Detail

setDeterminism

public void setDeterminism(boolean checkDeterminism)

clone

public TransducerGraph clone()
                      throws java.lang.CloneNotSupportedException

Overrides:

clone in class java.lang.Object

Throws:

java.lang.CloneNotSupportedException

getArcs

public java.util.Set<TransducerGraph.Arc> getArcs()

getNodes

public java.util.Set getNodes()

Just does union of keysets of maps.

getInputs

public java.util.Set getInputs()

setStartNode

public void setStartNode(java.lang.Object o)

setEndNode

public void setEndNode(java.lang.Object o)

getStartNode

public java.lang.Object getStartNode()

getEndNodes

public java.util.Set getEndNodes()

getArcsByInput

public java.util.Set<TransducerGraph.Arc> getArcsByInput(java.lang.Object node)

Returns a Set of type TransducerGraph.Arc.

getArcsBySource

public java.util.Set<TransducerGraph.Arc> getArcsBySource(java.lang.Object node)

Returns a Set of type TransducerGraph.Arc.

getArcsByTarget

public java.util.Set<TransducerGraph.Arc> getArcsByTarget(java.lang.Object node)

Returns a Set of type TransducerGraph.Arc.

getArcBySourceAndInput

public TransducerGraph.Arc getArcBySourceAndInput(java.lang.Object node,
                                                  java.lang.Object input)

Can only be one because automaton is deterministic.

getArcsByTargetAndInput

public java.util.Set<TransducerGraph.Arc> getArcsByTargetAndInput(java.lang.Object node,
                                                                  java.lang.Object input)

Returns a Set of type TransducerGraph.Arc.

getArc

public TransducerGraph.Arc getArc(java.lang.Object source,
                                  java.lang.Object target)

Slow implementation.

addArc

public boolean addArc(java.lang.Object source,
                      java.lang.Object target,
                      java.lang.Object input,
                      java.lang.Object output)

Returns:

true if and only if it created a new Arc and added it to the graph.

addArc

protected boolean addArc(TransducerGraph.Arc a)

Returns:

true if and only if it added Arc a to the graph. determinism.

removeArc

public boolean removeArc(TransducerGraph.Arc a)

canAddArc

public boolean canAddArc(java.lang.Object source,
                         java.lang.Object target,
                         java.lang.Object input,
                         java.lang.Object output)

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

asDOTString

public java.lang.String asDOTString()

inFlow

public double inFlow(java.lang.Object node)

outFlow

public double outFlow(java.lang.Object node)

getOutputOfPathInGraph

public double getOutputOfPathInGraph(java.util.List path)

For testing only. Doubles combined by addition.

sampleUniformPathFromGraph

public java.util.List sampleUniformPathFromGraph()

for testing only. doubles combined by addition.

getPathOutputs

public java.util.List<java.lang.Double> getPathOutputs(java.util.List<java.util.List<java.lang.String>> pathList)

For testing only.

testGraphPaths

public static boolean testGraphPaths(TransducerGraph sourceGraph,
                                     TransducerGraph testGraph,
                                     int numPaths)

createGraphFromPaths

public static TransducerGraph createGraphFromPaths(java.util.List paths,
                                                   int markovOrder)

If markovOrder is zero, we always transition back to the start state If markovOrder is negative, we assume that it is infinite

createGraphFromPaths

public static <T> TransducerGraph createGraphFromPaths(ClassicCounter<java.util.List<T>> pathCounter,
                                                       int markovOrder)

addOnePathToGraph

public static void addOnePathToGraph(java.util.List path,
                                     double count,
                                     int markovOrder,
                                     TransducerGraph graph)

createRandomGraph

public static TransducerGraph createRandomGraph(int numPaths,
                                                int pathLengthMean,
                                                double pathLengthVariance,
                                                int numInputs,
                                                java.util.List<java.util.List<java.lang.String>> pathList)

For testing only. All paths will be added to pathList as Lists. // generate a bunch of paths through the graph with the input alphabet // and create new nodes for each one.

createRandomPaths

public static java.util.List createRandomPaths(int numPaths,
                                               int pathLengthMean,
                                               double pathLengthVariance,
                                               int numInputs)

depthFirstSearch

public void depthFirstSearch(boolean forward,
                             java.lang.StringBuilder b)

main

public static void main(java.lang.String[] args)

For testing only.