Generated on for Gecode by doxygen 1.17.0
dfa.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.dev>
5 *
6 * Copyright:
7 * Christian Schulte, 2004
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <gecode/int.hh>
35
36#include <algorithm>
37#include <vector>
38
39namespace Gecode { namespace Int { namespace Extensional {
40
45 public:
46 forceinline bool
48 return x.i_state < y.i_state;
49 }
50 forceinline static void
55 };
56
61 public:
62 forceinline bool
64 return x.symbol < y.symbol;
65 }
66 forceinline static void
71 };
72
77 public:
78 forceinline bool
80 return ((x.symbol < y.symbol) ||
81 ((x.symbol == y.symbol) && (x.i_state < y.i_state)));
82 }
83 forceinline static void
88 };
89
94 public:
95 forceinline bool
97 return x.o_state < y.o_state;
98 }
99 forceinline static void
104 };
105
106
111 public:
112 int state;
113 int group;
114 };
115
120 public:
121 forceinline bool
122 operator ()(const StateGroup& x, const StateGroup& y) {
123 return ((x.group < y.group) ||
124 ((x.group == y.group) && (x.state < y.state)));
125 }
126 static void
131 };
132
137 public:
140 };
141
143 forceinline int
144 state_index(const std::vector<int>& states, int state) {
145 return static_cast<int>(
146 std::lower_bound(states.begin(),states.end(),state)-states.begin());
147 }
148
156
157}}}
158
159namespace Gecode {
160
161 void
162 DFA::init(int start, Transition t_spec[], int f_spec[], bool minimize) {
163 using namespace Int;
164 using namespace Extensional;
165 Region region;
166
167 int n_trans = 0;
168 int max_state = start;
169 for (Transition* t = &t_spec[0]; t->i_state >= 0; t++) {
170 max_state = std::max(max_state,t->i_state);
171 max_state = std::max(max_state,t->o_state);
172 n_trans++;
173 }
174 std::size_t n_final_spec = 0;
175 for (int* f = &f_spec[0]; *f >= 0; f++) {
176 max_state = std::max(max_state,*f);
177 n_final_spec++;
178 }
179 // Use identifiers directly when the state range is bounded by the input
180 // size: transitions, final entries, and the start state.
181 const bool compact = static_cast<std::size_t>(max_state) >=
182 static_cast<std::size_t>(n_trans)+n_final_spec+1;
183 std::vector<int> states;
184 int n_states;
185 if (compact) {
186 states.reserve(2*static_cast<std::size_t>(n_trans)+n_final_spec+1);
187 states.push_back(start);
188 for (Transition* t = &t_spec[0]; t->i_state >= 0; t++) {
189 states.push_back(t->i_state);
190 states.push_back(t->o_state);
191 }
192 for (int* f = &f_spec[0]; *f >= 0; f++)
193 states.push_back(*f);
194 std::sort(states.begin(),states.end());
195 states.erase(std::unique(states.begin(),states.end()),states.end());
196 n_states = static_cast<int>(states.size());
197 start = state_index(states,start);
198 } else {
199 n_states = max_state+1;
200 }
201
202 // Temporary structure for transitions
203 Transition* trans = region.alloc<Transition>(n_trans);
204 if (compact) {
205 for (int i=0; i<n_trans; i++) {
206 trans[i] = t_spec[i];
207 trans[i].i_state = state_index(states,trans[i].i_state);
208 trans[i].o_state = state_index(states,trans[i].o_state);
209 }
210 } else {
211 for (int i=0; i<n_trans; i++)
212 trans[i] = t_spec[i];
213 }
214 // Temporary structures for finals
215 int* final = region.alloc<int>(n_states+1);
216 bool* is_final = region.alloc<bool>(n_states+1);
217 int n_finals = 0;
218 for (int i=0; i<n_states+1; i++)
219 is_final[i] = false;
220 for (int* f = &f_spec[0]; *f != -1; f++) {
221 const int state = compact ? state_index(states,*f) : *f;
222 if (!is_final[state]) {
223 is_final[state] = true;
224 final[n_finals++] = state;
225 }
226 }
227
228 if (minimize) {
229 // Sort transitions by symbol and i_state
230 TransBySymbolI_State::sort(trans, n_trans);
231 Transition** idx = region.alloc<Transition*>(n_trans+1);
232 // idx[i]...idx[i+1]-1 gives where transitions for symbol i start
233 int n_symbols = 0;
234 {
235 int j = 0;
236 while (j < n_trans) {
237 idx[n_symbols++] = &trans[j];
238 int s = trans[j].symbol;
239 while ((j < n_trans) && (s == trans[j].symbol))
240 j++;
241 }
242 idx[n_symbols] = &trans[j];
243 assert(j == n_trans);
244 }
245 // Map states to groups
246 int* s2g = region.alloc<int>(n_states+1);
247 StateGroup* part = region.alloc<StateGroup>(n_states+1);
248 GroupStates* g2s = region.alloc<GroupStates>(n_states+1);
249 // Initialize: final states is group one, all other group zero
250 for (int i=0; i<n_states+1; i++) {
251 part[i].state = i;
252 part[i].group = is_final[i] ? 1 : 0;
253 s2g[i] = part[i].group;
254 }
255 // Important: the state n_state is the dead state, conceptually
256 // if there is no transition for a symbol and input state, it is
257 // assumed that there is an implicit transition to n_state
258
259 // Set up the indexing data structure, sort by group
260 StateGroupByGroup::sort(part,n_states+1);
261 int n_groups;
262 if (part[0].group == part[n_states].group) {
263 // No final states, just one group
264 g2s[0].fst = &part[0]; g2s[0].lst = &part[n_states+1];
265 n_groups = 1;
266 } else {
267 int i = 0;
268 assert(part[0].group == 0);
269 do i++; while (part[i].group == 0);
270 g2s[0].fst = &part[0]; g2s[0].lst = &part[i];
271 g2s[1].fst = &part[i]; g2s[1].lst = &part[n_states+1];
272 n_groups = 2;
273 }
274
275 // Do the refinement
276 {
277 int m_groups;
278 do {
279 m_groups = n_groups;
280 // Iterate over symbols
281 for (int sidx = n_symbols; sidx--; ) {
282 // Iterate over groups
283 for (int g = n_groups; g--; ) {
284 // Ignore singleton groups
285 if (g2s[g].lst-g2s[g].fst > 1) {
286 // Apply transitions to group states
287 // This exploits that both transitions as well as
288 // stategroups are sorted by (input) state
289 Transition* t = idx[sidx];
290 Transition* t_lst = idx[sidx+1];
291 for (StateGroup* sg = g2s[g].fst; sg<g2s[g].lst; sg++) {
292 while ((t < t_lst) && (t->i_state < sg->state))
293 t++;
294 // Compute group resulting from transition
295 if ((t < t_lst) && (t->i_state == sg->state))
296 sg->group = s2g[t->o_state];
297 else
298 sg->group = s2g[n_states]; // Go to dead state
299 }
300 // Sort group by groups from transitions
301 StateGroupByGroup::sort(g2s[g].fst,
302 static_cast<int>(g2s[g].lst-g2s[g].fst));
303 // Group must be split?
304 if (g2s[g].fst->group != (g2s[g].lst-1)->group) {
305 // Skip first group
306 StateGroup* sg = g2s[g].fst+1;
307 while ((sg-1)->group == sg->group)
308 sg++;
309 // Start splitting
310 StateGroup* lst = g2s[g].lst;
311 g2s[g].lst = sg;
312 while (sg < lst) {
313 s2g[sg->state] = n_groups;
314 g2s[n_groups].fst = sg++;
315 while ((sg < lst) && ((sg-1)->group == sg->group)) {
316 s2g[sg->state] = n_groups; sg++;
317 }
318 g2s[n_groups++].lst = sg;
319 }
320 }
321 }
322 }
323 }
324 } while (n_groups != m_groups);
325 // New start state
326 start = s2g[start];
327 // Compute new final states
328 n_finals = 0;
329 for (int g = n_groups; g--; )
330 for (StateGroup* sg = g2s[g].fst; sg < g2s[g].lst; sg++)
331 if (is_final[sg->state]) {
332 final[n_finals++] = g;
333 break;
334 }
335 // Compute representatives
336 int* s2r = region.alloc<int>(n_states+1);
337 for (int i=0; i<n_states+1; i++)
338 s2r[i] = -1;
339 for (int g=0; g<n_groups; g++)
340 s2r[g2s[g].fst->state] = g;
341 // Clean transitions
342 int j = 0;
343 for (int i = 0; i<n_trans; i++)
344 if (s2r[trans[i].i_state] != -1) {
345 trans[j].i_state = s2g[trans[i].i_state];
346 trans[j].symbol = trans[i].symbol;
347 trans[j].o_state = s2g[trans[i].o_state];
348 j++;
349 }
350 n_trans = j;
351 n_states = n_groups;
352 }
353 }
354
355 // Do a reachability analysis for all states starting from start state
357 int* state = region.alloc<int>(n_states);
358 for (int i=0; i<n_states; i++)
359 state[i] = SI_NONE;
360
361 Transition** idx = region.alloc<Transition*>(n_states+1);
362 {
363 // Sort all transitions according to i_state and create index structure
364 // idx[i]...idx[i+1]-1 gives where transitions for state i start
365 TransByI_State::sort(trans, n_trans);
366 {
367 int j = 0;
368 for (int i=0; i<n_states; i++) {
369 idx[i] = &trans[j];
370 while ((j < n_trans) && (i == trans[j].i_state))
371 j++;
372 }
373 idx[n_states] = &trans[j];
374 assert(j == n_trans);
375 }
376
377 state[start] = SI_FROM_START;
378 visit.push(start);
379 while (!visit.empty()) {
380 int s = visit.pop();
381 for (Transition* t = idx[s]; t < idx[s+1]; t++)
382 if (!(state[t->o_state] & SI_FROM_START)) {
383 state[t->o_state] |= SI_FROM_START;
384 visit.push(t->o_state);
385 }
386 }
387 }
388
389 // Do a reachability analysis for all states to a final state
390 {
391 // Sort all transitions according to o_state and create index structure
392 // idx[i]...idx[i+1]-1 gives where transitions for state i start
393 TransByO_State::sort(trans, n_trans);
394 {
395 int j = 0;
396 for (int i=0; i<n_states; i++) {
397 idx[i] = &trans[j];
398 while ((j < n_trans) && (i == trans[j].o_state))
399 j++;
400 }
401 idx[n_states] = &trans[j];
402 assert(j == n_trans);
403 }
404
405 for (int i=0; i<n_finals; i++) {
406 state[final[i]] |= (SI_TO_FINAL | SI_FINAL);
407 visit.push(final[i]);
408 }
409 while (!visit.empty()) {
410 int s = visit.pop();
411 for (Transition* t = idx[s]; t < idx[s+1]; t++)
412 if (!(state[t->i_state] & SI_TO_FINAL)) {
413 state[t->i_state] |= SI_TO_FINAL;
414 visit.push(t->i_state);
415 }
416 }
417 }
418
419 // Now all reachable states are known (also the final ones)
420 int* re = region.alloc<int>(n_states);
421 for (int i=0; i<n_states; i++)
422 re[i] = -1;
423
424 // Renumber states
425 int m_states = 0;
426 // Start state gets zero
427 re[start] = m_states++;
428
429 // Renumber final states
430 for (int i=n_states; i--; )
431 if ((state[i] == (SI_FINAL | SI_FROM_START | SI_TO_FINAL)) && (re[i] < 0))
432 re[i] = m_states++;
433 // If start state is final, final states start from zero, otherwise from one
434 int final_fst = (state[start] & SI_FINAL) ? 0 : 1;
435 int final_lst = m_states;
436 // final_fst...final_lst-1 are the final states
437
438 // Renumber remaining states
439 for (int i=n_states; i--; )
440 if ((state[i] == (SI_FROM_START | SI_TO_FINAL)) && (re[i] < 0))
441 re[i] = m_states++;
442
443 // Count number of remaining transitions
444 int m_trans = 0;
445 for (int i=n_trans; i--; )
446 if ((re[trans[i].i_state] >= 0) && (re[trans[i].o_state] >= 0))
447 m_trans++;
448
449 // All done... Construct the automaton
450 DFAI* d = new DFAI(m_trans);
451 d->n_states = m_states;
452 d->n_trans = m_trans;
453 d->final_fst = final_fst;
454 d->final_lst = final_lst;
455 {
456 int j = 0;
457 Transition* r = &d->trans[0];
458 for (int i = 0; i<n_trans; i++)
459 if ((re[trans[i].i_state] >= 0) && (re[trans[i].o_state] >= 0)) {
460 r[j].symbol = trans[i].symbol;
461 r[j].i_state = re[trans[i].i_state];
462 r[j].o_state = re[trans[i].o_state];
463 j++;
464 }
465 TransBySymbol::sort(r,m_trans);
466 }
467 {
468 // Count number of symbols
469 unsigned int n_symbols = 0;
470 for (int i = 0; i<m_trans; ) {
471 int s = d->trans[i++].symbol;
472 n_symbols++;
473 while ((i<m_trans) && (d->trans[i].symbol == s))
474 i++;
475 }
476 d->n_symbols = n_symbols;
477 }
478 {
479 // Compute maximal degree
480 unsigned int max_degree = 0;
481 unsigned int* deg = region.alloc<unsigned int>(m_states);
482
483 // Compute in-degree per state
484 for (int i=0; i<m_states; i++)
485 deg[i] = 0;
486 for (int i=0; i<m_trans; i++)
487 deg[d->trans[i].o_state]++;
488 for (int i=0; i<m_states; i++)
489 max_degree = std::max(max_degree,deg[i]);
490
491 // Compute out-degree per state
492 for (int i=0; i<m_states; i++)
493 deg[i] = 0;
494 for (int i=0; i<m_trans; i++)
495 deg[d->trans[i].i_state]++;
496 for (int i=0; i<m_states; i++)
497 max_degree = std::max(max_degree,deg[i]);
498
499 // Compute transitions per symbol
500 {
501 int i=0;
502 while (i < m_trans) {
503 int j=i++;
504 while ((i < m_trans) &&
505 (d->trans[j].symbol == d->trans[i].symbol))
506 i++;
507 max_degree = std::max(max_degree,static_cast<unsigned int>(i-j));
508 }
509 }
510
511 d->max_degree = max_degree;
512 }
513
514 d->fill();
515 object(d);
516 }
517
518 DFA::DFA(int start, Transition t_spec[], int f_spec[], bool minimize) {
519 init(start,t_spec,f_spec,minimize);
520 }
521
522 DFA::DFA(int start, std::initializer_list<Transition> tl,
523 std::initializer_list<int> fl, bool minimize) {
524 Region reg;
525 int nt = static_cast<int>(tl.size());
526 int nf = static_cast<int>(fl.size());
527 Transition* ts = reg.alloc<Transition>(nt + 1);
528 {
529 int i=0;
530 for (const Transition& t : tl)
531 ts[i++] = t;
532 ts[nt].i_state = -1;
533 }
534 int* fs = reg.alloc<int>(nf + 1);
535 {
536 int i=0;
537 for (const int& f : fl)
538 fs[i++] = f;
539 fs[nf] = -1;
540 }
541 init(start,ts,fs,minimize);
542 }
543
544 DFA
545 DFA::nfa(int start, Transition t[], int f[]) {
546 return DFA(start,t,f,false);
547 }
548
549 DFA
550 DFA::nfa(int start, std::initializer_list<Transition> t,
551 std::initializer_list<int> f) {
552 return DFA(start,t,f,false);
553 }
554
555 bool
556 DFA::equal(const DFA& d) const {
557 assert(n_states() == d.n_states());
558 assert(n_transitions() == d.n_transitions());
559 assert(n_symbols() == d.n_symbols());
560 assert(final_fst() == d.final_fst());
561 assert(final_lst() == d.final_lst());
562 DFA::Transitions me(*this);
563 DFA::Transitions they(d);
564 while (me()) {
565 if (me.i_state() != they.i_state())
566 return false;
567 if (me.symbol() != they.symbol())
568 return false;
569 if (me.o_state() != they.o_state())
570 return false;
571 ++me;
572 ++they;
573 }
574 return true;
575 }
576
577}
578
579// STATISTICS: int-prop
580
Data stored for a DFA.
Definition dfa.hpp:42
Specification of a DFA transition.
Definition int.hh:2629
int i_state
input state
Definition int.hh:2631
int o_state
output state Default constructor
Definition int.hh:2633
Iterator for DFA transitions (sorted by symbols).
Definition int.hh:2640
Finite automaton with deterministic construction by default.
Definition int.hh:2620
unsigned int max_degree(void) const
Return maximal degree (in-degree and out-degree) of any state.
Definition dfa.hpp:157
int n_states(void) const
Return the number of states.
Definition dfa.hpp:139
DFA(void)
Initialize for DFA accepting the empty word.
Definition dfa.hpp:131
int final_lst(void) const
Return the number of the last final state.
Definition dfa.hpp:169
int n_transitions(void) const
Return the number of transitions.
Definition dfa.hpp:151
unsigned int n_symbols(void) const
Return the number of symbols.
Definition dfa.hpp:145
void init(int s, Transition t[], int f[], bool minimize=true)
Initialize DFA.
Definition dfa.cpp:162
int final_fst(void) const
Return the number of the first final state.
Definition dfa.hpp:163
static DFA nfa(int s, Transition t[], int f[])
Construct a nondeterministic finite automaton.
Definition dfa.cpp:545
GroupStates is used to index StateGroup by group
Definition dfa.cpp:136
Sort groups stated by group and then state.
Definition dfa.cpp:119
bool operator()(const StateGroup &x, const StateGroup &y)
Definition dfa.cpp:122
static void sort(StateGroup sg[], int n)
Definition dfa.cpp:127
Stategroup is used to compute a partition of states.
Definition dfa.cpp:110
Sort transition array by input state.
Definition dfa.cpp:44
bool operator()(const DFA::Transition &x, const DFA::Transition &y)
Definition dfa.cpp:47
static void sort(DFA::Transition t[], int n)
Definition dfa.cpp:51
Sort transition array by output state.
Definition dfa.cpp:93
static void sort(DFA::Transition t[], int n)
Definition dfa.cpp:100
bool operator()(const DFA::Transition &x, const DFA::Transition &y)
Definition dfa.cpp:96
Sort transition array by symbol and then input states.
Definition dfa.cpp:76
static void sort(DFA::Transition t[], int n)
Definition dfa.cpp:84
bool operator()(const DFA::Transition &x, const DFA::Transition &y)
Definition dfa.cpp:79
Sort transition array by symbol (value).
Definition dfa.cpp:60
static void sort(DFA::Transition t[], int n)
Definition dfa.cpp:67
bool operator()(const DFA::Transition &x, const DFA::Transition &y)
Definition dfa.cpp:63
Handle to region.
Definition region.hpp:55
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition region.hpp:386
SharedHandle::Object * object(void) const
Access to the shared object.
Stack with fixed number of elements.
void push(const T &x)
Push element x on top of stack.
T pop(void)
Pop topmost element from stack and return it.
bool empty(void) const
Test whether stack is empty.
Extensional propagators
Definition int.hh:2774
StateInfo
Information about states.
Definition dfa.cpp:150
@ SI_FINAL
State is final.
Definition dfa.cpp:154
@ SI_NONE
State is not reachable.
Definition dfa.cpp:151
@ SI_FROM_START
State is reachable from start state.
Definition dfa.cpp:152
@ SI_TO_FINAL
Final state is reachable from state.
Definition dfa.cpp:153
int state_index(const std::vector< int > &states, int state)
Return the compact index for an external state identifier.
Definition dfa.cpp:144
Finite domain integers.
Definition lastval.hh:52
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode toplevel namespace
#define forceinline
Definition config.hpp:144