Public Member Functions

fst::SccVisitor< Arc > Class Template Reference

#include <fst/connect.h>

Collaboration diagram for fst::SccVisitor< Arc >:
Collaboration graph
[legend]

List of all members.

Public Member Functions

 SccVisitor (std::vector< StateId > *scc, std::vector< bool > *access, std::vector< bool > *coaccess, uint64 *props)
 SccVisitor (uint64 *props)
void InitVisit (const Fst< Arc > &fst)
bool InitState (StateId s, StateId root)
bool TreeArc (StateId s, const Arc &arc)
bool BackArc (StateId s, const Arc &arc)
bool ForwardOrCrossArc (StateId s, const Arc &arc)
void FinishState (StateId state, StateId p, const Arc *)
 Last argument always ignored, but required by the interface.
void FinishVisit ()

Detailed Description

template<class Arc>
class fst::SccVisitor< Arc >

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 96 of file connect.h.


Constructor & Destructor Documentation

template<class Arc>
fst::SccVisitor< Arc >::SccVisitor ( std::vector< StateId > *  scc,
std::vector< bool > *  access,
std::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, accessibility, coaccessibility) set/cleared (o.w. unchanged).

Definition at line 108 of file connect.h.

template<class Arc>
fst::SccVisitor< Arc >::SccVisitor ( uint64 *  props  )  [inline, explicit]

Definition at line 111 of file connect.h.


Member Function Documentation

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

Definition at line 120 of file connect.h.

template<class Arc >
void fst::SccVisitor< Arc >::FinishState ( StateId  state,
StateId  p,
const Arc *   
) [inline]

Last argument always ignored, but required by the interface.

Definition at line 227 of file connect.h.

template<class Arc>
void fst::SccVisitor< Arc >::FinishVisit (  )  [inline]

Definition at line 146 of file connect.h.

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

Definition at line 133 of file connect.h.

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

Definition at line 202 of file connect.h.

template<class Arc >
void fst::SccVisitor< Arc >::InitVisit ( const Fst< Arc > &  fst  )  [inline]

Definition at line 179 of file connect.h.

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

Definition at line 118 of file connect.h.


The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines