Диссертация (1137435), страница 18

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 18)

r i g h t ;f o r ( int j = 0 ; j < A. s i z e ( ) ; ++j ) {int x = A[ j ] ;i f ( ! used [ x ] ) {used [ x ] = true ;fo r ( int i = 0 ; i <attr_implications [ x ] . size () ;++i ) {int impl_ind =attr_implications [ x][ i ];−−r e q u i r e d [ impl_ind ] ;i f ( r e q u i r e d [ impl_ind ]== 0 )add_right .push_back (impl_ind ) ;}}}}mset r e t ;f o r ( int i = 0 ; i < n ; ++i )146i f ( used [ i ] )r e t . push_back ( i ) ;return r e t ;}s t d : : v e c t o r <I m p l i c a t i o n > find_min_base ( const s t d : : v e c t o r <I m p l i c a t i o n >& i m p l i c a t i o n s ) {s t d : : v e c t o r <I m p l i c a t i o n > r e t ;i f ( i m p l i c a t i o n s . s i z e ( ) == 0 )return r e t ;int n = i m p l i c a t i o n s [ 0 ] . n u m b e r _ o f _ a t t r i i b u t e s ;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 = 0 ; i < i m p l i c a t i o n s .

s i z e ( ) ; ++i ) {Implication I ;I . number_of_attriibutes = n ;I . l e f t = implications [ i ] . l e f t ;I . r i g h t = l i n _ c l o s u r e ( i m p l i c a t i o n s , get_union (implications [ i ] . left , implications [ i ] . right ));J . push_back ( I ) ;}s o r t ( J . b e g i n ( ) , J . end ( ) ) ;int j s z = 1 ;f o r ( int i = 1 ; i < J . s i z e ( ) ; ++i ) {147i f ( J [ i ] != J [ i − 1 ] ) {J[ jsz ] = J[ i ] ;++j s z ;}}J. resize ( jsz ) ;f o r ( int i = 0 ; i < J . s i z e ( ) ; ++i ) {int r e t _ s z = r e t . s i z e ( ) ;f o r ( int j = i + 1 ; j < J .

s i z e ( ) ; ++j )r e t . push_back ( J [ j ] ) ;mset C = l i n _ c l o s u r e ( r e t , J [ i ] . l e f t ) ;r e t . r e s i z e ( ret_sz ) ;i f (C != J [ i ] . r i g h t ) {Implication I ;I . number_of_attriibutes = n ;I . l e f t = C;I . right = J [ i ] . right ;r e t . push_back ( I ) ;}}return r e t ;}}1485.7.Приложение 1.3Файл context.h:#i f n d e f CONTEXT_H#define CONTEXT_H#include " mset . h"namespace s p a r s e _ c o n t e x t {c l a s s Context{public :int M;s t d : : v e c t o r <mset> o b j e c t s ;mset c l o s u r e ( const mset& X) const ;bool i s _ c l o s e d ( const mset& X) const ;void p r i n t ( ) const ;s t d : : v e c t o r <s t d : : v e c t o r <bool> > g e t _ b i n a r y _ t a b l e ( )const ;void i n i t _ f r o m _ t a b l e ( const s t d : : v e c t o r <s t d : : v e c t o r <int>>& t a b l e ) ;};}149#endifФайл context.cpp:#include " c o n t e x t .

