dfa.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Christian Schulte, 2004
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include <gecode/int.hh>
namespace Gecode { namespace Int { namespace Extensional {
class TransByI_State {
public:
forceinline bool
operator ()(const DFA::Transition& x, const DFA::Transition& y) {
return x.i_state < y.i_state;
}
forceinline static void
sort(DFA::Transition t[], int n) {
TransByI_State tbis;
Support::quicksort<DFA::Transition,TransByI_State>(t,n,tbis);
}
};
class TransBySymbol {
public:
forceinline bool
operator ()(const DFA::Transition& x, const DFA::Transition& y) {
return x.symbol < y.symbol;
}
forceinline static void
sort(DFA::Transition t[], int n) {
TransBySymbol tbs;
Support::quicksort<DFA::Transition,TransBySymbol>(t,n,tbs);
}
};
class TransBySymbolI_State {
public:
forceinline bool
operator ()(const DFA::Transition& x, const DFA::Transition& y) {
return ((x.symbol < y.symbol) ||
((x.symbol == y.symbol) && (x.i_state < y.i_state)));
}
forceinline static void
sort(DFA::Transition t[], int n) {
TransBySymbolI_State tbsi;
Support::quicksort<DFA::Transition,TransBySymbolI_State>(t,n,tbsi);
}
};
class TransByO_State {
public:
forceinline bool
operator ()(const DFA::Transition& x, const DFA::Transition& y) {
return x.o_state < y.o_state;
}
forceinline static void
sort(DFA::Transition t[], int n) {
TransByO_State tbos;
Support::quicksort<DFA::Transition,TransByO_State>(t,n,tbos);
}
};
class StateGroup {
public:
int state;
int group;
};
class StateGroupByGroup {
public:
forceinline bool
operator ()(const StateGroup& x, const StateGroup& y) {
return ((x.group < y.group) ||
((x.group == y.group) && (x.state < y.state)));
}
static void
sort(StateGroup sg[], int n) {
StateGroupByGroup o;
Support::quicksort<StateGroup,StateGroupByGroup>(sg,n,o);
}
};
class GroupStates {
public:
StateGroup* fst;
StateGroup* lst;
};
enum StateInfo {
SI_NONE = 0,
SI_FROM_START = 1,
SI_TO_FINAL = 2,
SI_FINAL = 4
};
}}}
namespace Gecode {
void
DFA::init(int start, Transition t_spec[], int f_spec[], bool minimize) {
using namespace Int;
using namespace Extensional;
Region region;
// Compute number of states and transitions
int n_states = start;
int n_trans = 0;
for (Transition* t = &t_spec[0]; t->i_state >= 0; t++) {
n_states = std::max(n_states,t->i_state);
n_states = std::max(n_states,t->o_state);
n_trans++;
}
for (int* f = &f_spec[0]; *f >= 0; f++)
n_states = std::max(n_states,*f);
n_states++;
// Temporary structure for transitions
Transition* trans = region.alloc<Transition>(n_trans);
for (int i=0; i<n_trans; i++)
trans[i] = t_spec[i];
// Temporary structures for finals
int* final = region.alloc<int>(n_states+1);
bool* is_final = region.alloc<bool>(n_states+1);
int n_finals = 0;
for (int i=0; i<n_states+1; i++)
is_final[i] = false;
for (int* f = &f_spec[0]; *f != -1; f++) {
is_final[*f] = true;
final[n_finals++] = *f;
}
if (minimize) {
// Sort transitions by symbol and i_state
TransBySymbolI_State::sort(trans, n_trans);
Transition** idx = region.alloc<Transition*>(n_trans+1);
// idx[i]...idx[i+1]-1 gives where transitions for symbol i start
int n_symbols = 0;
{
int j = 0;
while (j < n_trans) {
idx[n_symbols++] = &trans[j];
int s = trans[j].symbol;
while ((j < n_trans) && (s == trans[j].symbol))
j++;
}
idx[n_symbols] = &trans[j];
assert(j == n_trans);
}
// Map states to groups
int* s2g = region.alloc<int>(n_states+1);
StateGroup* part = region.alloc<StateGroup>(n_states+1);
GroupStates* g2s = region.alloc<GroupStates>(n_states+1);
// Initialize: final states is group one, all other group zero
for (int i=0; i<n_states+1; i++) {
part[i].state = i;
part[i].group = is_final[i] ? 1 : 0;
s2g[i] = part[i].group;
}
// Important: the state n_state is the dead state, conceptually
// if there is no transition for a symbol and input state, it is
// assumed that there is an implicit transition to n_state
// Set up the indexing data structure, sort by group
StateGroupByGroup::sort(part,n_states+1);
int n_groups;
if (part[0].group == part[n_states].group) {
// No final states, just one group
g2s[0].fst = &part[0]; g2s[0].lst = &part[n_states+1];
n_groups = 1;
} else {
int i = 0;
assert(part[0].group == 0);
do i++; while (part[i].group == 0);
g2s[0].fst = &part[0]; g2s[0].lst = &part[i];
g2s[1].fst = &part[i]; g2s[1].lst = &part[n_states+1];
n_groups = 2;
}
// Do the refinement
{
int m_groups;
do {
m_groups = n_groups;
// Iterate over symbols
for (int sidx = n_symbols; sidx--; ) {
// Iterate over groups
for (int g = n_groups; g--; ) {
// Ignore singleton groups
if (g2s[g].lst-g2s[g].fst > 1) {
// Apply transitions to group states
// This exploits that both transitions as well as
// stategroups are sorted by (input) state
Transition* t = idx[sidx];
Transition* t_lst = idx[sidx+1];
for (StateGroup* sg = g2s[g].fst; sg<g2s[g].lst; sg++) {
while ((t < t_lst) && (t->i_state < sg->state))
t++;
// Compute group resulting from transition
if ((t < t_lst) && (t->i_state == sg->state))
sg->group = s2g[t->o_state];
else
sg->group = s2g[n_states]; // Go to dead state
}
// Sort group by groups from transitions
StateGroupByGroup::sort(g2s[g].fst,
static_cast<int>(g2s[g].lst-g2s[g].fst));
// Group must be split?
if (g2s[g].fst->group != (g2s[g].lst-1)->group) {
// Skip first group
StateGroup* sg = g2s[g].fst+1;
while ((sg-1)->group == sg->group)
sg++;
// Start splitting
StateGroup* lst = g2s[g].lst;
g2s[g].lst = sg;
while (sg < lst) {
s2g[sg->state] = n_groups;
g2s[n_groups].fst = sg++;
while ((sg < lst) && ((sg-1)->group == sg->group)) {
s2g[sg->state] = n_groups; sg++;
}
g2s[n_groups++].lst = sg;
}
}
}
}
}
} while (n_groups != m_groups);
// New start state
start = s2g[start];
// Compute new final states
n_finals = 0;
for (int g = n_groups; g--; )
for (StateGroup* sg = g2s[g].fst; sg < g2s[g].lst; sg++)
if (is_final[sg->state]) {
final[n_finals++] = g;
break;
}
// Compute representatives
int* s2r = region.alloc<int>(n_states+1);
for (int i=0; i<n_states+1; i++)
s2r[i] = -1;
for (int g=0; g<n_groups; g++)
s2r[g2s[g].fst->state] = g;
// Clean transitions
int j = 0;
for (int i = 0; i<n_trans; i++)
if (s2r[trans[i].i_state] != -1) {
trans[j].i_state = s2g[trans[i].i_state];
trans[j].symbol = trans[i].symbol;
trans[j].o_state = s2g[trans[i].o_state];
j++;
}
n_trans = j;
n_states = n_groups;
}
}
// Do a reachability analysis for all states starting from start state
Gecode::Support::StaticStack<int,Region> visit(region,n_states);
int* state = region.alloc<int>(n_states);
for (int i=0; i<n_states; i++)
state[i] = SI_NONE;
Transition** idx = region.alloc<Transition*>(n_states+1);
{
// Sort all transitions according to i_state and create index structure
// idx[i]...idx[i+1]-1 gives where transitions for state i start
TransByI_State::sort(trans, n_trans);
{
int j = 0;
for (int i=0; i<n_states; i++) {
idx[i] = &trans[j];
while ((j < n_trans) && (i == trans[j].i_state))
j++;
}
idx[n_states] = &trans[j];
assert(j == n_trans);
}
state[start] = SI_FROM_START;
visit.push(start);
while (!visit.empty()) {
int s = visit.pop();
for (Transition* t = idx[s]; t < idx[s+1]; t++)
if (!(state[t->o_state] & SI_FROM_START)) {
state[t->o_state] |= SI_FROM_START;
visit.push(t->o_state);
}
}
}
// Do a reachability analysis for all states to a final state
{
// Sort all transitions according to o_state and create index structure
// idx[i]...idx[i+1]-1 gives where transitions for state i start
TransByO_State::sort(trans, n_trans);
{
int j = 0;
for (int i=0; i<n_states; i++) {
idx[i] = &trans[j];
while ((j < n_trans) && (i == trans[j].o_state))
j++;
}
idx[n_states] = &trans[j];
assert(j == n_trans);
}
for (int i=0; i<n_finals; i++) {
state[final[i]] |= (SI_TO_FINAL | SI_FINAL);
visit.push(final[i]);
}
while (!visit.empty()) {
int s = visit.pop();
for (Transition* t = idx[s]; t < idx[s+1]; t++)
if (!(state[t->i_state] & SI_TO_FINAL)) {
state[t->i_state] |= SI_TO_FINAL;
visit.push(t->i_state);
}
}
}
// Now all reachable states are known (also the final ones)
int* re = region.alloc<int>(n_states);
for (int i=0; i<n_states; i++)
re[i] = -1;
// Renumber states
int m_states = 0;
// Start state gets zero
re[start] = m_states++;
// Renumber final states
for (int i=n_states; i--; )
if ((state[i] == (SI_FINAL | SI_FROM_START | SI_TO_FINAL)) && (re[i] < 0))
re[i] = m_states++;
// If start state is final, final states start from zero, otherwise from one
int final_fst = (state[start] & SI_FINAL) ? 0 : 1;
int final_lst = m_states;
// final_fst...final_lst-1 are the final states
// Renumber remaining states
for (int i=n_states; i--; )
if ((state[i] == (SI_FROM_START | SI_TO_FINAL)) && (re[i] < 0))
re[i] = m_states++;
// Count number of remaining transitions
int m_trans = 0;
for (int i=n_trans; i--; )
if ((re[trans[i].i_state] >= 0) && (re[trans[i].o_state] >= 0))
m_trans++;
// All done... Construct the automaton
DFAI* d = new DFAI(m_trans);
d->n_states = m_states;
d->n_trans = m_trans;
d->final_fst = final_fst;
d->final_lst = final_lst;
{
int j = 0;
Transition* r = &d->trans[0];
for (int i = 0; i<n_trans; i++)
if ((re[trans[i].i_state] >= 0) && (re[trans[i].o_state] >= 0)) {
r[j].symbol = trans[i].symbol;
r[j].i_state = re[trans[i].i_state];
r[j].o_state = re[trans[i].o_state];
j++;
}
TransBySymbol::sort(r,m_trans);
}
{
// Count number of symbols
unsigned int n_symbols = 0;
for (int i = 0; i<m_trans; ) {
int s = d->trans[i++].symbol;
n_symbols++;
while ((i<m_trans) && (d->trans[i].symbol == s))
i++;
}
d->n_symbols = n_symbols;
}
{
// Compute maximal degree
unsigned int max_degree = 0;
unsigned int* deg = region.alloc<unsigned int>(m_states);
// Compute in-degree per state
for (int i=0; i<m_states; i++)
deg[i] = 0;
for (int i=0; i<m_trans; i++)
deg[d->trans[i].o_state]++;
for (int i=0; i<m_states; i++)
max_degree = std::max(max_degree,deg[i]);
// Compute out-degree per state
for (int i=0; i<m_states; i++)
deg[i] = 0;
for (int i=0; i<m_trans; i++)
deg[d->trans[i].i_state]++;
for (int i=0; i<m_states; i++)
max_degree = std::max(max_degree,deg[i]);
// Compute transitions per symbol
{
int i=0;
while (i < m_trans) {
int j=i++;
while ((i < m_trans) &&
(d->trans[j].symbol == d->trans[i].symbol))
i++;
max_degree = std::max(max_degree,static_cast<unsigned int>(i-j));
}
}
d->max_degree = max_degree;
}
d->fill();
object(d);
}
DFA::DFA(int start, Transition t_spec[], int f_spec[], bool minimize) {
init(start,t_spec,f_spec,minimize);
}
DFA::DFA(int start, std::initializer_list<Transition> tl,
std::initializer_list<int> fl, bool minimize) {
Region reg;
int nt = static_cast<int>(tl.size());
int nf = static_cast<int>(fl.size());
Transition* ts = reg.alloc<Transition>(nt + 1);
{
int i=0;
for (const Transition& t : tl)
ts[i++] = t;
ts[nt].i_state = -1;
}
int* fs = reg.alloc<int>(nf + 1);
{
int i=0;
for (const int& f : fl)
fs[i++] = f;
fs[nf] = -1;
}
init(start,ts,fs,minimize);
}
bool
DFA::equal(const DFA& d) const {
assert(n_states() == d.n_states());
assert(n_transitions() == d.n_transitions());
assert(n_symbols() == d.n_symbols());
assert(final_fst() == d.final_fst());
assert(final_lst() == d.final_lst());
DFA::Transitions me(*this);
DFA::Transitions they(d);
while (me()) {
if (me.i_state() != they.i_state())
return false;
if (me.symbol() != they.symbol())
return false;
if (me.o_state() != they.o_state())
return false;
++me;
++they;
}
return true;
}
}
// STATISTICS: int-prop
Gecode::DFA::DFAI
Data stored for a DFA.
Definition dfa.hpp:42
Gecode::DFA::Transition
Specification of a DFA transition.
Definition int.hh:2058
Gecode::DFA::Transition::i_state
int i_state
input state
Definition int.hh:2060
Gecode::DFA::Transition::o_state
int o_state
output state Default constructor
Definition int.hh:2062
Gecode::DFA::Transition::symbol
int symbol
symbol
Definition int.hh:2061
Gecode::DFA::Transitions
Iterator for DFA transitions (sorted by symbols).
Definition int.hh:2069
Gecode::DFA
Deterministic finite automaton (DFA).
Definition int.hh:2049
Gecode::DFA::max_degree
unsigned int max_degree(void) const
Return maximal degree (in-degree and out-degree) of any state.
Definition dfa.hpp:157
Gecode::DFA::n_states
int n_states(void) const
Return the number of states.
Definition dfa.hpp:139
Gecode::DFA::DFA
DFA(void)
Initialize for DFA accepting the empty word.
Definition dfa.hpp:131
Gecode::DFA::final_lst
int final_lst(void) const
Return the number of the last final state.
Definition dfa.hpp:169
Gecode::DFA::n_transitions
int n_transitions(void) const
Return the number of transitions.
Definition dfa.hpp:151
Gecode::DFA::n_symbols
unsigned int n_symbols(void) const
Return the number of symbols.
Definition dfa.hpp:145
Gecode::DFA::init
void init(int s, Transition t[], int f[], bool minimize=true)
Initialize DFA.
Definition dfa.cpp:152
Gecode::DFA::final_fst
int final_fst(void) const
Return the number of the first final state.
Definition dfa.hpp:163
Gecode::Int::Extensional::GroupStates
GroupStates is used to index StateGroup by group
Definition dfa.cpp:133
Gecode::Int::Extensional::GroupStates::fst
StateGroup * fst
Definition dfa.cpp:135
Gecode::Int::Extensional::GroupStates::lst
StateGroup * lst
Definition dfa.cpp:136
Gecode::Int::Extensional::StateGroupByGroup
Sort groups stated by group and then state.
Definition dfa.cpp:116
Gecode::Int::Extensional::StateGroupByGroup::operator()
bool operator()(const StateGroup &x, const StateGroup &y)
Definition dfa.cpp:119
Gecode::Int::Extensional::StateGroupByGroup::sort
static void sort(StateGroup sg[], int n)
Definition dfa.cpp:124
Gecode::Int::Extensional::StateGroup
Stategroup is used to compute a partition of states.
Definition dfa.cpp:107
Gecode::Int::Extensional::StateGroup::group
int group
Definition dfa.cpp:110
Gecode::Int::Extensional::StateGroup::state
int state
Definition dfa.cpp:109
Gecode::Int::Extensional::TransByI_State
Sort transition array by input state.
Definition dfa.cpp:41
Gecode::Int::Extensional::TransByI_State::operator()
bool operator()(const DFA::Transition &x, const DFA::Transition &y)
Definition dfa.cpp:44
Gecode::Int::Extensional::TransByI_State::sort
static void sort(DFA::Transition t[], int n)
Definition dfa.cpp:48
Gecode::Int::Extensional::TransByO_State
Sort transition array by output state.
Definition dfa.cpp:90
Gecode::Int::Extensional::TransByO_State::sort
static void sort(DFA::Transition t[], int n)
Definition dfa.cpp:97
Gecode::Int::Extensional::TransByO_State::operator()
bool operator()(const DFA::Transition &x, const DFA::Transition &y)
Definition dfa.cpp:93
Gecode::Int::Extensional::TransBySymbolI_State
Sort transition array by symbol and then input states.
Definition dfa.cpp:73
Gecode::Int::Extensional::TransBySymbolI_State::sort
static void sort(DFA::Transition t[], int n)
Definition dfa.cpp:81
Gecode::Int::Extensional::TransBySymbolI_State::operator()
bool operator()(const DFA::Transition &x, const DFA::Transition &y)
Definition dfa.cpp:76
Gecode::Int::Extensional::TransBySymbol
Sort transition array by symbol (value).
Definition dfa.cpp:57
Gecode::Int::Extensional::TransBySymbol::sort
static void sort(DFA::Transition t[], int n)
Definition dfa.cpp:64
Gecode::Int::Extensional::TransBySymbol::operator()
bool operator()(const DFA::Transition &x, const DFA::Transition &y)
Definition dfa.cpp:60
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Region::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition region.hpp:386
Gecode::SharedHandle::object
SharedHandle::Object * object(void) const
Access to the shared object.
Definition shared-object.hpp:102
Gecode::Support::StaticStack
Stack with fixed number of elements.
Definition static-stack.hpp:42
Gecode::Support::StaticStack::push
void push(const T &x)
Push element x on top of stack.
Definition static-stack.hpp:137
Gecode::Support::StaticStack::pop
T pop(void)
Pop topmost element from stack and return it.
Definition static-stack.hpp:116
Gecode::Support::StaticStack::empty
bool empty(void) const
Test whether stack is empty.
Definition static-stack.hpp:98
int.hh
Gecode::Int::Extensional
Extensional propagators
Gecode::Int::Extensional::StateInfo
StateInfo
Information about states.
Definition dfa.cpp:140
Gecode::Int::Extensional::SI_FINAL
@ SI_FINAL
State is final.
Definition dfa.cpp:144
Gecode::Int::Extensional::SI_NONE
@ SI_NONE
State is not reachable.
Definition dfa.cpp:141
Gecode::Int::Extensional::SI_FROM_START
@ SI_FROM_START
State is reachable from start state.
Definition dfa.cpp:142
Gecode::Int::Extensional::SI_TO_FINAL
@ SI_TO_FINAL
Final state is reachable from state.
Definition dfa.cpp:143
Gecode::Int
Finite domain integers.
Gecode::Support::quicksort
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode
Gecode toplevel namespace
forceinline
#define forceinline
Definition config.hpp:187