Path discovery & enumeration. More...

#include <gfsmAutomaton.h>
#include <gfsmPaths.hi>

Include dependency graph for gfsmPaths.h:

This graph shows which files directly or indirectly include this file:

Data Structures
struct	gfsmPath
	Type for an automaton path (labels only, no alignment) More...
struct	gfsmPathsToStringsOptions_
	Utility struct for gfsm_paths_to_strings() More...
struct	gfsmArcPathToStringOptions_
	Utility struct for gfsm_arcpath_to_gstring() and friends. More...

Typedefs
typedef GPtrArray	gfsmArcPath
	Type for an automaton arc path (full alignment: GPtrArray of gfsmArc*)

Functions

static gfsmArcPath *	gfsm_arcpath_new (void)
static gfsmArcPath *	gfsm_arcpath_new_append (gfsmArcPath p1, gfsmArc a)
gfsmArcPath *	gfsm_arcpath_copy (gfsmArcPath dst, gfsmArcPath src)
static gfsmArcPath *	gfsm_arcpath_dup (gfsmArcPath *p1)
static void	gfsm_arcpath_free (gfsmArcPath *p)
void	gfsm_arcpath_list_free (GSList *arcpaths)

gfsmLabelVector Utilities
#define	gfsm_label_vector_dup(src) gfsm_label_vector_copy(g_ptr_array_sized_new(src->len), src)
gfsmLabelVector *	gfsm_label_vector_copy (gfsmLabelVector dst, gfsmLabelVector src)
gfsmLabelVector *	gfsm_label_vector_reverse (gfsmLabelVector *v)

gfsmPath Utilities
#define	gfsm_path_new(sr) gfsm_path_new_full(NULL,NULL,gfsm_sr_one(sr))
static gfsmPath *	gfsm_path_new_full (gfsmLabelVector lo, gfsmLabelVector hi, gfsmWeight w)
gfsmPath *	gfsm_path_new_copy (gfsmPath *p1)
gfsmPath *	gfsm_path_new_append (gfsmPath p1, gfsmLabelVal lo, gfsmLabelVal hi, gfsmWeight w, gfsmSemiring sr)
gfsmPath *	gfsm_path_new_times_w (gfsmPath p1, gfsmWeight w, gfsmSemiring sr)
static void	gfsm_path_push (gfsmPath p, gfsmLabelVal lo, gfsmLabelVal hi, gfsmWeight w, gfsmSemiring sr)
static void	gfsm_path_pop (gfsmPath *p, gfsmLabelVal lo, gfsmLabelVal hi)
gint	gfsm_path_compare_data (const gfsmPath p1, const gfsmPath p2, gfsmSemiring *sr)
static gfsmPath *	gfsm_path_reverse (gfsmPath *p)
static void	gfsm_path_free (gfsmPath *p)

Automaton Serialization: gfsmPath
#define	_gfsm_paths_to_strings_options gfsmPathsToStringsOptions_
typedef struct gfsmPathsToStringsOptions_	gfsmPathsToStringsOptions
	Utility struct for gfsm_paths_to_strings()
gfsmSet *	gfsm_automaton_paths (gfsmAutomaton fsm, gfsmSet paths)
gfsmSet *	gfsm_automaton_paths_full (gfsmAutomaton fsm, gfsmSet paths, gfsmLabelSide which)
gfsmSet *	_gfsm_automaton_paths_r (gfsmAutomaton fsm, gfsmSet paths, gfsmLabelSide which, gfsmStateId q, gfsmPath *path)
GSList *	gfsm_paths_to_strings (gfsmSet paths, gfsmAlphabet abet_lo, gfsmAlphabet abet_hi, gfsmSemiring sr, gboolean warn_on_undefined, gboolean att_style, GSList *strings)
gboolean	_gfsm_paths_to_strings_foreach_func (gfsmPath path, gpointer value_dummy, gfsmPathsToStringsOptions opts)
GString *	gfsm_path_to_gstring (gfsmPath path, GString gs, gfsmAlphabet abet_lo, gfsmAlphabet abet_hi, gfsmSemiring *sr, gboolean warn_on_undefined, gboolean att_style)
char *	gfsm_path_to_string (gfsmPath path, gfsmAlphabet abet_lo, gfsmAlphabet abet_hi, gfsmSemiring sr, gboolean warn_on_undefined, gboolean att_style)

