A simple transition graph format that consists of states and transitions between those states. More...

#include <HfstTransitionGraph.h>

Public Types
typedef HfstStates::const_iterator	const_iterator
	A const iterator type that points a state in a graph. More...

typedef C::SymbolType	HfstSymbol
	Datatype for a symbol in a transition. More...

typedef std::pair< HfstSymbol, HfstSymbol >	HfstSymbolPair
	Datatype for a symbol pair in a transition. More...

typedef std::set< HfstSymbolPair >	HfstSymbolPairSet
	A set of symbol pairs. More...

typedef std::vector < HfstSymbolPair >	HfstSymbolPairVector
	A vector of symbol pairs. More...

typedef std::set< HfstSymbol >	HfstSymbolSet
	A set of symbol pairs. More...

typedef std::set< HfstSymbol >	HfstTransitionGraphAlphabet
	Datatype for the alphabet of a graph. More...

typedef std::vector < HfstTransition< C > >	HfstTransitions
	Datatype for the states of a transition in a graph. More...

Public Member Functions
HfstState	add_state (void)
	Add a new state to this graph and return its number. More...

HfstState	add_state (HfstState s)
	Add a state s to this graph. More...

void	add_symbol_to_alphabet (const HfstSymbol &symbol)
	Explicitly add symbol to the alphabet of the graph. More...

void	add_symbols_to_alphabet (const HfstSymbolSet &symbols)
	Same as add_symbol_to_alphabet for each symbol in symbols. More...

void	add_transition (HfstState s, const HfstTransition< C > &transition, bool add_symbols_to_alphabet=true)
	Add a transition transition to state s. More...

iterator	begin ()
	Get an iterator to the beginning of the states in the graph. More...

const_iterator	begin () const
	Get a const iterator to the beginning of states in the graph. More...

HfstTransitionGraph &	disjunct (const StringPairVector &spv, typename C::WeightType weight)
	Disjunct this graph with a one-path graph defined by string pair vector spv with weight weight. More...

iterator	end ()
	Get an iterator to the end of states (last state + 1) in the graph. More...

const_iterator	end () const
	Get a const iterator to the end of states (last state + 1) in the graph. More...

const HfstTransitionGraphAlphabet &	get_alphabet () const
	Get the set of HfstSymbols in the alphabet of the graph. More...

C::WeightType	get_final_weight (HfstState s) const

HfstState	get_max_state () const
	Get the biggest state number in use. More...

HfstTransitionGraph &	harmonize (HfstTransitionGraph &another)
	Harmonize this HfstTransitionGraph and another. More...

	HfstTransitionGraph (void)
	Create a graph with one initial state that has state number zero and is not a final state, i.e. create an empty graph. More...

	HfstTransitionGraph (const HfstTransitionGraph &graph)
	Create a deep copy of HfstTransitionGraph graph. More...

	HfstTransitionGraph (const hfst::HfstTransducer &transducer)
	Create an HfstTransitionGraph equivalent to HfstTransducer transducer. FIXME: move to a separate file. More...

HfstTransitionGraph &	insert_freely (const HfstSymbolPair &symbol_pair, typename C::WeightType weight)
	Insert freely any number of symbol_pair in the graph with weight weight. More...

HfstTransitionGraph &	insert_freely (const HfstSymbolPairSet &symbol_pairs, typename C::WeightType weight)
	Insert freely any number of any symbol in symbol_pairs in the graph with weight weight. More...

HfstTransitionGraph &	insert_freely (const HfstTransitionGraph &graph)
	Insert freely any number of graph in this graph. More...

bool	is_final_state (HfstState s) const
	Whether state s is final. FIXME: return positive infinity instead if not final. More...

int	longest_path_size ()

HfstTransitionGraph &	operator= (const HfstTransitionGraph &graph)
	The assignment operator. More...

const HfstTransitions &	operator[] (HfstState s) const
	Get the set of transitions of state s in this graph. More...

std::vector< unsigned int >	path_sizes ()

void	prune_alphabet (bool force=true)
	Remove all symbols that do not occur in transitions of the graph from its alphabet. More...

void	remove_symbol_from_alphabet (const HfstSymbol &symbol)
	Remove symbol symbol from the alphabet of the graph. More...

void	remove_transition (HfstState s, const HfstTransition< C > &transition, bool remove_symbols_from_alphabet=false)
	Remove transition transition from state s. remove_symbols_from_alphabet defines whether symbols in transition are removed from the alphabet if they are no longer used in the graph. More...

