dfs-visit.h revision 8fc5a7f51e62cb4ae44a27bdf4176d04adc80ede 
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
27namespace 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
58const int kDfsWhite = 0;   // Undiscovered
59const int kDfsGrey =  1;   // Discovered & unfinished
60const int kDfsBlack = 2;   // Finished
61
62// An Fst state's DFS stack state
63template <class Arc>
64struct 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.
76template <class Arc, class V, class ArcFilter>
77void 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
157template <class Arc, class V>
158void 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