BackboneLength.h

Go to the documentation of this file.

 
#pragma once
 
#include <queue>
 
#include <ext/algorithm>
#include <ext/utility>
 
#include <automaton/FSM/DFA.h>
 
namespace stringology {
 
namespace properties {
 
class BackboneLength {
public:
    template < class SymbolType, class StateType >
    static unsigned length ( const automaton::DFA < SymbolType, StateType > & automaton );
 
    template < class StateType >
    class BackboneLengthLess {
    public:
        bool operator ( ) ( const std::pair < StateType, unsigned > & first, const std::pair < StateType, unsigned > & second ) {
            return first.second < second.second;
        }
    };
 
};
 
template < class SymbolType, class StateType >
unsigned BackboneLength::length ( const automaton::DFA < SymbolType, StateType > & automaton ) {
    std::priority_queue < std::pair < StateType, unsigned >, ext::vector < std::pair < StateType, unsigned > >, BackboneLengthLess < StateType > > open;
    ext::map < StateType, unsigned > closed;
 
    unsigned max = 0;
    open.push ( std::make_pair ( automaton.getInitialState ( ), max ) );
 
    while ( ! open.empty ( ) ) {
        std::pair < StateType, unsigned > current = std::move ( open.top ( ) );
        open.pop ( );
        unsigned & dist = closed [ current.first ];
 
        if ( dist > current.second )
            continue;
 
        dist = current.second;
        max = std::max ( max, current.second );
 
        for ( const std::pair < const ext::pair < StateType, SymbolType >, StateType > & target : automaton.getTransitionsFromState ( current.first ) )
            open.push ( std::make_pair ( target.second, current.second + 1 ) );
    }
 
    return max;
}
 
} /* namespace properties */
 
} /* namespace stringology */