void	set_final_weight (HfstState s, const typename C::WeightType &weight)
	Set the final weight of state s in this graph to weight. More...

HfstTransitionGraph &	sort_arcs (void)
	Sort the arcs of this transducer according to input and output symbols. More...

std::vector< HfstState >	states () const
	The states of the graph. More...

HfstTransitionGraph &	substitute (const HfstSymbol &old_symbol, const HfstSymbol &new_symbol, bool input_side=true, bool output_side=true)
	Substitute old_symbol with new_symbol in all transitions. input_side and output_side define whether the substitution is made on input and output sides. More...

HfstTransitionGraph &	substitute (const HfstSymbolSubstitutions &substitutions)
	Substitute all transitions as defined in substitutions. More...

HfstTransitionGraph &	substitute (const HfstSymbolPairSubstitutions &substitutions)
	Substitute all transitions as defined in substitutions. More...

HfstTransitionGraph &	substitute (const HfstSymbolPair &sp, const HfstSymbolPairSet &sps)
	Substitute all transitions sp with a set of transitions sps. More...

HfstTransitionGraph &	substitute (const HfstSymbolPair &old_pair, const HfstSymbolPair &new_pair)
	Substitute all transitions old_pair with new_pair. More...

HfstTransitionGraph &	substitute (bool(*func)(const HfstSymbolPair &sp, HfstSymbolPairSet &sps))
	Substitute all transitions with a set of transitions as defined by function func. More...

HfstTransitionGraph &	substitute (const HfstSymbolPair &sp, const HfstTransitionGraph &graph)
	Substitute all transitions old_symbol : new_symbol with a copy of graph. More...

const HfstTransitions &	transitions (HfstState s) const
	Alternative name for operator[]. More...

void	write_in_att_format (std::ostream &os, bool write_weights=true)
	Write the graph in AT&T format to ostream os. write_weights defines whether weights are printed. More...

void	write_in_att_format (FILE *file, bool write_weights=true)
	Write the graph in AT&T format to FILE file. write_weights defines whether weights are printed. More...

void	write_in_att_format_number (FILE *file, bool write_weights=true)
	Write the graph in AT&T format to FILE file using numbers instead of symbol names. write_weights defines whether weights are printed. More...

void	write_in_prolog_format (FILE *file, const std::string &name, bool write_weights=true)
	Write the graph in prolog format to FILE file. write_weights defines whether weights are printed (todo). More...

void	write_in_prolog_format (std::ostream &os, const std::string &name, bool write_weights=true)
	Write the graph in prolog format to ostream os. write_weights defines whether weights are printed (todo). More...

void	write_in_xfst_format (std::ostream &os, bool write_weights=true)
	Write the graph in xfst text format to ostream os. write_weights defines whether weights are printed (todo). More...

void	write_in_xfst_format (FILE *file, bool write_weights=true)
	Write the graph in xfst text format to FILE file. write_weights defines whether weights are printed (todo). More...

Static Public Member Functions
static HfstTransitionGraph	read_in_att_format (std::istream &is, std::string epsilon_symbol, unsigned int &linecount)
	Create an HfstTransitionGraph as defined in AT&T transducer format in istream is. epsilon_symbol defines how epsilon is represented. More...

static HfstTransitionGraph	read_in_att_format (FILE *file, std::string epsilon_symbol, unsigned int &linecount)
	Create an HfstTransitionGraph as defined in AT&T transducer format in FILE file. epsilon_symbol defines how epsilon is represented. More...

Public Attributes
std::string	name
	The name of the graph. More...

Detailed Description

template<class C>
class hfst::implementations::HfstTransitionGraph< C >

A simple transition graph format that consists of states and transitions between those states.

Probably the easiest way to use this template is to choose the implementations HfstBasicTransducer (HfstTransitionGraph<HfstTropicalTransducerTransitionData>) and HfstBasicTransition (HfstTransition<HfstTropicalTransducerTransitionData>). The class HfstTropicalTransducerTransitionData contains an input string, an output string and a float weight. HfstBasicTransducer is the implementation that is used as an example in this documentation.