h"#include <c s t d i o >#include <a l g o r i t h m >namespace s p a r s e _ c o n t e x t {mset Context : : c l o s u r e ( const mset& X) const{mset r e t ;f o r ( int i = 0 ; i < M; ++i )r e t . push_back ( i ) ;f o r ( int i = 0 ; i < o b j e c t s . s i z e ( ) ; ++i ) {i f ( i s _ s u b s e t ( o b j e c t s [ i ] , X) )ret = get_intersection ( ret , objects [ i ] );}return r e t ;}bool Context : : i s _ c l o s e d ( const mset& X) const{return X == c l o s u r e (X) ;}150void Context : : p r i n t ( ) const{f o r ( int i = 0 ; i < o b j e c t s . s i z e ( ) ; ++i ) {s t d : : v e c t o r <bool> row (M, f a l s e ) ;f o r ( int j = 0 ; j < o b j e c t s [ i ] . s i z e ( ) ; ++j )row [ o b j e c t s [ i ] [ j ] ] = true ;f o r ( int j = 0 ; j < M; ++j ) {i f ( row [ j ] )p r i n t f ( "1" ) ;elsep r i n t f ( "0" ) ;}p r i n t f ( "\n" ) ;}}s t d : : v e c t o r <s t d : : v e c t o r <bool> > Context : : g e t _ b i n a r y _ t a b l e ( )const{s t d : : v e c t o r <s t d : : v e c t o r <bool> > r e t ;f o r ( int i = 0 ; i < o b j e c t s .

s i z e ( ) ; ++i ) {s t d : : v e c t o r <bool> row (M, f a l s e ) ;f o r ( int j = 0 ; j < o b j e c t s [ i ] . s i z e ( ) ; ++j )row [ o b j e c t s [ i ] [ j ] ] = true ;r e t . push_back ( row ) ;}return r e t ;151}void Context : : i n i t _ f r o m _ t a b l e ( const s t d : : v e c t o r <s t d : : v e c t o r <int> >& t a b l e ) {s t d : : v e c t o r <int> c n t ( t a b l e [ 0 ] . s i z e ( ) , 0 ) ;f o r ( int i = 0 ; i < t a b l e .

s i z e ( ) ; ++i ) {f o r ( int j = 0 ; j < t a b l e [ i ] . s i z e ( ) ; ++j )c n t [ j ]= s t d : : max( c n t [ j ] , t a b l e [ i ] [ j ] +1) ;}f o r ( int i = 0 ; i < c n t . s i z e ( ) ; ++i )i f ( c n t [ i ] == 2 )cnt [ i ] = 1 ;s t d : : v e c t o r <int> sum ( t a b l e [ 0 ] . s i z e ( ) , 0 ) ;sum [ 0 ] = c n t [ 0 ] ;f o r ( int i = 1 ; i < c n t . s i z e ( ) ; ++i )sum [ i ] = sum [ i − 1 ] + c n t [ i ] ;M = sum . back ( ) ;f o r ( int i = 0 ; i < t a b l e . s i z e ( ) ; ++i ) {mset o b j ;f o r ( int j = 0 ; j < t a b l e [ i ] .

s i z e ( ) ; ++j ) {int i n d = 0 ;i f ( j > 0)i n d += sum [ j − 1 ] ;i f ( c n t [ j ] == 1 ) {i f ( t a b l e [ i ] [ j ] == 0 )i n d = −1000;152} elsei n d += t a b l e [ i ] [ j ] ;i f ( i n d >= 0 )o b j . push_back ( i n d ) ;}o b j e c t s . push_back ( o b j ) ;}}}5.8.Приложение 1.4Файл min_transversals.h:#i f n d e f MIN_TRANSVERSALS_H#define MIN_TRANSVERSALS_H#include <v e c t o r >#include <i o s t r e a m >#include <a l g o r i t h m >#include " mset . h"namespacemin_transversals {153void u p d a t e _ p a r t i t i o n ( const s t d : : v e c t o r <int>& p a r t i t i o n , const mset& E ,s t d : : v e c t o r <int>&new_partition ,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);void d f s _ t r a n s v e r s a l ( const mset& t r a n s v , int i ,const s t d : : v e c t o r < s t d : : v e c t o r<int> >& part_nodes ,mset& c u r r e n t _ t r a n s v e r s a l ) ;void e x t r a c t _ t r a n s v e r s a l s ( const mset& t r a n s v , const s t d : : v e c t o r <int>&partition ) ;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 ) ;void 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 ) ;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 ) ;154}#endif //MIN_TRANSVERSALS_HФайл min_transversals.cpp:#include " m i n _ t r a n s v e r s a l s .

