// See www.openfst.org for extensive documentation on this weighted
|
// finite-state transducer library.
|
//
|
// Depth-first search visitation. See visit.h for more general search queue
|
// disciplines.
|
|
#ifndef FST_DFS_VISIT_H_
|
#define FST_DFS_VISIT_H_
|
|
#include <stack>
|
#include <vector>
|
|
#include <fst/arcfilter.h>
|
#include <fst/fst.h>
|
|
|
namespace fst {
|
|
// Visitor Interface: class determining actions taken during a depth-first
|
// search-style visit. If any of the boolean member functions return false, the
|
// DFS is aborted by first calling FinishState() on all currently grey states
|
// and then calling FinishVisit().
|
//
|
// This is similar to the more general visitor interface in visit.h, except
|
// that FinishState returns additional information appropriate only for a DFS
|
// and some methods names here are better suited to a DFS.
|
//
|
// template <class Arc>
|
// class Visitor {
|
// public:
|
// using StateId = typename Arc::StateId;
|
//
|
// Visitor(T *return_data);
|
//
|
// // Invoked before DFS visit.
|
// void InitVisit(const Fst<Arc> &fst);
|
//
|
// // Invoked when state discovered (2nd arg is DFS tree root).
|
// bool InitState(StateId s, StateId root);
|
//
|
// // Invoked when tree arc to white/undiscovered state examined.
|
// bool TreeArc(StateId s, const Arc &arc);
|
//
|
// // Invoked when back arc to grey/unfinished state examined.
|
// bool BackArc(StateId s, const Arc &arc);
|
//
|
// // Invoked when forward or cross arc to black/finished state examined.
|
// bool ForwardOrCrossArc(StateId s, const Arc &arc);
|
//
|
// // Invoked when state finished ('s' is tree root, 'parent' is kNoStateId,
|
// // and 'arc' is nullptr).
|
// void FinishState(StateId s, StateId parent, const Arc *arc);
|
//
|
// // Invoked after DFS visit.
|
// void FinishVisit();
|
// };
|
|
namespace internal {
|
|
// An FST state's DFS stack state.
|
template <class FST>
|
struct DfsState {
|
using Arc = typename FST::Arc;
|
using StateId = typename Arc::StateId;
|
|
DfsState(const FST &fst, StateId s) : state_id(s), arc_iter(fst, s) {}
|
|
void *operator new(size_t size, MemoryPool<DfsState<FST>> *pool) {
|
return pool->Allocate();
|
}
|
|
static void Destroy(DfsState<FST> *dfs_state,
|
MemoryPool<DfsState<FST>> *pool) {
|
if (dfs_state) {
|
dfs_state->~DfsState<FST>();
|
pool->Free(dfs_state);
|
}
|
}
|
|
StateId state_id; // FST state.
|
ArcIterator<FST> arc_iter; // The corresponding arcs.
|
};
|
|
} // namespace internal
|
|
// Performs depth-first visitation. Visitor class argument determines actions
|
// and contains any return data. ArcFilter determines arcs that are considered.
|
// If 'access_only' is true, performs visitation only to states accessible from
|
// the initial state.
|
//
|
// Note this is similar to Visit() in visit.h called with a LIFO queue, except
|
// this version has a Visitor class specialized and augmented for a DFS.
|
template <class FST, class Visitor, class ArcFilter>
|
void DfsVisit(const FST &fst, Visitor *visitor, ArcFilter filter,
|
bool access_only = false) {
|
visitor->InitVisit(fst);
|
const auto start = fst.Start();
|
if (start == kNoStateId) {
|
visitor->FinishVisit();
|
return;
|
}
|
// An FST state's DFS status
|
static constexpr uint8 kDfsWhite = 0; // Undiscovered.
|
static constexpr uint8 kDfsGrey = 1; // Discovered but unfinished.
|
static constexpr uint8 kDfsBlack = 2; // Finished.
|
std::vector<uint8> state_color;
|
std::stack<internal::DfsState<FST> *> state_stack; // DFS execution stack.
|
MemoryPool<internal::DfsState<FST>> state_pool; // Pool for DFSStates.
|
auto nstates = start + 1; // Number of known states in general case.
|
bool expanded = false;
|
if (fst.Properties(kExpanded, false)) { // Tests if expanded case, then
|
nstates = CountStates(fst); // uses ExpandedFst::NumStates().
|
expanded = true;
|
}
|
state_color.resize(nstates, kDfsWhite);
|
StateIterator<FST> siter(fst);
|
// Continue DFS while true.
|
bool dfs = true;
|
// Iterate over trees in DFS forest.
|
for (auto root = start; dfs && root < nstates;) {
|
state_color[root] = kDfsGrey;
|
state_stack.push(new (&state_pool) internal::DfsState<FST>(fst, root));
|
dfs = visitor->InitState(root, root);
|
while (!state_stack.empty()) {
|
auto *dfs_state = state_stack.top();
|
const auto s = dfs_state->state_id;
|
if (s >= static_cast<typename FST::Arc::StateId>(state_color.size())) {
|
nstates = s + 1;
|
state_color.resize(nstates, kDfsWhite);
|
}
|
ArcIterator<FST> &aiter = dfs_state->arc_iter;
|
if (!dfs || aiter.Done()) {
|
state_color[s] = kDfsBlack;
|
internal::DfsState<FST>::Destroy(dfs_state, &state_pool);
|
state_stack.pop();
|
if (!state_stack.empty()) {
|
auto *parent_state = state_stack.top();
|
auto &piter = parent_state->arc_iter;
|
visitor->FinishState(s, parent_state->state_id, &piter.Value());
|
piter.Next();
|
} else {
|
visitor->FinishState(s, kNoStateId, nullptr);
|
}
|
continue;
|
}
|
const auto &arc = aiter.Value();
|
if (arc.nextstate >= state_color.size()) {
|
nstates = arc.nextstate + 1;
|
state_color.resize(nstates, kDfsWhite);
|
}
|
if (!filter(arc)) {
|
aiter.Next();
|
continue;
|
}
|
const auto next_color = state_color[arc.nextstate];
|
switch (next_color) {
|
default:
|
case kDfsWhite:
|
dfs = visitor->TreeArc(s, arc);
|
if (!dfs) break;
|
state_color[arc.nextstate] = kDfsGrey;
|
state_stack.push(new (&state_pool)
|
internal::DfsState<FST>(fst, arc.nextstate));
|
dfs = visitor->InitState(arc.nextstate, root);
|
break;
|
case kDfsGrey:
|
dfs = visitor->BackArc(s, arc);
|
aiter.Next();
|
break;
|
case kDfsBlack:
|
dfs = visitor->ForwardOrCrossArc(s, arc);
|
aiter.Next();
|
break;
|
}
|
}
|
if (access_only) break;
|
// Finds next tree root.
|
for (root = root == start ? 0 : root + 1;
|
root < nstates && state_color[root] != kDfsWhite; ++root) {
|
}
|
// Checks for a state beyond the largest known state.
|
if (!expanded && root == nstates) {
|
for (; !siter.Done(); siter.Next()) {
|
if (siter.Value() == nstates) {
|
++nstates;
|
state_color.push_back(kDfsWhite);
|
break;
|
}
|
}
|
}
|
}
|
visitor->FinishVisit();
|
}
|
|
template <class Arc, class Visitor>
|
void DfsVisit(const Fst<Arc> &fst, Visitor *visitor) {
|
DfsVisit(fst, visitor, AnyArcFilter<Arc>());
|
}
|
|
} // namespace fst
|
|
#endif // FST_DFS_VISIT_H_
|
