fst::SccVisitor< A > Class Template Reference

#include <fst/connect.h>

Collaboration diagram for fst::SccVisitor< A >:

List of all members.

Public Types
typedef A	Arc
typedef Arc::Weight	Weight
typedef A::StateId	StateId
Public Member Functions
	SccVisitor (vector< StateId > *scc, vector< bool > *access, vector< bool > *coaccess, uint64 *props)
	SccVisitor (uint64 *props)
void	InitVisit (const Fst< A > &fst)
bool	InitState (StateId s, StateId root)
bool	TreeArc (StateId s, const A &arc)
bool	BackArc (StateId s, const A &arc)
bool	ForwardOrCrossArc (StateId s, const A &arc)
void	FinishState (StateId s, StateId p, const A *)
void	FinishVisit ()

---

Detailed Description

template<class A>
class fst::SccVisitor< A >

Finds and returns strongly-connected components, accessible and coaccessible states and related properties. Uses Tarjan's single DFS SCC algorithm (see Aho, et al, "Design and Analysis of Computer Algorithms", 189pp). Use with DfsVisit();

Definition at line 120 of file connect.h.

---

Member Typedef Documentation

template<class A>

typedef A fst::SccVisitor< A >::Arc

Definition at line 122 of file connect.h.

template<class A>

typedef A::StateId fst::SccVisitor< A >::StateId

Definition at line 124 of file connect.h.

template<class A>

typedef Arc::Weight fst::SccVisitor< A >::Weight

Definition at line 123 of file connect.h.

---

Constructor & Destructor Documentation

template<class A>

fst::SccVisitor< A >::SccVisitor	(	vector< StateId > *	scc,
		vector< bool > *	access,
		vector< bool > *	coaccess,
		uint64 *	props
	)			[inline]

scc[i]: strongly-connected component number for state i. SCC numbers will be in topological order for acyclic input. access[i]: accessibility of state i. coaccess[i]: coaccessibility of state i. Any of above can be NULL. props: related property bits (cyclicity, initial cyclicity, accessibiliity, coaccessiblity) set/cleared (o.w. unchanged).

Definition at line 133 of file connect.h.

template<class A>

fst::SccVisitor< A >::SccVisitor

(

uint64 *

props

)

[inline]

Definition at line 136 of file connect.h.

---

Member Function Documentation

template<class A>

bool fst::SccVisitor< A >::BackArc	(	StateId	s,
		const A &	arc
	)			[inline]

Definition at line 145 of file connect.h.

template<class A >

void fst::SccVisitor< A >::FinishState	(	StateId	s,
		StateId	p,
		const A *
	)			[inline]

Definition at line 256 of file connect.h.

template<class A>

void fst::SccVisitor< A >::FinishVisit

(

)

[inline]

Definition at line 172 of file connect.h.

template<class A>

bool fst::SccVisitor< A >::ForwardOrCrossArc	(	StateId	s,
		const A &	arc
	)			[inline]

Definition at line 160 of file connect.h.

template<class A >

bool fst::SccVisitor< A >::InitState	(	StateId	s,
		StateId	root
	)			[inline]

Definition at line 227 of file connect.h.

template<class A >

void fst::SccVisitor< A >::InitVisit

(

const Fst< A > &

fst

)

[inline]

Definition at line 202 of file connect.h.

template<class A>

bool fst::SccVisitor< A >::TreeArc	(	StateId	s,
		const A &	arc
	)			[inline]

Definition at line 143 of file connect.h.

---

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

• openfst-1.2.6/src/include/fst/connect.h