// state-reachable.h
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Copyright 2005-2010 Google, Inc.
// Author: riley@google.com (Michael Riley)
//
// \file
// Class to determine whether a given (final) state can be reached from some
// other given state.
#ifndef FST_LIB_STATE_REACHABLE_H__
#define FST_LIB_STATE_REACHABLE_H__
#include <vector>
using std::vector;
#include <fst/dfs-visit.h>
#include <fst/fst.h>
#include <fst/interval-set.h>
namespace fst {
// Computes the (final) states reachable from a given state in an FST.
// After this visitor has been called, a final state f can be reached
// from a state s iff (*isets)[s].Member(state2index[f]) is true, where
// (*isets[s]) is a set of half-open inteval of final state indices
// and state2index[f] maps from a final state to its index.
//
// If state2index is empty, it is filled-in with suitable indices.
// If it is non-empty, those indices are used; in this case, the
// final states must have out-degree 0.
template <class A, typename I = typename A::StateId>
class IntervalReachVisitor {
public:
typedef typename A::StateId StateId;
typedef typename A::Label Label;
typedef typename A::Weight Weight;
typedef typename IntervalSet<I>::Interval Interval;
IntervalReachVisitor(const Fst<A> &fst,
vector< IntervalSet<I> > *isets,
vector<I> *state2index)
: fst_(fst),
isets_(isets),
state2index_(state2index),
index_(state2index->empty() ? 1 : -1),
error_(false) {
isets_->clear();
}
void InitVisit(const Fst<A> &fst) { error_ = false; }
bool InitState(StateId s, StateId r) {
while (isets_->size() <= s)
isets_->push_back(IntervalSet<Label>());
while (state2index_->size() <= s)
state2index_->push_back(-1);
if (fst_.Final(s) != Weight::Zero()) {
// Create tree interval
vector<Interval> *intervals = (*isets_)[s].Intervals();
if (index_ < 0) { // Use state2index_ map to set index
if (fst_.NumArcs(s) > 0) {
FSTERROR() << "IntervalReachVisitor: state2index map must be empty "
<< "for this FST";
error_ = true;
return false;
}
I index = (*state2index_)[s];
if (index < 0) {
FSTERROR() << "IntervalReachVisitor: state2index map incomplete";
error_ = true;
return false;
}
intervals->push_back(Interval(index, index + 1));
} else { // Use pre-order index
intervals->push_back(Interval(index_, index_ + 1));
(*state2index_)[s] = index_++;
}
}
return true;
}
bool TreeArc(StateId s, const A &arc) {
return true;
}
bool BackArc(StateId s, const A &arc) {
FSTERROR() << "IntervalReachVisitor: cyclic input";
error_ = true;
return false;
}
bool ForwardOrCrossArc(StateId s, const A &arc) {
// Non-tree interval
(*isets_)[s].Union((*isets_)[arc.nextstate]);
return true;
}
void FinishState(StateId s, StateId p, const A *arc) {
if (index_ >= 0 && fst_.Final(s) != Weight::Zero()) {
vector<Interval> *intervals = (*isets_)[s].Intervals();
(*intervals)[0].end = index_; // Update tree interval end
}
(*isets_)[s].Normalize();
if (p != kNoStateId)
(*isets_)[p].Union((*isets_)[s]); // Propagate intervals to parent
}
void FinishVisit() {}
bool Error() const { return error_; }
private:
const Fst<A> &fst_;
vector< IntervalSet<I> > *isets_;
vector<I> *state2index_;
I index_;
bool error_;
};
// Tests reachability of final states from a given state. To test for
// reachability from a state s, first do SetState(s). Then a final
// state f can be reached from state s of FST iff Reach(f) is true.
template <class A, typename I = typename A::StateId>
class StateReachable {
public:
typedef A Arc;
typedef I Index;
typedef typename A::StateId StateId;
typedef typename A::Label Label;
typedef typename A::Weight Weight;
typedef typename IntervalSet<I>::Interval Interval;
StateReachable(const Fst<A> &fst)
: error_(false) {
IntervalReachVisitor<Arc> reach_visitor(fst, &isets_, &state2index_);
DfsVisit(fst, &reach_visitor);
if (reach_visitor.Error()) error_ = true;
}
StateReachable(const StateReachable<A> &reachable) {
FSTERROR() << "Copy constructor for state reachable class "
<< "not yet implemented.";
error_ = true;
}
// Set current state.
void SetState(StateId s) { s_ = s; }
// Can reach this label from current state?
bool Reach(StateId s) {
if (s >= state2index_.size())
return false;
I i = state2index_[s];
if (i < 0) {
FSTERROR() << "StateReachable: state non-final: " << s;
error_ = true;
return false;
}
return isets_[s_].Member(i);
}
// Access to the state-to-index mapping. Unassigned states have index -1.
vector<I> &State2Index() { return state2index_; }
// Access to the interval sets. These specify the reachability
// to the final states as intervals of the final state indices.
const vector< IntervalSet<I> > &IntervalSets() { return isets_; }
bool Error() const { return error_; }
private:
StateId s_; // Current state
vector< IntervalSet<I> > isets_; // Interval sets per state
vector<I> state2index_; // Finds index for a final state
bool error_;
void operator=(const StateReachable<A> &); // Disallow
};
} // namespace fst
#endif // FST_LIB_STATE_REACHABLE_H__