gfsmStateSort.h File Reference

sort states of a gfsmAutomaton More...

#include <gfsmAutomaton.h>

Include dependency graph for gfsmStateSort.h:

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

Go to the source code of this file.

Functions
void	gfsm_statesort_aff (gfsmAutomaton *fsm, gfsmStateIdMap *old2new)
void	gfsm_statesort_dfs (gfsmAutomaton *fsm, gfsmStateIdMap *old2new)
void	gfsm_statesort_bfs (gfsmAutomaton *fsm, gfsmStateIdMap *old2new)
Methods: gfsmStateIdMap application
void	gfsm_statemap_apply (gfsmAutomaton *fsm, gfsmStateIdMap *old2new, gfsmStateId n_new_states)
Methods: gfsmStateIdMap acquisition
gfsmStateIdMap *	gfsm_statemap_aff (gfsmAutomaton *fsm, gfsmStateIdMap *old2new)
gfsmStateIdMap *	gfsm_statemap_dfs (gfsmAutomaton *fsm, gfsmStateIdMap *old2new)
gfsmStateIdMap *	gfsm_statemap_bfs (gfsmAutomaton *fsm, gfsmStateIdMap *old2new)
gfsmStateIdMap *	gfsm_statemap_depths (gfsmAutomaton *fsm, gfsmStateIdMap *depths)
Low-level fsmStateIdMap utilities
gfsmStateIdMap *	gfsm_statemap_init (gfsmStateIdMap *smap, gfsmStateId sz)

Detailed Description

Function Documentation

void gfsm_statesort_aff	(	gfsmAutomaton *	fsm,
		gfsmStateIdMap *	old2new
	)

Type for maps from (old) gfsmStateId to new gfsmStateId , used by state-sorting functions.
 GArray of ::gfsmStateId such that @code qid_new==old2new[qid_old] \enccode .
 \a qid_new may be ::gfsmNoState to ignore the corresponding \a qid_old

*/ typedef GArray gfsmStateIdMap;

/*======================================================================*/ /// Methods: High-level state sorting //@{

/** Sort fsm according to an 'affine' enumeration. Basically just a wrapper for

gfsm_statemap_apply(fsm,gfsm_statemap_aff(fsm,old2new),0); 

Caller is responsible for freeing old2new if it is specified and non-NULL.

Parameters

fsm	automaton to be sorted
old2new	target ::gfsmStateIdMap , or NULL to use a temporary map

See Also

gfsm_renumber_states(), gfsm_statemap_aff(), gfsm_statemap_apply()

void gfsm_statesort_dfs	(	gfsmAutomaton *	fsm,
		gfsmStateIdMap *	old2new
	)

Sort fsm according to a depth-first enumeration. Basically just a wrapper for

gfsm_statemap_apply(fsm,gfsm_statemap_dfs(fsm,old2new),0); 

Caller is responsible for freeing old2new if it is specified and non-NULL.

Parameters

fsm	automaton to be sorted
old2new	target ::gfsmStateIdMap , or NULL to use a temporary map

See Also

gfsm_statemap_dfs(), gfsm_statemap_apply()

void gfsm_statesort_bfs	(	gfsmAutomaton *	fsm,
		gfsmStateIdMap *	old2new
	)

Sort fsm according to a breadth-first enumeration. Basically just a wrapper for

gfsm_statemap_apply(fsm,gfsm_statemap_bfs(fsm,old2new),0); 

Caller is responsible for freeing old2new if it is specified and non-NULL.

Parameters

fsm	automaton to be sorted
old2new	target ::gfsmStateIdMap , or NULL to use a temporary map

See Also

gfsm_statemap_bfs(), gfsm_statemap_apply()

void gfsm_statemap_apply	(	gfsmAutomaton *	fsm,
		gfsmStateIdMap *	old2new,
		gfsmStateId	n_new_states
	)

Renumber states of fsm according to the ::gfsmStateIdMap old2new .

Parameters

fsm	automaton whose states are to be mapped
old2new	state-mapping to apply
n_new_states	number of target states to allocate; may be 0 (zero) to auto-compute

gfsmStateIdMap* gfsm_statemap_aff	(	gfsmAutomaton *	fsm,
		gfsmStateIdMap *	old2new
	)

Populate and return an 'affine' ::gfsmStateIdMap for fsm. The returns ::gfsmStateIdMap is such that the target state enumeration has no 'gaps', and the root state is mapped to the 0 (zero).

Parameters

fsm	automaton to be mapped
old2new	destination ::gfsmStateIdMap , or NULL to create and return a new map

Returns

old2new , or a new ::gfsmStateIdMap

See Also

gfsm_renumber_states()

gfsmStateIdMap* gfsm_statemap_dfs	(	gfsmAutomaton *	fsm,
		gfsmStateIdMap *	old2new
	)

Populate and return a depth-first ::gfsmStateIdMap for fsm

Parameters

fsm	automaton to be mapped
old2new	destination ::gfsmStateIdMap , or NULL to create and return a new map

Returns

old2new , or a new ::gfsmStateIdMap

gfsmStateIdMap* gfsm_statemap_bfs	(	gfsmAutomaton *	fsm,
		gfsmStateIdMap *	old2new
	)

Populate and return a breadth-first ::gfsmStateIdMap for fsm

Parameters

fsm	automaton to be mapped
old2new	destination ::gfsmStateIdMap , or NULL to create and return a new map

Returns

old2new , or a new ::gfsmStateIdMap

gfsmStateIdMap* gfsm_statemap_depths	(	gfsmAutomaton *	fsm,
		gfsmStateIdMap *	depths
	)

Get depth information for each state; depths[q]==minim-path-length(q0,q) or gfsmNoState if non-accessible

Parameters

fsm	automaton to be investigated
depths	destination ::gfsmStateIdMap , or NULL to create and return a new map

Returns

depths or a new gfsmStateIdMap

gfsmStateIdMap* gfsm_statemap_init	(	gfsmStateIdMap *	smap,
		gfsmStateId	sz
	)

Initialize a ::gfsmStateIdMap smap of size .

• a new ::gfsmStateIdMap will be allocated if smap is passed as NULL
• all target values in sm are initialized to gfsmNoState.

  Parameters

  smap	map to initialize , or NULL
  sz	new size of map

  Returns

  smap , or a new ::gfsmStateIdMap