Automaton Serialization: gfsmArcPath
typedef struct gfsmArcPathToStringOptions_	gfsmArcPathToStringOptions
	Utility struct for gfsm_arcpath_to_gstring() and friends.
GSList *	gfsm_automaton_arcpaths (gfsmAutomaton *fsm)
void	_gfsm_automaton_arcpaths_r (gfsmAutomaton fsm, gfsmStateId qid, GSList path, guint path_len, GSList paths, GSList nodes)
GString *	gfsm_arcpath_to_gstring (gfsmArcPath path, GString gs, gfsmArcPathToStringOptions *opts)
char *	gfsm_arcpath_to_string (gfsmArcPath path, gfsmArcPathToStringOptions opts)
GSList *	gfsm_arcpaths_to_strings (GSList paths, gfsmArcPathToStringOptions opts)

Automaton Serialization: Viterbi
#define	gfsm_viterbi_trellis_paths(trellis, paths) gfsm_viterbi_trellis_paths_full((trellis),(paths),gfsmLSUpper)
#define	gfsm_viterbi_trellis_bestpath(trellis, path) gfsm_viterbi_trellis_bestpath_full((trellis),(path),gfsmLSUpper)
gfsmSet *	gfsm_viterbi_trellis_paths_full (gfsmAutomaton trellis, gfsmSet paths, gfsmLabelSide which)
gfsmPath *	gfsm_viterbi_trellis_bestpath_full (gfsmAutomaton trellis, gfsmPath path, gfsmLabelSide which)
void	_gfsm_viterbi_trellis_bestpath_r (gfsmAutomaton trellis, gfsmPath path, gfsmLabelSide which, gfsmStateId qid)

Detailed Description

Macro Definition Documentation

#define gfsm_label_vector_dup ( src ) gfsm_label_vector_copy(g_ptr_array_sized_new(src->len), src)

Duplicate a gfsmLabelVector.

Returns: dst

#define gfsm_path_new ( sr ) gfsm_path_new_full(NULL,NULL,gfsm_sr_one(sr))

Create and return a new empty gfsmPath, specifying semiring.

#define _gfsm_paths_to_strings_options gfsmPathsToStringsOptions_

backwards compatible type alias

#define gfsm_viterbi_trellis_paths	(	trellis,
		paths
	)	gfsm_viterbi_trellis_paths_full((trellis),(paths),gfsmLSUpper)

Extract upper side of all paths from a Viterbi trellis.

Returns a gfsmSet whose elements are (gfsmPath*)s. allocated with gfsm_slice_new(). It is the caller's responsibility to free the returned objects.

Returns: paths if non-NULL, otherwise a new gfsmSet*.

#define gfsm_viterbi_trellis_bestpath	(	trellis,
		path
	)	gfsm_viterbi_trellis_bestpath_full((trellis),(path),gfsmLSUpper)

Extract the upper-side of the best path from a Viterbi trellis.

Returns: path if non-NULL, otherwise a new gfsmPath*.

Typedef Documentation

typedef GPtrArray gfsmArcPath

typedef struct gfsmPathsToStringsOptions_ gfsmPathsToStringsOptions

typedef struct gfsmArcPathToStringOptions_ gfsmArcPathToStringOptions

Function Documentation

gfsmLabelVector* gfsm_label_vector_copy	(	gfsmLabelVector *	dst,
		gfsmLabelVector *	src
	)

Copy gfsmLabelVector.

Returns: dst

gfsmLabelVector* gfsm_label_vector_reverse ( gfsmLabelVector * v )

Reverse a gfsmLabelVector.

Returns: v

static gfsmPath* gfsm_path_new_full	(	gfsmLabelVector *	lo,
		gfsmLabelVector *	hi,
		gfsmWeight	w
	)

inlinestatic

Create and return a new gfsmPath, specifying components If either of lo or hi are NULL, a new vector will be created.

gfsmPath* gfsm_path_new_copy ( gfsmPath * p1 )

Create and return a new gfsmPath as a copy of an existing gfsmPath

gfsmPath* gfsm_path_new_append	(	gfsmPath *	p1,
		gfsmLabelVal	lo,
		gfsmLabelVal	hi,
		gfsmWeight	w,
		gfsmSemiring *	sr
	)

Create and return a new gfsmPath, appending to an existing path