An example of creating a HfstBasicTransducer [foo:bar baz:baz] with weight 0.4 from scratch:

  // Create an empty transducer
  // The transducer has initially one start state (number zero) 
  // that is not final
  HfstBasicTransducer fsm;
  // Add two states to the transducer
  fsm.add_state(1);
  fsm.add_state(2);
  // Create a transition [foo:bar] leading to state 1 with weight 0.1 ...
  HfstBasicTransition tr(1, "foo", "bar", 0.1);
  // ... and add it to state zero
  fsm.add_transition(0, tr);
  // Add a transition [baz:baz] with weight 0 from state 1 to state 2 
  fsm.add_transition(1, HfstBasicTransition(2, "baz", "baz", 0.0));
  // Set state 2 as final with weight 0.3
  fsm.set_final_weight(2, 0.3);

   An example of iterating through a HfstBasicTransducer's states
   and transitions when printing it in AT&T format to stderr:

  // The first state is always number zero.
  unsigned int source_state=0;

  // Go through all states
    for (HfstBasicTransducer::const_iterator it = fsm.begin();
     it != fsm.end(); it++ )
      {
        // Go through all transitions
    for (HfstBasicTransducer::HfstTransitions::const_iterator tr_it 
           = it->begin(); tr_it != it->end(); tr_it++)
      {
        std::cerr << source_state << "\t"
              << tr_it->get_target_state() << "\t"
              << tr_it->get_input_symbol() << "\t"
              << tr_it->get_output_symbol() << "\t"
              << tr_it->get_weight() << std::endl;
      }

    if (fsm.is_final_state(source_state)) 
      {
        std::cerr << source_state << "\t"
              << fsm.get_final_weight(source_state) << std::endl;
      }

    // the next state is numbered source_state + 1  
    source_state++;
      }

See Also: HfstBasicTransducer HfstBasicTransition

Member Typedef Documentation

typedef HfstStates::const_iterator const_iterator

A const iterator type that points a state in a graph.

The value pointed by the iterator is of type HfstTransitions.

typedef C::SymbolType HfstSymbol

Datatype for a symbol in a transition.

typedef std::pair<HfstSymbol, HfstSymbol> HfstSymbolPair

Datatype for a symbol pair in a transition.

typedef std::set<HfstSymbolPair> HfstSymbolPairSet

A set of symbol pairs.

typedef std::vector<HfstSymbolPair> HfstSymbolPairVector

A vector of symbol pairs.

typedef std::set<HfstSymbol> HfstSymbolSet

A set of symbol pairs.

typedef std::set<HfstSymbol> HfstTransitionGraphAlphabet

Datatype for the alphabet of a graph.

typedef std::vector<HfstTransition<C> > HfstTransitions

Datatype for the states of a transition in a graph.

Constructor & Destructor Documentation

HfstTransitionGraph ( void )

inline

Create a graph with one initial state that has state number zero and is not a final state, i.e. create an empty graph.

HfstTransitionGraph ( const HfstTransitionGraph< C > & graph )

inline

Create a deep copy of HfstTransitionGraph graph.

HfstTransitionGraph ( const hfst::HfstTransducer & transducer )

inline

Create an HfstTransitionGraph equivalent to HfstTransducer transducer. FIXME: move to a separate file.

Member Function Documentation

HfstState add_state ( void )

inline

Add a new state to this graph and return its number.

Returns: The next (smallest) free state number.

HfstState add_state ( HfstState s )

inline

Add a state s to this graph.

If the state already exists, it is not added again. All states with state number smaller than s are also added to the graph if they did not exist before.

Returns: s

void add_symbol_to_alphabet ( const HfstSymbol & symbol )

inline

Explicitly add symbol to the alphabet of the graph.

Note: Usually the user does not have to take care of the alphabet of a graph. This function can be useful in some special cases.

void add_symbols_to_alphabet ( const HfstSymbolSet & symbols )

inline

Same as add_symbol_to_alphabet for each symbol in symbols.

void add_transition	(	HfstState	s,
		const HfstTransition< C > &	transition,
		bool	add_symbols_to_alphabet = `true`
	)

inline

Add a transition transition to state s.

If state s does not exist, it is created.

iterator begin ( )

inline

Get an iterator to the beginning of the states in the graph.

For an example, see HfstTransitionGraph

const_iterator begin ( ) const

inline

Get a const iterator to the beginning of states in the graph.

HfstTransitionGraph& disjunct	(	const StringPairVector &	spv,
		typename C::WeightType	weight
	)

inline

Disjunct this graph with a one-path graph defined by string pair vector spv with weight weight.

Precondition: This graph must be a trie where all weights are in final states, i.e. all transitions have a zero weight.

There is no way to test whether a graph is a trie, so the use of this function is probably limited to fast construction of a lexicon. Here is an example:

