Home | History | Annotate | Download | only in lib 
      1 // dfs-visit.h
      2 //
      3 // Licensed under the Apache License, Version 2.0 (the "License");
      4 // you may not use this file except in compliance with the License.
      5 // You may obtain a copy of the License at
      6 //
      7 //      http://www.apache.org/licenses/LICENSE-2.0
      8 //
      9 // Unless required by applicable law or agreed to in writing, software
     10 // distributed under the License is distributed on an "AS IS" BASIS,
     11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     12 // See the License for the specific language governing permissions and
     13 // limitations under the License.
     14 //
     15 //
     16 // \file
     17 // Depth-first search visitation
     18 
     19 #ifndef FST_LIB_DFS_VISIT_H__
     20 #define FST_LIB_DFS_VISIT_H__
     21 
     22 #include <stack>
     23 
     24 #include "fst/lib/arcfilter.h"
     25 #include "fst/lib/expanded-fst.h"
     26 
     27 namespace fst {
     28 
     29 // Visitor Interface - class determines actions taken during a Dfs.
     30 // If any of the boolean member functions return false, the DFS is
     31 // aborted by first calling FinishState() on all currently grey states
     32 // and then calling FinishVisit().
     33 //
     34 // template <class Arc>
     35 // class Visitor {
     36 //  public:
     37 //   typedef typename Arc::StateId StateId;
     38 //
     39 //   Visitor(T *return_data);
     40 //   // Invoked before DFS visit
     41 //   void InitVisit(const Fst<Arc> &fst);
     42 //   // Invoked when state discovered (2nd arg is DFS tree root)
     43 //   bool InitState(StateId s, StateId root);
     44 //   // Invoked when tree arc examined (to white/undiscovered state)
     45 //   bool TreeArc(StateId s, const Arc &a);
     46 //   // Invoked when back arc examined (to grey/unfinished state)
     47 //   bool BackArc(StateId s, const Arc &a);
     48 //   // Invoked when forward or cross arc examined (to black/finished state)
     49 //   bool ForwardOrCrossArc(StateId s, const Arc &a);
     50 //   // Invoked when state finished (PARENT is kNoStateID and ARC == NULL
     51 //   // when S is tree root)
     52 //   void FinishState(StateId s, StateId parent, const Arc *parent_arc);
     53 //   // Invoked after DFS visit
     54 //   void FinishVisit();
     55 // };
     56 
     57 // An Fst state's DFS status
     58 const int kDfsWhite = 0;   // Undiscovered
     59 const int kDfsGrey =  1;   // Discovered & unfinished
     60 const int kDfsBlack = 2;   // Finished
     61 
     62 // An Fst state's DFS stack state
     63 template <class Arc>
     64 struct DfsState {
     65   typedef typename Arc::StateId StateId;
     66 
     67   DfsState(const Fst<Arc> &fst, StateId s): state_id(s), arc_iter(fst, s) {}
     68 
     69   StateId state_id;       // Fst state ...
     70   ArcIterator< Fst<Arc> > arc_iter;  // and its corresponding arcs
     71 };
     72 
     73 
     74 // Performs depth-first visitation. Visitor class argument determines actions
     75 // and contains any return data. ArcFilter determines arcs that are considered.
     76 template <class Arc, class V, class ArcFilter>
     77 void DfsVisit(const Fst<Arc> &fst, V *visitor, ArcFilter filter) {
     78   typedef typename Arc::StateId StateId;
     79 
     80   visitor->InitVisit(fst);
     81 
     82   StateId start = fst.Start();
     83   if (start == kNoStateId) {
     84     visitor->FinishVisit();
     85     return;
     86   }
     87 
     88   vector<char> state_color;            // Fst state DFS status
     89   stack<DfsState<Arc> *> state_stack;  // DFS execution stack
     90 
     91   StateId nstates = CountStates(fst);
     92 
     93   while ((StateId)state_color.size() < nstates)
     94     state_color.push_back(kDfsWhite);
     95 
     96   // Continue DFS while true
     97   bool dfs = true;
     98 
     99   // Iterate over trees in DFS forest.
    100   for (StateId root = start; dfs && root < nstates;) {
    101     state_color[root] = kDfsGrey;
    102     state_stack.push(new DfsState<Arc>(fst, root));
    103     dfs = visitor->InitState(root, root);
    104     while (!state_stack.empty()) {
    105       DfsState<Arc> *dfs_state = state_stack.top();
    106       StateId s = dfs_state->state_id;
    107       ArcIterator< Fst<Arc> > &aiter = dfs_state->arc_iter;
    108       if (!dfs || aiter.Done()) {
    109         state_color[s] = kDfsBlack;
    110         delete dfs_state;
    111         state_stack.pop();
    112         if (!state_stack.empty()) {
    113           DfsState<Arc> *parent_state = state_stack.top();
    114           StateId p = parent_state->state_id;
    115           ArcIterator< Fst<Arc> > &piter = parent_state->arc_iter;
    116           visitor->FinishState(s, p, &piter.Value());
    117           piter.Next();
    118         } else {
    119           visitor->FinishState(s, kNoStateId, 0);
    120         }
    121         continue;
    122       }
    123       const Arc &arc = aiter.Value();
    124       if (!filter(arc)) {
    125         aiter.Next();
    126         continue;
    127       }
    128       int next_color = state_color[arc.nextstate];
    129       switch (next_color) {
    130         default:
    131         case kDfsWhite:
    132           dfs = visitor->TreeArc(s, arc);
    133           if (!dfs) break;
    134           state_color[arc.nextstate] = kDfsGrey;
    135           state_stack.push(new DfsState<Arc>(fst, arc.nextstate));
    136           dfs = visitor->InitState(arc.nextstate, root);
    137           break;
    138         case kDfsGrey:
    139           dfs = visitor->BackArc(s, arc);
    140           aiter.Next();
    141           break;
    142         case kDfsBlack:
    143           dfs = visitor->ForwardOrCrossArc(s, arc);
    144           aiter.Next();
    145           break;
    146       }
    147     }
    148     // Find next tree root
    149     for (root = root == start ? 0 : root + 1;
    150          root < nstates && state_color[root] != kDfsWhite;
    151          ++root);
    152   }
    153   visitor->FinishVisit();
    154 }
    155 
    156 
    157 template <class Arc, class V>
    158 void DfsVisit(const Fst<Arc> &fst, V *visitor) {
    159   DfsVisit(fst, visitor, AnyArcFilter<Arc>());
    160 }
    161 
    162 }  // namespace fst
    163 
    164 #endif  // FST_LIB_DFS_VISIT_H__
    165