gfsmPath* gfsm_path_new_times_w	(	gfsmPath *	p1,
		gfsmWeight	w,
		gfsmSemiring *	sr
	)

Create and return a new gfsmPath as a copy of an existing gfsmPath with weight multiplied by w

static void gfsm_path_push	(	gfsmPath *	p,
		gfsmLabelVal	lo,
		gfsmLabelVal	hi,
		gfsmWeight	w,
		gfsmSemiring *	sr
	)

inlinestatic

Append an arc to a gfsmPath

static void gfsm_path_pop	(	gfsmPath *	p,
		gfsmLabelVal	lo,
		gfsmLabelVal	hi
	)

inlinestatic

Pop an arc from a gfsmPath

gint gfsm_path_compare_data	(	const gfsmPath *	p1,
		const gfsmPath *	p2,
		gfsmSemiring *	sr
	)

3-way path comparison function.

static gfsmPath* gfsm_path_reverse ( gfsmPath * p )

inlinestatic

Reverse a gfsmPath

static void gfsm_path_free ( gfsmPath * p )

inlinestatic

Destroy a gfsmPath

gfsmSet* gfsm_automaton_paths	(	gfsmAutomaton *	fsm,
		gfsmSet *	paths
	)

Serialize a gfsmAutomaton to a set of (gfsmPath*)s. Really just a wrapper for gfsm_automaton_paths_full()

Parameters

fsm	Acyclic automaton to be serializd
paths	output set or NULL

Returns: paths if non-NULL, otherwise a new gfsmSet*.

gfsmSet* gfsm_automaton_paths_full	(	gfsmAutomaton *	fsm,
		gfsmSet *	paths,
		gfsmLabelSide	which
	)

Serialize a gfsmAutomaton to a set of (gfsmPath*)s.

Causes deep recursion for cyclic automata. Returns a gfsmSet whose elements are (gfsmPath*)s. allocated with gfsm_slice_new(). It is the caller's responsibility to free the returned objects.

Parameters

fsm	Acyclic automaton to be serializd
which	Which side of arc-labels to serialize
paths	output set or NULL

Returns: paths if non-NULL, otherwise a new gfsmSet*.

gfsmSet* _gfsm_automaton_paths_r	(	gfsmAutomaton *	fsm,
		gfsmSet *	paths,
		gfsmLabelSide	which,
		gfsmStateId	q,
		gfsmPath *	path
	)

Recursive guts for gfsm_automaton_paths()

GSList* gfsm_paths_to_strings	(	gfsmSet *	paths,
		gfsmAlphabet *	abet_lo,
		gfsmAlphabet *	abet_hi,
		gfsmSemiring *	sr,
		gboolean	warn_on_undefined,
		gboolean	att_style,
		GSList *	strings
	)

Convert a gfsmPathSet to a list of (char*)s. abet_lo and abet_hi should be (gfsmStringAlphabet*)s.

gboolean _gfsm_paths_to_strings_foreach_func	(	gfsmPath *	path,
		gpointer	value_dummy,
		gfsmPathsToStringsOptions *	opts
	)

Utility for gfsm_paths_to_strings()

GString* gfsm_path_to_gstring	(	gfsmPath *	path,
		GString *	gs,
		gfsmAlphabet *	abet_lo,
		gfsmAlphabet *	abet_hi,
		gfsmSemiring *	sr,
		gboolean	warn_on_undefined,
		gboolean	att_style
	)

Append string for a single gfsmPath* to a GString, which may be NULL to allocate a new string.

Returns: gs if non-NULL, otherwise a new GString*.

Warning: it is the caller's responsibility to free the returned GString*.

char* gfsm_path_to_string	(	gfsmPath *	path,
		gfsmAlphabet *	abet_lo,
		gfsmAlphabet *	abet_hi,
		gfsmSemiring *	sr,
		gboolean	warn_on_undefined,
		gboolean	att_style
	)

Allocate and return a new string (char*) for a single gfsmPath*.

Returns: new (char*) representing path.

Warning: it is the callers responsibility to free the returned char*.

static gfsmArcPath* gfsm_arcpath_new ( void )

inlinestatic

Create and return a new gfsmArcPath*

static gfsmArcPath* gfsm_arcpath_new_append	(	gfsmArcPath *	p1,
		gfsmArc *	a
	)

