// connect.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
// Classes and functions to remove unsuccessful paths from an Fst.
#ifndef FST_LIB_CONNECT_H__
#define FST_LIB_CONNECT_H__
#include <vector>
using std::vector;
#include <fst/dfs-visit.h>
#include <fst/union-find.h>
#include <fst/mutable-fst.h>
namespace fst {
// Finds and returns connected components. Use with Visit().
template <class A>
class CcVisitor {
public:
typedef A Arc;
typedef typename Arc::Weight Weight;
typedef typename A::StateId StateId;
// cc[i]: connected component number for state i.
CcVisitor(vector<StateId> *cc)
: comps_(new UnionFind<StateId>(0, kNoStateId)),
cc_(cc),
nstates_(0) { }
// comps: connected components equiv classes.
CcVisitor(UnionFind<StateId> *comps)
: comps_(comps),
cc_(0),
nstates_(0) { }
~CcVisitor() {
if (cc_) // own comps_?
delete comps_;
}
void InitVisit(const Fst<A> &fst) { }
bool InitState(StateId s, StateId root) {
++nstates_;
if (comps_->FindSet(s) == kNoStateId)
comps_->MakeSet(s);
return true;
}
bool WhiteArc(StateId s, const A &arc) {
comps_->MakeSet(arc.nextstate);
comps_->Union(s, arc.nextstate);
return true;
}
bool GreyArc(StateId s, const A &arc) {
comps_->Union(s, arc.nextstate);
return true;
}
bool BlackArc(StateId s, const A &arc) {
comps_->Union(s, arc.nextstate);
return true;
}
void FinishState(StateId s) { }
void FinishVisit() {
if (cc_)
GetCcVector(cc_);
}
// cc[i]: connected component number for state i.
// Returns number of components.
int GetCcVector(vector<StateId> *cc) {
cc->clear();
cc->resize(nstates_, kNoStateId);
StateId ncomp = 0;
for (StateId i = 0; i < nstates_; ++i) {
StateId rep = comps_->FindSet(i);
StateId &comp = (*cc)[rep];
if (comp == kNoStateId) {
comp = ncomp;
++ncomp;
}
(*cc)[i] = comp;
}
return ncomp;
}
private:
UnionFind<StateId> *comps_; // Components
vector<StateId> *cc_; // State's cc number
StateId nstates_; // State count
};
// 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();
template <class A>
class SccVisitor {
public:
typedef A Arc;
typedef typename A::Weight Weight;
typedef typename A::StateId StateId;
// 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).
SccVisitor(vector<StateId> *scc, vector<bool> *access,
vector<bool> *coaccess, uint64 *props)
: scc_(scc), access_(access), coaccess_(coaccess), props_(props) {}
SccVisitor(uint64 *props)
: scc_(0), access_(0), coaccess_(0), props_(props) {}
void InitVisit(const Fst<A> &fst);
bool InitState(StateId s, StateId root);
bool TreeArc(StateId s, const A &arc) { return true; }
bool BackArc(StateId s, const A &arc) {
StateId t = arc.nextstate;
if ((*dfnumber_)[t] < (*lowlink_)[s])
(*lowlink_)[s] = (*dfnumber_)[t];
if ((*coaccess_)[t])
(*coaccess_)[s] = true;
*props_ |= kCyclic;
*props_ &= ~kAcyclic;
if (arc.nextstate == start_) {
*props_ |= kInitialCyclic;
*props_ &= ~kInitialAcyclic;
}
return true;
}
bool ForwardOrCrossArc(StateId s, const A &arc) {
StateId t = arc.nextstate;
if ((*dfnumber_)[t] < (*dfnumber_)[s] /* cross edge */ &&
(*onstack_)[t] && (*dfnumber_)[t] < (*lowlink_)[s])
(*lowlink_)[s] = (*dfnumber_)[t];
if ((*coaccess_)[t])
(*coaccess_)[s] = true;
return true;
}
void FinishState(StateId s, StateId p, const A *);
void FinishVisit() {
// Numbers SCC's in topological order when acyclic.
if (scc_)
for (StateId i = 0; i < scc_->size(); ++i)
(*scc_)[i] = nscc_ - 1 - (*scc_)[i];
if (coaccess_internal_)
delete coaccess_;
delete dfnumber_;
delete lowlink_;
delete onstack_;
delete scc_stack_;
}
private:
vector<StateId> *scc_; // State's scc number
vector<bool> *access_; // State's accessibility
vector<bool> *coaccess_; // State's coaccessibility
uint64 *props_;
const Fst<A> *fst_;
StateId start_;
StateId nstates_; // State count
StateId nscc_; // SCC count
bool coaccess_internal_;
vector<StateId> *dfnumber_; // state discovery times
vector<StateId> *lowlink_; // lowlink[s] == dfnumber[s] => SCC root
vector<bool> *onstack_; // is a state on the SCC stack
vector<StateId> *scc_stack_; // SCC stack (w/ random access)
};
template <class A> inline
void SccVisitor<A>::InitVisit(const Fst<A> &fst) {
if (scc_)
scc_->clear();
if (access_)
access_->clear();
if (coaccess_) {
coaccess_->clear();
coaccess_internal_ = false;
} else {
coaccess_ = new vector<bool>;
coaccess_internal_ = true;
}
*props_ |= kAcyclic | kInitialAcyclic | kAccessible | kCoAccessible;
*props_ &= ~(kCyclic | kInitialCyclic | kNotAccessible | kNotCoAccessible);
fst_ = &fst;
start_ = fst.Start();
nstates_ = 0;
nscc_ = 0;
dfnumber_ = new vector<StateId>;
lowlink_ = new vector<StateId>;
onstack_ = new vector<bool>;
scc_stack_ = new vector<StateId>;
}
template <class A> inline
bool SccVisitor<A>::InitState(StateId s, StateId root) {
scc_stack_->push_back(s);
while (dfnumber_->size() <= s) {
if (scc_)
scc_->push_back(-1);
if (access_)
access_->push_back(false);
coaccess_->push_back(false);
dfnumber_->push_back(-1);
lowlink_->push_back(-1);
onstack_->push_back(false);
}
(*dfnumber_)[s] = nstates_;
(*lowlink_)[s] = nstates_;
(*onstack_)[s] = true;
if (root == start_) {
if (access_)
(*access_)[s] = true;
} else {
if (access_)
(*access_)[s] = false;
*props_ |= kNotAccessible;
*props_ &= ~kAccessible;
}
++nstates_;
return true;
}
template <class A> inline
void SccVisitor<A>::FinishState(StateId s, StateId p, const A *) {
if (fst_->Final(s) != Weight::Zero())
(*coaccess_)[s] = true;
if ((*dfnumber_)[s] == (*lowlink_)[s]) { // root of new SCC
bool scc_coaccess = false;
size_t i = scc_stack_->size();
StateId t;
do {
t = (*scc_stack_)[--i];
if ((*coaccess_)[t])
scc_coaccess = true;
} while (s != t);
do {
t = scc_stack_->back();
if (scc_)
(*scc_)[t] = nscc_;
if (scc_coaccess)
(*coaccess_)[t] = true;
(*onstack_)[t] = false;
scc_stack_->pop_back();
} while (s != t);
if (!scc_coaccess) {
*props_ |= kNotCoAccessible;
*props_ &= ~kCoAccessible;
}
++nscc_;
}
if (p != kNoStateId) {
if ((*coaccess_)[s])
(*coaccess_)[p] = true;
if ((*lowlink_)[s] < (*lowlink_)[p])
(*lowlink_)[p] = (*lowlink_)[s];
}
}
// Trims an FST, removing states and arcs that are not on successful
// paths. This version modifies its input.
//
// Complexity:
// - Time: O(V + E)
// - Space: O(V + E)
// where V = # of states and E = # of arcs.
template<class Arc>
void Connect(MutableFst<Arc> *fst) {
typedef typename Arc::StateId StateId;
vector<bool> access;
vector<bool> coaccess;
uint64 props = 0;
SccVisitor<Arc> scc_visitor(0, &access, &coaccess, &props);
DfsVisit(*fst, &scc_visitor);
vector<StateId> dstates;
for (StateId s = 0; s < access.size(); ++s)
if (!access[s] || !coaccess[s])
dstates.push_back(s);
fst->DeleteStates(dstates);
fst->SetProperties(kAccessible | kCoAccessible, kAccessible | kCoAccessible);
}
} // namespace fst
#endif // FST_LIB_CONNECT_H__