HfstBasicTransducer lexicon;
HfstTokenizer TOK;
lexicon.disjunct(TOK.tokenize("dog"), 0.3);
lexicon.disjunct(TOK.tokenize("cat"), 0.5);
lexicon.disjunct(TOK.tokenize("elephant"), 1.6);

iterator end ( )

inline

Get an iterator to the end of states (last state + 1) in the graph.

const_iterator end ( ) const

inline

Get a const iterator to the end of states (last state + 1) in the graph.

const HfstTransitionGraphAlphabet& get_alphabet ( ) const

inline

Get the set of HfstSymbols in the alphabet of the graph.

The HfstSymbols do not necessarily occur in any transitions of the graph. Epsilon, unknown and identity symbols are always included in the alphabet.

C::WeightType get_final_weight ( HfstState s ) const

inline

Get the final weight of state s in this graph.

HfstState get_max_state ( ) const

inline

Get the biggest state number in use.

HfstTransitionGraph& harmonize ( HfstTransitionGraph< C > & another )

inline

Harmonize this HfstTransitionGraph and another.

In harmonization the unknown and identity symbols in transitions of both graphs are expanded according to the symbols that are previously unknown to the graph.

For example the graphs

   [a:b ?:?]
   [c:d ? ?:c]

are expanded to

   [ a:b [?:? | ?:c | ?:d | c:d | d:c | c:? | d:?] ] 
   [ c:d [? | a | b] [?:c| a:c | b:?] ]

when harmonized. The symbol "?" means @_UNKNOWN_SYMBOL_@ in either or both sides of a transition (transitions of type [?:x], [x:?] and [?:?]). The transition [?] means [@_IDENTITY_SYMBOL_@].

Note: This function is always called for arguments of functions that take two or more graphs as their arguments, unless otherwise said.

HfstTransitionGraph& insert_freely	(	const HfstSymbolPair &	symbol_pair,
		typename C::WeightType	weight
	)

inline

Insert freely any number of symbol_pair in the graph with weight weight.

HfstTransitionGraph& insert_freely	(	const HfstSymbolPairSet &	symbol_pairs,
		typename C::WeightType	weight
	)

inline

Insert freely any number of any symbol in symbol_pairs in the graph with weight weight.

HfstTransitionGraph& insert_freely ( const HfstTransitionGraph< C > & graph )

inline

Insert freely any number of graph in this graph.

bool is_final_state ( HfstState s ) const

inline

Whether state s is final. FIXME: return positive infinity instead if not final.

int longest_path_size ( )

inline

The length of longest string accepted by this graph. If no string is accepted, return -1.

HfstTransitionGraph& operator= ( const HfstTransitionGraph< C > & graph )

inline

The assignment operator.

const HfstTransitions& operator[] ( HfstState s ) const

inline

Get the set of transitions of state s in this graph.

If the state does not exist, a StateIndexOutOfBoundsException is thrown.

std::vector<unsigned int> path_sizes ( )

inline

The lengths of strings accepted by this graph, in descending order. If not string is accepted, return an empty vector.

void prune_alphabet ( bool force = true )

inline

Remove all symbols that do not occur in transitions of the graph from its alphabet.

Parameters

force Whether unused symbols are removed even if unknown or identity symbols occur in transitions.

Epsilon, unknown and identity symbols are always included in the alphabet.

static HfstTransitionGraph read_in_att_format	(	std::istream &	is,
		std::string	epsilon_symbol,
		unsigned int &	linecount
	)

inlinestatic

Create an HfstTransitionGraph as defined in AT&T transducer format in istream is. epsilon_symbol defines how epsilon is represented.

Precondition: is not at end, otherwise an exception is thrown.

Note: Multiple AT&T transducer definitions are separated with the line "--".

static HfstTransitionGraph read_in_att_format	(	FILE *	file,
		std::string	epsilon_symbol,
		unsigned int &	linecount
	)

inlinestatic

Create an HfstTransitionGraph as defined in AT&T transducer format in FILE file. epsilon_symbol defines how epsilon is represented.

Precondition: is not at end, otherwise an exception is thrown.

Note: Multiple AT&T transducer definitions are separated with the line "--".

void remove_symbol_from_alphabet ( const HfstSymbol & symbol )

inline

Remove symbol symbol from the alphabet of the graph.

Note: Use with care, removing symbols that occur in the transitions of the graph can have unexpected results.

void remove_transition	(	HfstState	s,
		const HfstTransition< C > &	transition,
		bool	remove_symbols_from_alphabet = `false`
	)

inline

Remove transition transition from state s. remove_symbols_from_alphabet defines whether symbols in transition are removed from the alphabet if they are no longer used in the graph.