inlinestatic

Create and return a new gfsmArcPath* by appending a to an existing path p1

gfsmArcPath* gfsm_arcpath_copy	(	gfsmArcPath *	dst,
		gfsmArcPath *	src
	)

Copy a gfsmArcPath* src to dst

Returns: dst

static gfsmArcPath* gfsm_arcpath_dup ( gfsmArcPath * p1 )

inlinestatic

Create and return a new gfsmArcPath* by duplicating an old one

static void gfsm_arcpath_free ( gfsmArcPath * p )

inlinestatic

Destroy a gfsmArcPath

void gfsm_arcpath_list_free ( GSList * arcpaths )

Destroy a GSList of gfsmArcPath*

GSList* gfsm_automaton_arcpaths ( gfsmAutomaton * fsm )

Serialize a gfsmAutomaton to a list of (gfsmArcPath*)s. Causes deep recursion for cyclic automata. Returns a GSList whose element data are (gfsmArcPath*)s. It is the caller's responsibility to free the returned objects. The pointer data in the returned (gfsmArcPath*)s are (gfsmArc*)s into fsm, and will be freed with that automaton for all but the final pointer of each gfsmArcPath, and the final element is a gpointer-encoded gfsmWeight representing the final weight associated with the arc path; extract it e.g. with gfsm_ptr2weight(arcpath->data[arcpath->len-1]).

Parameters

fsm	Acyclic automaton to be serializd

Returns: a new GSList of (gfsmArcPath*)s

void _gfsm_automaton_arcpaths_r	(	gfsmAutomaton *	fsm,
		gfsmStateId	qid,
		GSList *	path,
		guint	path_len,
		GSList **	paths,
		GSList **	nodes
	)

Recursive guts for gfsm_automaton_arcpaths().

Parameters

fsm	automaton being serialized
qid	current state in automaton search
path	path to current state (GSList of gfsmArc*), reversed
path_len	length of current path (for cyclicity check)
paths	GSList of (GSList of gfsmArc): all complete paths, reversed
nodes	GSList of (GSList of gfsmArc): all allocated nodes

GString* gfsm_arcpath_to_gstring	(	gfsmArcPath *	path,
		GString *	gs,
		gfsmArcPathToStringOptions *	opts
	)

Append string for a single gfsmArcPath* to a GString, which may be NULL to allocate a new string.

Returns: gs if non-NULL, otherwise a new GString*.

Warning: it is the caller's responsibility to free the returned GString*.

char* gfsm_arcpath_to_string	(	gfsmArcPath *	path,
		gfsmArcPathToStringOptions *	opts
	)

Allocate and return a new string (char*) for a single gfsmArcPath*.

Returns: new (char*) representing path.

Warning: it is the callers responsibility to free the returned char*.

GSList* gfsm_arcpaths_to_strings	(	GSList *	paths,
		gfsmArcPathToStringOptions *	opts
	)

Stringifily a whole GSList of (gfsmArcPath*)s.

Returns: GSList of char*

gfsmSet* gfsm_viterbi_trellis_paths_full	(	gfsmAutomaton *	trellis,
		gfsmSet *	paths,
		gfsmLabelSide	which
	)

Extract all paths from a Viterbi trellis.

Returns a gfsmSet whose elements are (gfsmPath*)s. allocated with gfsm_slice_new(). It is the caller's responsibility to free the returned objects.

Returns: paths if non-NULL, otherwise a new gfsmSet*.

gfsmPath* gfsm_viterbi_trellis_bestpath_full	(	gfsmAutomaton *	trellis,
		gfsmPath *	path,
		gfsmLabelSide	which
	)

Extract the best path from a Viterbi trellis.

Returns: path if non-NULL, otherwise a new gfsmPath*.

void _gfsm_viterbi_trellis_bestpath_r	(	gfsmAutomaton *	trellis,
		gfsmPath *	path,
		gfsmLabelSide	which,
		gfsmStateId	qid
	)

Guts for gfsm_viterbi_trellis_*path*()

Data Structures

Typedefs

Functions

gfsmLabelVector Utilities

gfsmPath Utilities

Automaton Serialization: gfsmPath

Automaton Serialization: gfsmArcPath

Automaton Serialization: Viterbi

Detailed Description

Macro Definition Documentation

Typedef Documentation

Function Documentation