spot  2.11.6
Public Member Functions | Protected Attributes | List of all members
spot::bfs_steps Class Referenceabstract

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 statesearch (const state *start, twa_run::steps &l)
 Start the search from start, and append the resulting path (if any) to l. More...
 
virtual const statefilter (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
stepthe source state (as returned by filter()), and the labels of the outgoing transition
destthe 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:

Please direct any question, comment, or bug report to the Spot mailing list at spot@lrde.epita.fr.
Generated on Fri Feb 27 2015 10:00:07 for spot by doxygen 1.9.1