If state or transition does not exist, nothing is done.

void set_final_weight	(	HfstState	s,
		const typename C::WeightType &	weight
	)

inline

Set the final weight of state s in this graph to weight.

If the state does not exist, it is created.

HfstTransitionGraph& sort_arcs ( void )

inline

Sort the arcs of this transducer according to input and output symbols.

std::vector<HfstState> states ( ) const

inline

The states of the graph.

HfstTransitionGraph& substitute	(	const HfstSymbol &	old_symbol,
		const HfstSymbol &	new_symbol,
		bool	input_side = `true`,
		bool	output_side = `true`
	)

inline

Substitute old_symbol with new_symbol in all transitions. input_side and output_side define whether the substitution is made on input and output sides.

HfstTransitionGraph& substitute ( const HfstSymbolSubstitutions & substitutions )

inline

Substitute all transitions as defined in substitutions.

HfstTransitionGraph& substitute ( const HfstSymbolPairSubstitutions & substitutions )

inline

Substitute all transitions as defined in substitutions.

For each transition x:y, substitutions is searched and if a mapping x:y -> X:Y is found, the transition x:y is replaced with X:Y. If no mapping is found, the transition remains the same.

HfstTransitionGraph& substitute	(	const HfstSymbolPair &	sp,
		const HfstSymbolPairSet &	sps
	)

inline

Substitute all transitions sp with a set of transitions sps.

HfstTransitionGraph& substitute	(	const HfstSymbolPair &	old_pair,
		const HfstSymbolPair &	new_pair
	)

inline

Substitute all transitions old_pair with new_pair.

HfstTransitionGraph& substitute ( bool(*)(const HfstSymbolPair &sp, HfstSymbolPairSet &sps) func )

inline

Substitute all transitions with a set of transitions as defined by function func.

func takes as its argument a transition sp and inserts into the set of transitions sps the transitions with which the original transition sp must be replaced. func returns a value indicating whether any substitution must be made, i.e. whether any transition was inserted into sps.

HfstTransitionGraph& substitute	(	const HfstSymbolPair &	sp,
		const HfstTransitionGraph< C > &	graph
	)

inline

Substitute all transitions old_symbol : new_symbol with a copy of graph.

Copies of graph are attached to this graph with epsilon transitions.

The weights of the transitions to be substituted are copied to epsilon transitions leaving from the source state of the transitions to be substituted to the initial state of a copy of graph.

The final weights in graph are copied to epsilon transitions leading from the final states (after substitution non-final states) of graph to target states of transitions old_symbol : new_symbol (that are substituted) in this graph.

const HfstTransitions& transitions ( HfstState s ) const

inline

Alternative name for operator[].

Python interface uses this function as '[]' is not a legal name.

See Also: operator[]

void write_in_att_format	(	std::ostream &	os,
		bool	write_weights = `true`
	)

inline

Write the graph in AT&T format to ostream os. write_weights defines whether weights are printed.

void write_in_att_format	(	FILE *	file,
		bool	write_weights = `true`
	)

inline

Write the graph in AT&T format to FILE file. write_weights defines whether weights are printed.

void write_in_att_format_number	(	FILE *	file,
		bool	write_weights = `true`
	)

inline

Write the graph in AT&T format to FILE file using numbers instead of symbol names. write_weights defines whether weights are printed.

void write_in_prolog_format	(	FILE *	file,
		const std::string &	name,
		bool	write_weights = `true`
	)

inline

Write the graph in prolog format to FILE file. write_weights defines whether weights are printed (todo).

void write_in_prolog_format	(	std::ostream &	os,
		const std::string &	name,
		bool	write_weights = `true`
	)

inline

Write the graph in prolog format to ostream os. write_weights defines whether weights are printed (todo).

void write_in_xfst_format	(	std::ostream &	os,
		bool	write_weights = `true`
	)

inline

Write the graph in xfst text format to ostream os. write_weights defines whether weights are printed (todo).

void write_in_xfst_format	(	FILE *	file,
		bool	write_weights = `true`
	)

inline

Write the graph in xfst text format to FILE file. write_weights defines whether weights are printed (todo).

Member Data Documentation

std::string name

The name of the graph.

The documentation for this class was generated from the following files:

libhfst/src/HfstDataTypes.h
libhfst/src/implementations/HfstTransitionGraph.h

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Detailed Description

template<class C> class hfst::implementations::HfstTransitionGraph< C >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class C>
class hfst::implementations::HfstTransitionGraph< C >