Make a BFS in a spot::tgba to compute a twa_run::steps. More...

#include <spot/twaalgos/bfssteps.hh>

Collaboration diagram for spot::bfs_steps:

Public Member Functions
	bfs_steps (const const_twa_ptr &a)

const state *	search (const state *start, twa_run::steps &l)
	Start the search from start, and append the resulting path (if any) to l. More...

virtual const state *	filter (const state *s)=0
	Return a state* that is unique for a. More...

virtual bool	match (twa_run::step &step, const state *dest)=0
	Whether a new transition completes a path. More...

virtual void	finalize (const std::map< const state , twa_run::step, state_ptr_less_than > &father, const twa_run::step &s, const state start, twa_run::steps &l)
	Append the resulting path to the resulting run. More...

Protected Attributes
const_twa_ptr	a_
	The spot::tgba we are searching into. More...

Detailed Description

Make a BFS in a spot::tgba to compute a twa_run::steps.

This class should be used to compute the shortest path between a state of a spot::tgba and the first transition or state that matches some conditions.

These conditions should be specified by defining bfs_steps::match() in a subclass. Also the search can be restricted to some set of states with a proper definition of bfs_steps::filter().

Member Function Documentation

◆ filter()

virtual const state * spot::bfs_steps::filter ( const state * s )

pure virtual

Return a state* that is unique for a.

bfs_steps does not do handle the memory for the states it generates, this is the job of filter(). Here s is a new state* that search() has just allocated (using twa_succ_iterator::dst()), and the return of this function should be a state* that does not need to be freed by search().

If you already have a map or a set which uses states as keys, you should probably arrange for filter() to return these keys, and destroy s. Otherwise you will have to define such a set, just to be able to destroy all the state* in a subclass.

This function can return 0 if the given state should not be explored.

◆ finalize()

virtual void spot::bfs_steps::finalize	(	const std::map< const state *, twa_run::step, state_ptr_less_than > &	father,
		const twa_run::step &	s,
		const state *	start,
		twa_run::steps &	l
	)

virtual

Append the resulting path to the resulting run.

This is called after match() has returned true, to append the resulting path to l. This seldom needs to be overridden, unless you do not want l to be updated (in which case an empty finalize() will do).

◆ match()

virtual bool spot::bfs_steps::match	(	twa_run::step &	step,
		const state *	dest
	)

pure virtual

Whether a new transition completes a path.

This function is called immediately after each call to filter() that does not return 0.

Parameters

step	the source state (as returned by filter()), and the labels of the outgoing transition
dest	the destination state (as returned by filter())

Returns: true iff a path that included this step should be accepted.

The search() algorithms stops as soon as match() returns true, and when this happens the list argument of search() is be augmented with the shortest past that ends with this transition.

◆ search()

const state * spot::bfs_steps::search	(	const state *	start,
		twa_run::steps &	l
	)

Start the search from start, and append the resulting path (if any) to l.

Returns: the destination state of the last step (not included in l) if a matching path was found, or 0 otherwise.

Member Data Documentation

◆ a_

const_twa_ptr spot::bfs_steps::a_

protected

The spot::tgba we are searching into.

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

spot/twaalgos/bfssteps.hh

Public Member Functions

Protected Attributes