edu.stanford.nlp.fsm
Class TransducerGraph

java.lang.Object
  edu.stanford.nlp.fsm.TransducerGraph

All Implemented Interfaces:

Cloneable

public class TransducerGraph
extends Object
implements Cloneable

TransducerGraph

Class for representing a deterministic finite state automaton without epsilon transitions.

Author:

Teg Grenager

Nested Class Summary

static class	TransducerGraph.Arc
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

static Object

EPSILON_INPUT

Constructor Summary

TransducerGraph()

TransducerGraph(Set newArcs)
Uses the Arcs newArcs.

TransducerGraph(Set newArcs, Object startNode, 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

boolean	addArc(Object source, Object target, Object input, Object output)
protected boolean	addArc(TransducerGraph.Arc a)
static void	addOnePathToGraph(List path, double count, int markovOrder, TransducerGraph graph)
String	asDOTString()
boolean	canAddArc(Object source, Object target, Object input, Object output)
boolean	canAddPath(List path) For testing only.
Object	clone()
static TransducerGraph	createGraphFromPaths(Counter pathCounter, int markovOrder)
static TransducerGraph	createGraphFromPaths(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, List pathList) For testing only.
static List	createRandomPaths(int numPaths, int pathLengthMean, double pathLengthVariance, int numInputs)
void	depthFirstSearch(boolean forward, StringBuffer b)
protected Set	ensure(Object o)
TransducerGraph.Arc	getArc(Object source, Object target) Slow implementation.
TransducerGraph.Arc	getArcBySourceAndInput(Object node, Object input) Can only be one because automaton is deterministic.
Set	getArcs()
Set	getArcsByInput(Object node) Returns a Set of type TransducerGraph.Arc.
Set	getArcsBySource(Object node) Returns a Set of type TransducerGraph.Arc.
Set	getArcsByTarget(Object node) Returns a Set of type TransducerGraph.Arc.
Set	getArcsByTargetAndInput(Object node, Object input) Returns a Set of type TransducerGraph.Arc.
Set	getEndNodes()
Set	getInputs()
Set	getNodes() Just does union of keysets of maps.
double	getOutputOfPathInGraph(List path) For testing only.
List	getPathOutputs(List pathList) For testing only.
double	getSourceTotal(Object node)
Object	getStartNode()
double	inFlow(Object node)
static void	main(String[] args) For testing only.
double	outFlow(Object node)
static void	printPathOutputs(List pathList, TransducerGraph graph, boolean printPaths) For testing only.
boolean	removeArc(TransducerGraph.Arc a)
Map	samplePathsFromGraph(int numPaths)
List	sampleUniformPathFromGraph() for testing only.
void	setDeterminism(boolean checkDeterminism)
void	setDotWeightingInverted(boolean inverted)
void	setEndNode(Object o)
void	setStartNode(Object o)
static boolean	testGraphPaths(TransducerGraph sourceGraph, TransducerGraph testGraph, int numPaths)
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 Object EPSILON_INPUT

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(Set newArcs,
                       Object startNode,
                       Set endNodes,
                       TransducerGraph.ArcProcessor arcProcessor,
                       TransducerGraph.NodeProcessor nodeProcessor)

TransducerGraph

public TransducerGraph(Set newArcs)

Uses the Arcs newArcs.

Method Detail

setDeterminism

public void setDeterminism(boolean checkDeterminism)

clone

public Object clone()

Overrides:

clone in class Object

getArcs

public Set getArcs()

getNodes

public Set getNodes()

Just does union of keysets of maps.

getInputs

public Set getInputs()

setStartNode

public void setStartNode(Object o)

setEndNode

public void setEndNode(Object o)

getStartNode

public Object getStartNode()

getEndNodes

public Set getEndNodes()

getArcsByInput

public Set getArcsByInput(Object node)

Returns a Set of type TransducerGraph.Arc.

getArcsBySource

public Set getArcsBySource(Object node)

Returns a Set of type TransducerGraph.Arc.

ensure

protected Set ensure(Object o)

getArcsByTarget

public Set getArcsByTarget(Object node)

Returns a Set of type TransducerGraph.Arc.

getArcBySourceAndInput

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

Can only be one because automaton is deterministic.

getArcsByTargetAndInput

public Set getArcsByTargetAndInput(Object node,
                                   Object input)

Returns a Set of type TransducerGraph.Arc.

getArc

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

Slow implementation.

addArc

public boolean addArc(Object source,
                      Object target,
                      Object input,
                      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(Object source,
                         Object target,
                         Object input,
                         Object output)

toString

public String toString()

Overrides:

toString in class Object

setDotWeightingInverted

public void setDotWeightingInverted(boolean inverted)

asDOTString

public String asDOTString()

inFlow

public double inFlow(Object node)

outFlow

public double outFlow(Object node)

getSourceTotal

public double getSourceTotal(Object node)

getOutputOfPathInGraph

public double getOutputOfPathInGraph(List path)

For testing only. Doubles combined by addition.

sampleUniformPathFromGraph

public List sampleUniformPathFromGraph()

for testing only. doubles combined by addition.

samplePathsFromGraph

public Map samplePathsFromGraph(int numPaths)

printPathOutputs

public static void printPathOutputs(List pathList,
                                    TransducerGraph graph,
                                    boolean printPaths)

For testing only.

getPathOutputs

public List getPathOutputs(List pathList)

For testing only.

testGraphPaths

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

canAddPath

public boolean canAddPath(List path)

For testing only. Doubles combined by multiplication.

createGraphFromPaths

public static TransducerGraph createGraphFromPaths(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 TransducerGraph createGraphFromPaths(Counter pathCounter,
                                                   int markovOrder)

addOnePathToGraph

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

createRandomGraph

public static TransducerGraph createRandomGraph(int numPaths,
                                                int pathLengthMean,
                                                double pathLengthVariance,
                                                int numInputs,
                                                List 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 List createRandomPaths(int numPaths,
                                     int pathLengthMean,
                                     double pathLengthVariance,
                                     int numInputs)

depthFirstSearch

public void depthFirstSearch(boolean forward,
                             StringBuffer b)

main

public static void main(String[] args)

For testing only.