h"namespace m i n _ t r a n s v e r s a l s {s t a t i c s t d : : v e c t o r <mset> k eys ;void u p d a t e _ p a r t i t i o n ( const s t d : : v e c t o r <int>& p a r t i t i o n , const mset& E ,s t d : : v e c t o r <int>&new_partition ,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){int n = p a r t i t i o n .

s i z e ( ) ;int no_parts = 0 ;f o r ( int v = 0 ; v < n ; ++v )no_parts = s t d : : max( no_parts , p a r t i t i o n [ v ] + 1 ) ;s t d : : v e c t o r <int> s i z e _ o f _ p a r t ( no_parts , 0 ) ;f o r ( int v = 0 ; v < n ; ++v ) {int part_index = p a r t i t i o n [ v ] ;155++s i z e _ o f _ p a r t [ part_index ] ;}s t d : : v e c t o r <int> part_cover ( no_parts , 0 ) ;f o r ( int i = 0 ; i < E . s i z e ( ) ; ++i ) {int v = E [ i ] ;int part_index = p a r t i t i o n [ v ] ;++part_cover [ part_index ] ;}f i r s t _ p a r t . a s s i g n ( no_parts , −1) ;second_part .

a s s i g n ( no_parts , −1) ;int no_new_parts = 0 ;f o r ( int i = 0 ; i < no_parts ; ++i ) {i f ( part_cover [ i ] == s i z e _ o f _ p a r t [ i ] ) {second_part [ i ] = no_new_parts ;++no_new_parts ;}i f ( part_cover [ i ] > 0 && part_cover [ i ] < s i z e _ o f _ p a r t [ i]) {second_part [ i ] = no_new_parts ;++no_new_parts ;f i r s t _ p a r t [ i ] = no_new_parts ;++no_new_parts ;}i f ( part_cover [ i ] == 0 ) {f i r s t _ p a r t [ i ] = no_new_parts ;156++no_new_parts ;}}new_partition . a s s i g n (n , 0) ;f o r ( int v = 0 ; v < n ; ++v ) {int part_index = p a r t i t i o n [ v ] ;n e w _ p a r t i t i o n [ v ] = f i r s t _ p a r t [ part_index ] ;}f o r ( int i = 0 ; i < E .

s i z e ( ) ; ++i ) {int v = E [ i ] ;int part_index = p a r t i t i o n [ v ] ;n e w _ p a r t i t i o n [ v ] = second_part [ part_index ] ;}}void d f s _ t r a n s v e r s a l ( const mset& t r a n s v , int i ,const s t d : : v e c t o r < s t d : : v e c t o r<int> >& part_nodes ,mset& c u r r e n t _ t r a n s v e r s a l ){i f ( i >= t r a n s v . s i z e ( ) ) {// c u r r e n t _ t r a n s v e r s a l i s a new minimal t r a n s v e r s a l ! ! !================k e y s . push_back ( c u r r e n t _ t r a n s v e r s a l ) ;157//============================================================return ;}int part_index = t r a n s v [ i ] ;f o r ( int j = 0 ; j < part_nodes [ part_index ] .

s i z e ( ) ; ++j ) {int v = part_nodes [ part_index ] [ j ] ;c u r r e n t _ t r a n s v e r s a l . push_back ( v ) ;d f s _ t r a n s v e r s a l ( t r a n s v , i + 1 , part_nodes ,current_transversal ) ;c u r r e n t _ t r a n s v e r s a l . pop_back ( ) ;}}void e x t r a c t _ t r a n s v e r s a l s ( const mset& t r a n s v , const s t d : : v e c t o r <int>&partition ) {int n = p a r t i t i o n . s i z e ( ) ;int no_parts = 0 ;f o r ( int v = 0 ; v < n ; ++v )no_parts = s t d : : max( no_parts , p a r t i t i o n [ v ] + 1 ) ;s t d : : v e c t o r < s t d : : v e c t o r <int> > part_nodes ( no_parts ) ;f o r ( int v = 0 ; v < n ; ++v ) {int part_index = p a r t i t i o n [ v ] ;part_nodes [ part_index ] .

Характеристики

Список файлов диссертации