Диссертация (1137435), страница 19
Текст из файла (страница 19)
push_back ( v ) ;}158mset c u r r e n t _ t r a n s v ;d f s _ t r a n s v e r s a l ( t r a n s v , 0 , part_nodes , c u r r e n t _ t r a n s v ) ;}bool i s _ a p p r o p r i a t e _ n o d e ( const mset& t r a n s v , int added_node , const s t d: : v e c t o r <int> p a r t i t i o n ,const s t d : : v e c t o r <mset>& edges ,int last_edge_index ){i f ( last_edge_index < 0 )return true ;int n = p a r t i t i o n .
s i z e ( ) ;s t d : : v e c t o r <bool> transv_mask ( n , f a l s e ) ; // no_parts <= n , so ni s OKf o r ( int i = 0 ; i < t r a n s v . s i z e ( ) ; ++i ) {int part_index = t r a n s v [ i ] ;transv_mask [ part_index ] = true ;}s t d : : v e c t o r <bool> important_part ( n , f a l s e ) ;f o r ( int i = 0 ; i <= last_edge_index ; ++i ) {bool important_edge = true ;bool i n t r _ a t _ l e a s t _ 2 = f a l s e ;int e l e m e n t _ f r o m _ i n t e r s e c t i o n = −1;f o r ( int j = 0 ; j < e d g e s [ i ] . s i z e ( ) ; ++j ) {159int v = e d g e s [ i ] [ j ] ;int part_index = p a r t i t i o n [ v ] ;i f ( part_index == added_node ) {important_edge = f a l s e ;break ;}i f ( transv_mask [ part_index ] ) {i f ( e l e m e n t _ f r o m _ i n t e r s e c t i o n == −1)element_from_intersection =part_index ;i f ( e l e m e n t _ f r o m _ i n t e r s e c t i o n !=part_index ) {important_edge = f a l s e ;break ;}}}i f ( important_edge )important_part [ e l e m e n t _ f r o m _ i n t e r s e c t i o n ] =true ;}f o r ( int i = 0 ; i < n ; ++i )i f ( transv_mask [ i ] && ! important_part [ i ] )return f a l s e ;return true ;}160void add_next_hyperedge ( const s t d : : v e c t o r <int>& p a r t i t i o n , const mset&t r a n s v , const s t d : : v e c t o r <mset>& edges ,int edge_index ){i f ( edge_index >= e d g e s .
s i z e ( ) ) {e x t r a c t _ t r a n s v e r s a l s ( transv , p a r t i t i o n ) ;return ;}const mset& E = e d g e s [ edge_index ] ;int n = p a r t i t i o n . s i z e ( ) ;s t d : : v e c t o r <int> n e w _ p a r t i t i o n ;s t d : : v e c t o r <int> f i r s t _ p a r t ;s t d : : v e c t o r <int> second_part ;u p d a t e _ p a r t i t i o n ( p a r t i t i o n , E , new_partition , f i r s t _ p a r t ,second_part ) ;int betta_cnt = 0 ;s t d : : v e c t o r <int> gamma_parts ;s t d : : v e c t o r <int> alpha_betta_parts ;f o r ( int i = 0 ; i < t r a n s v . s i z e ( ) ; ++i ) {int part_index = t r a n s v [ i ] ;i f ( f i r s t _ p a r t [ part_index ] == −1)++betta_cnt ;161i f ( f i r s t _ p a r t [ part_index ] != −1 && second_part [part_index ] != −1)gamma_parts . push_back ( part_index ) ;elsealpha_betta_parts .
push_back ( part_index ) ;}int gamma_cnt = gamma_parts . s i z e ( ) ;mset new_transv ;f o r ( int i = 0 ; i < alpha_betta_parts . s i z e ( ) ; ++i ) {int part_index = alpha_betta_parts [ i ] ;i f ( f i r s t _ p a r t [ part_index ] != −1)new_transv . push_back ( f i r s t _ p a r t [ part_index ] ) ;elsenew_transv . push_back ( second_part [ part_index ] ) ;}f o r ( long long mask = 1 ; mask < ( ( unsigned long long ) 1 <<gamma_cnt ) ; ++mask ) {new_transv .
r e s i z e ( alpha_betta_parts . s i z e ( ) ) ;f o r ( int i = 0 ; i < gamma_parts . s i z e ( ) ; ++i ) {int part_index = gamma_parts [ i ] ;i f ( ( mask >> i ) & 1 )new_transv . push_back ( second_part [part_index ] ) ;else162new_transv . push_back ( f i r s t _ p a r t [part_index ] ) ;}add_next_hyperedge ( new_partition , new_transv , edges ,edge_index + 1 ) ; // r e c u r s i v e c a l l}new_transv . r e s i z e ( alpha_betta_parts . s i z e ( ) ) ;f o r ( int i = 0 ; i < gamma_parts . s i z e ( ) ; ++i ) {int part_index = gamma_parts [ i ] ;new_transv .
push_back ( f i r s t _ p a r t [ part_index ] ) ;}i f ( betta_cnt >0) {add_next_hyperedge ( new_partition , new_transv , edges ,edge_index + 1 ) ; // r e c u r s i v e c a l l} else {s t d : : v e c t o r <bool> transv_mask ( f i r s t _ p a r t .
s i z e ( ) , f a l s e );f o r ( int i = 0 ; i < t r a n s v . s i z e ( ) ; ++i )transv_mask [ t r a n s v [ i ] ] = true ;f o r ( int i = 0 ; i < second_part . s i z e ( ) ; ++i ) {i f ( second_part [ i ] != −1 && ! transv_mask [ i ] ) {int part_index = i ;i f ( is_appropriate_node ( transv ,part_index , p a r t i t i o n , edges ,edge_index − 1 ) ) {163new_transv . push_back (second_part [ part_index ] ) ;add_next_hyperedge (new_partition , new_transv ,edges , edge_index + 1 ) ; //recursive callnew_transv .
pop_back ( ) ;}}}}}s t d : : v e c t o r <mset> f i n d _ a l l _ m i n i m a l _ t r a n s v e r s a l s ( const s t d : : v e c t o r <mset>& edges , int number_of_nodes ) {keys . r e s i z e (0) ;s t d : : v e c t o r <int> p a r t i t i o n ( number_of_nodes , 0 ) ;mset t r a n s v ;add_next_hyperedge ( p a r t i t i o n , t r a n s v , edges , 0 ) ;return k e y s ;}}1645.9.Приложение 1.5Файл angluin.h:#i f n d e f ANGLUIN_H#define ANGLUIN_H#include " mset . h"#include " i m p l i c a t i o n s .
h"#include " c o n t e x t . h"namespace i m p l i c a t i o n s {void u p d a t e _ i m p l i c a t i o n _ b a s e ( const mset& pexample , consts p a r s e _ c o n t e x t : : Context& K, s t d : : v e c t o r <I m p l i c a t i o n >& b a s e ) ;s t d : : v e c t o r <I m p l i c a t i o n > get_approximate_base ( consts p a r s e _ c o n t e x t : : Context& K, int no_steps ) ;}#endif ANGLUIN_HФайл angluin.cpp:#include " a n g l u i n . h"namespace i m p l i c a t i o n s {165void u p d a t e _ i m p l i c a t i o n _ b a s e ( const mset& example , consts p a r s e _ c o n t e x t : : Context& K, s t d : : v e c t o r <I m p l i c a t i o n >& b a s e ){bool ok = f a l s e ;f o r ( int i = 0 ; i < b as e .
s i z e ( ) ; ++i ) {i f ( ! i s _ s u b s e t ( example , ba se [ i ] . l e f t ) ) {mset A = g e t _ i n t e r s e c t i o n ( b as e [ i ] . l e f t ,example ) ;mset B = K. c l o s u r e (A) ;i f (A != B) {I m p l i c a t i o n impl ;impl . l e f t = A;impl . r i g h t = B ;impl . n u m b e r _ o f _ a t t r i i b u t e s = K.M;ba se [ i ] = impl ;return ;}}}I m p l i c a t i o n impl ;impl .
l e f t = example ;impl . r i g h t = K. c l o s u r e ( example ) ;impl . n u m b e r _ o f _ a t t r i i b u t e s = K.M;b a s e . push_back ( impl ) ;}166s t d : : v e c t o r <I m p l i c a t i o n > get_approximate_base ( consts p a r s e _ c o n t e x t : : Context& K, int no_steps ) {int m = K.M;s t d : : v e c t o r <I m p l i c a t i o n > J ;f o r ( int i t = 0 ; i t < no_steps ; ++i t ) {mset example ;i f ( i t < 200)example = get_rand_closed1 ( J , m, 0 .
5 ) ;elseexample = get_rand_closed2 ( J , m, 0 . 5 ) ;mset c l = K. c l o s u r e ( example ) ;i f ( c l != example ) {u p d a t e _ i m p l i c a t i o n _ b a s e ( example , K, J ) ;}}return J ;}}5.10.Приложение 1.6Файл proper_premises.h:#i f n d e f PROPER_PREMISES_H#define PROPER_PREMISES_H167#include " mset . h"#include " i m p l i c a t i o n s . h"#include " c o n t e x t . h"namespace p r o p e r _ p r e m i s e s {s t d : : v e c t o r <i m p l i c a t i o n s : : I m p l i c a t i o n >get_proper_premieses_base ( const s p a r s e _ c o n t e x t : : Context& K) ;}#endifФайл proper_premises.cpp:#include " p r o p e r _ p r e m i s e s .
h"#include " m i n _ t r a n s v e r s a l s . h"using namespace i m p l i c a t i o n s ;using namespace m i n _ t r a n s v e r s a l s ;using namespace s t d ;namespace p r o p e r _ p r e m i s e s {v e c t o r <mset> get_sh ( const s p a r s e _ c o n t e x t : : Context& c o n t e x t , intm) {v e c t o r <v e c t o r <bool> > K = c o n t e x t . g e t _ b i n a r y _ t a b l e ( ) ;int n = K [ 0 ] .
s i z e ( ) ;v e c t o r <mset> r e t ;f o r ( int i = 0 ; i < K. s i z e ( ) ; ++i ) {i f ( !K[ i ] [m] ) {168bool ok = true ;fo r ( int j = 0 ; j < K. s i z e ( ) ; ++j ) {i f ( !K[ j ] [m] && j != i ) {bool s u b s e t = true ;fo r ( int k = 0 ; k < n ;++k ) {i f (K[ i ] [ k ] &&!K[ j ] [ k ] ) {subset=false;break ;}}i f ( subset )ok = f a l s e ;break ;}}i f ( ok ) {mset X;fo r ( int k = 0 ; k < n ; ++k )i f ( !K[ i ] [ k ] )X. push_back ( k ) ;r e t . push_back (X) ;169}}}return r e t ;}s t d : : v e c t o r <I m p l i c a t i o n > get_proper_premieses_base ( consts p a r s e _ c o n t e x t : : Context& K) {s t d : : v e c t o r <I m p l i c a t i o n > J ;int m = K.M;f o r ( int i = 0 ; i < m; ++i ) {s t d : : v e c t o r <mset> sh = get_sh (K, i ) ;s t d : : v e c t o r <mset> t r =f i n d _ a l l _ m i n i m a l _ t r a n s v e r s a l s ( sh , m) ;f o r ( int j = 0 ; j < t r .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
