, , ,

<<


 >>  ()
Pages:     | 1 | 2 ||

...

-- [ 3 ] --

f o r ( int i = 0 ;

i B. s i z e ( ) ;

++i ) used [ B [ i ] ] = true ;

f o r ( int i = 0 ;

i n ;

++i ) i f ( used [ i ] ) r e t. push_back ( i ) ;

} return r e t ;

} mset g e t _ i n t e r s e c t i o n ( const mset& A, const mset& B) { mset r e t ;

bool ok = true ;

f o r ( int i = 1 ;

i A. s i z e ( ) ;

++i ) { i f (A[ i ] A[ i 1 ] ) { ok = f a l s e ;

break ;

} } i f ( ok ) { f o r ( int i = 1 ;

i B. s i z e ( ) ;

++i ) { i f (B [ i ] B [ i 1 ] ) { ok = f a l s e ;

break ;

} } } i f ( ok ) { int i = 0 ;

int j = 0 ;

while ( i A. s i z e ( ) && j B. s i z e ( ) ) { i f (A[ i ] B [ j ] ) ++i ;

e l s e i f (A[ i ] B [ j ] ) ++j ;

else { r e t. push_back (A[ i ] ) ;

++i ;

++j ;

} } } else { int n = 0 ;

f o r ( int i = 0 ;

i A. s i z e ( ) ;

++i ) n = s t d : : max( n, A[ i ] + 1 ) ;

f o r ( int i = 0 ;

i B. s i z e ( ) ;

++i ) n = s t d : : max( n, B [ i ] + 1 ) ;

s t d : : v e c t o r unsigned char used ( n, 0 ) ;

f o r ( int i = 0 ;

i A. s i z e ( ) ;

++i ) ++used [A[ i ] ] ;

f o r ( int i = 0 ;

i B. s i z e ( ) ;

++i ) ++used [ B [ i ] ] ;

f o r ( int i = 0 ;

i n ;

++i ) i f ( used [ i ] == 2 ) r e t. push_back ( i ) ;

} return r e t ;

} bool i s _ s u b s e t ( const mset& s u p e r s e t, const mset& s u b s e t ) { i f ( superset. s i z e () subset. s i z e () ) return f a l s e ;

int i = 0, j = 0 ;

bool r e t = true ;

while ( i s u b s e t. s i z e ( ) && j s u p e r s e t. s i z e ( ) ) { i f ( subset [ i ] superset [ j ] ) return f a l s e ;

i f ( s u b s e t [ i ] == s u p e r s e t [ j ] ) { ++i ;

++j ;

} else ++j ;

} return i = s u b s e t. s i z e ( ) ;

} void p r i n t ( const mset& s, int M) { s t d : : v e c t o r bool a (M, f a l s e ) ;

f o r ( int i = 0 ;

i s. s i z e ( ) ;

++i ) a [ s [ i ] ] = true ;

f o r ( int i = 0 ;

i M;

++i ) { if (a [ i ]) p r i n t f ( "1" ) ;

else p r i n t f ( "0" ) ;

} } mset rand_set ( int M, double p ) { mset r e t ;

// d o u b l e p = 0. 5 ;

f o r ( int i = 0 ;

i M;

++i ) i f ( ( double ) rand ( ) / RAND_MAX = p ) r e t. push_back ( i ) ;

return r e t ;

} 5.6. 1. implications.h:

#i f n d e f IMPLICATIONS_H #define IMPLICATIONS_H #include v e c t o r #include a l g o r i t h m #include " mset. h" namespace i m p l i c a t i o n s { struct I m p l i c a t i o n { int n u m b e r _ o f _ a t t r i i b u t e s ;

mset l e f t ;

mset r i g h t ;

bool operator ( const I m p l i c a t i o n& I ) const { i f ( n u m b e r _ o f _ a t t r i i b u t e s != I.

number_of_attriibutes ) return n u m b e r _ o f _ a t t r i i b u t e s I.

number_of_attriibutes ;

i f ( l e f t != I. l e f t ) return l e f t I. l e f t ;

return r i g h t I. r i g h t ;

} bool operator != ( const I m p l i c a t i o n& I ) const { i f ( n u m b e r _ o f _ a t t r i i b u t e s != I.

number_of_attriibutes ) return true ;

return l e f t != I. l e f t | | r i g h t != I. r i g h t ;

} bool operator == ( const I m p l i c a t i o n& I ) const { i f ( n u m b e r _ o f _ a t t r i i b u t e s != I.

number_of_attriibutes ) return f a l s e ;

return l e f t == I. l e f t && r i g h t == I. r i g h t ;

} };

mset l i n _ c l o s u r e ( 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, const mset& X) ;

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 ) ;

mset get_rand_closed1 ( 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, int M, double p = 0. 5 ) ;

mset get_rand_closed2 ( 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, int M, double p = 0. 5 ) ;

} #endif implications.cpp:

#include " i m p l i c a t i o n s. h" namespace i m p l i c a t i o n s { mset get_rand_closed1 ( 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, int M, double p ) { mset X = rand_set (M, p ) ;

// r e t u r n l i n _ c l o s u r e ( i m p l i c a t i o n s, X) ;

while ( 1 ) { X = rand_set (M, p ) ;

i f (X == l i n _ c l o s u r e ( i m p l i c a t i o n s, X) ) break ;

} return X;

} mset get_rand_closed2 ( 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, int M, double p ) { mset X = rand_set (M, p ) ;

return l i n _ c l o s u r e ( i m p l i c a t i o n s, X) ;

} mset l i n _ c l o s u r e ( 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, const mset& X) { i f ( i m p l i c a t i o n s. s i z e ( ) == 0 ) return X;

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 bool used ( n, f a l s e ) ;

s t d : : v e c t o r int r e q u i r e d ( i m p l i c a t i o n s. s i z e ( ), 0 ) ;

s t d : : v e c t o r s t d : : v e c t o r int a t t r _ i m p l i c a t i o n s ( n ) ;

f o r ( int i = 0 ;

i i m p l i c a t i o n s. s i z e ( ) ;

++i ) { const mset& A = i m p l i c a t i o n s [ i ]. l e f t ;

r e q u i r e d [ i ] = A. s i z e ( ) ;

f o r ( int j = 0 ;

j A. s i z e ( ) ;

++j ) { int a t r = A[ j ] ;

a t t r _ i m p l i c a t i o n s [ a t r ]. push_back ( i ) ;

} } s t d : : v e c t o r int add_right ;

f o r ( int j = 0 ;

j X. s i z e ( ) ;

++j ) { int x = X[ j ] ;

used [ x ] = true ;

f o r ( int i = 0 ;

i a t t r _ i m p l i c a t i o n s [ x ]. s i z e ( ) ;

++i ) { int impl_ind = a t t r _ i m p l i c a t i o n s [ 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 ) ;

} } while ( ! add_right. empty ( ) ) { int i n d = add_right. back ( ) ;

add_right. pop_back ( ) ;

const mset& A = i m p l i c a t i o n s [ i n d ]. 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 ) i 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 ) { i 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 ;

} } 5.7. 1. 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 ) ;

};

} #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) ;

} void 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" ) ;

else p 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 ;

} 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;

} else i 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. 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" namespace min_transversals { 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 );

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 ) ;

} #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 ] ;

++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 ;

++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 ) ;

// ============================================================ 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 ]. push_back ( v ) ;

} mset 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 n i s OK 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 ] ;

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 ) { int 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 ;

} 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 ) { 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 ;

i f ( f i r s t _ p a r t [ part_index ] != 1 && second_part [ part_index ] != 1) gamma_parts. push_back ( part_index ) ;

else alpha_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 ] ) ;

else new_transv. push_back ( second_part [ part_index ] ) ;

} f o r ( long long mask = 1 ;

mask ( ( unsigned long long ) 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 ] ) ;

else new_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 ) ) { new_transv. push_back ( second_part [ part_index ] ) ;

add_next_hyperedge ( new_partition, new_transv, edges, edge_index + 1 ) ;

// recursive call new_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 ;

} } 5.9. 1. 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, const s 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 ( const s 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 { void u p d a t e _ i m p l i c a t i o n _ b a s e ( const mset& example, const s 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 ) ;

} s t d : : v e c t o r I m p l i c a t i o n get_approximate_base ( const s 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 ) ;

else example = 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. proper_premises.h:

#i f n d e f PROPER_PREMISES_H #define PROPER_PREMISES_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 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, int m) { 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] ) { bool 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) ;

} } } 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 ( const s 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. s i z e ( ) ;

++j ) { Implication I ;

I. n u m b e r _ o f _ a t t r i i b u t e s = m;

I. l e f t = tr [ j ] ;

s o r t ( I. l e f t. b e g i n ( ), I. l e f t. end ( ) ) ;

I. r i g h t = K. c l o s u r e ( I. l e f t ) ;

J. push_back ( I ) ;

} } return J ;

} } 5.11. 2. shared_closure.h:

#i f n d e f SHARED_CLOSURE_H #define SHARED_CLOSURE_H #include " mset. h" #include " c o n t e x t. h" #include v e c t o r #include queue #include l i s t #include a l g o r i t h m namespace s h a r e d _ c l o s u r e { mset c l o s u r e ( const s t d : : v e c t o r s p a r s e _ c o n t e x t : : Context& K, const mset& X) ;

class PriorityQueue { public :

P r i o r i t y Q u e u e ( int M = 0 ) ;

void i n c r e a s e ( int a ) ;

void d e c r e a s e _ a l l ( ) ;

int get_min ( ) ;

int extract_min ( ) ;

void s e t ( int a, int key ) ;

private :

s t d : : v e c t o r s t d : : l i s t int a t t r i b u t e s ;

s t d : : v e c t o r int l i n k _ t o _ l i s t _ i n d e x ;

s t d : : v e c t o r s t d : : l i s t int : : c o n s t _ i t e r a t o r link_to_list_item ;


int no_deq ;

int f i r s t ;

};

} #endif shared_closure.cpp:

#include " s h a r e d _ c l o s u r e. h" namespace s h a r e d _ c l o s u r e { mset c l o s u r e ( const s t d : : v e c t o r s p a r s e _ c o n t e x t : : Context& K, const mset& X) { int m = K [ 0 ].M;

s t d : : v e c t o r s t d : : v e c t o r s t d : : v e c t o r int Kt ;

f o r ( int t = 0 ;

t K. s i z e ( ) ;

++t ) { Kt. push_back ( s t d : : v e c t o r s t d : : v e c t o r int (m, s t d : : v e c t o r int () ) ) ;

f o r ( int i = 0 ;

i K[ t ]. o b j e c t s. s i z e ( ) ;

++i ) { fo r ( int j = 0 ;

j K[ t ]. o b j e c t s [ i ].

s i z e ( ) ;

++j ) { int a = K[ t ]. o b j e c t s [ i ] [ j ] ;

Kt [ t ] [ a ]. push_back ( i ) ;

} } } s t d : : v e c t o r bool a d d e d _ a t t r i b u t e s (m, f a l s e ) ;

f o r ( int i = 0 ;

i X. s i z e ( ) ;

++i ) a d d e d _ a t t r i b u t e s [X[ i ] ] = true ;

s t d : : v e c t o r P r i o r i t y Q u e u e PQ(K. s i z e ( ), P r i o r i t y Q u e u e (m ));

s t d : : queueint s h a r e d _ a t t r i b u t e s ;

s t d : : v e c t o r s t d : : v e c t o r int o b j e c t s (K. s i z e ( ) ) ;

f o r ( int t = 0 ;

t K. s i z e ( ) ;

++t ) { s t d : : v e c t o r int c n t (m, 0 ) ;

f o r ( int i = 0 ;

i K[ t ]. o b j e c t s. s i z e ( ) ;

++i ) { i f ( i s _ s u b s e t (K[ t ]. o b j e c t s [ i ], X) ) { o b j e c t s [ t ]. push_back ( i ) ;

fo r ( int j = 0 ;

j K[ t ].

o b j e c t s [ i ]. s i z e ( ) ;

++j ) { int a = K[ t ]. o b j e c t s [ i ][ j ];

++c n t [ a ] ;

} } } f o r ( int a = 0 ;

a m;

++a ) { i f ( o b j e c t s [ t ]. s i z e ( ) == c n t [ a ] && !

added_attributes [ a ] ) { a d d e d _ a t t r i b u t e s [ a ] = true ;

s h a r e d _ a t t r i b u t e s. push ( a ) ;

} else PQ[ t ]. s e t ( a, ( int ) o b j e c t s [ t ].

s i z e ( ) cnt [ a ] ) ;

} } mset r e t = X;

while ( ! s h a r e d _ a t t r i b u t e s. empty ( ) ) { int j 0 = s h a r e d _ a t t r i b u t e s. f r o n t ( ) ;

s h a r e d _ a t t r i b u t e s. pop ( ) ;

f o r ( int t = 0 ;

t K. s i z e ( ) ;

++t ) { int s z = o b j e c t s [ t ]. s i z e ( ) ;

o b j e c t s [ j 0 ] = g e t _ i n t e r s e c t i o n ( Kt [ t ] [ j ], objects [ j0 ] ) ;

s t d : : v e c t o r int& l i s t 0 = Kt [ t ] [ j 0 ] ;

s t d : : v e c t o r int& l i s t 1 = o b j e c t s [ t ] ;

int i 0 = 0, i 1 = 0, obj_sz = 0 ;

while ( i 0 l i s t 0. s i z e ( ) && i 1 l i s t 1.

size () ) { i f ( l i s t 0 [ i 0 ] == l i s t 1 [ i 1 ] ) { o b j e c t s [ t ] [ obj_sz ] = l i s t 1 [ i1 ] ;

++obj_sz ;

++i 0 ;

++i 1 ;

} else i f ( l i s t 0 [ i0 ] l i s t 1 [ i ]) { ++i 0 ;

} else { fo r ( int j = 0 ;

j K[ t ]. objects [ i1 ]. size () ;

++j ) { int a = K[ t ].

objects [ i1 ] [ j ];

PQ[ t ]. i n c r e a s e ( a) ;

} PQ[ t ]. d e c r e a s e _ a l l ( ) ;

++i 1 ;

} } while (PQ[ t ]. get_min ( ) == 0 ) { int a = PQ[ t ]. extract_min ( ) ;

i f ( ! added_attributes [ a ] ) { added_attributes [ a ] = true ;

s h a r e d _ a t t r i b u t e s. push ( a) ;

} } o b j e c t s [ t ]. r e s i z e ( obj_sz ) ;

} } return r e t ;

} int P r i o r i t y Q u e u e : : get_min ( ) { while ( f i r s t a t t r i b u t e s. s i z e ( ) ) { i f ( ! a t t r i b u t e s [ f i r s t ]. empty ( ) ) break ;

} i f ( f i r s t = a t t r i b u t e s. s i z e ( ) ) return 1;

return f i r s t no_deq ;

} int P r i o r i t y Q u e u e : : extract_min ( ) { i f ( get_min ( ) == 1) return 1;

int a = a t t r i b u t e s [ f i r s t ]. f r o n t ( ) ;

a t t r i b u t e s [ f i r s t ]. erase ( a t t r i b u t e s [ f i r s t ]. begin () ) ;

return a ;

} void P r i o r i t y Q u e u e : : s e t ( int a, int key ) { a t t r i b u t e s [ key + no_deq ]. push_front ( a ) ;

l i n k _ t o _ l i s t _ i n d e x [ a ] = key + no_deq ;

l i n k _ t o _ l i s t _ i t e m [ a ] = a t t r i b u t e s [ key + no_deq ]. b e g i n ( ) ;

} void P r i o r i t y Q u e u e : : d e c r e a s e _ a l l ( ) { ++no_deq ;

} void P r i o r i t y Q u e u e : : i n c r e a s e ( int a ) { int i = l i n k _ t o _ l i s t _ i n d e x [ a ] ;

++l i n k _ t o _ l i s t _ i n d e x [ a ] ;

s t d : : l i s t int : : c o n s t _ i t e r a t o r i t = l i n k _ t o _ l i s t _ i t e m [ a ];

attributes [ i ]. erase ( it ) ;

a t t r i b u t e s [ i + 1 ]. push_front ( a ) ;

link_to_list_item [ a ] = a t t r i b u t e s [ i + 1 ]. begin () ;

} P r i o r i t y Q u e u e : : P r i o r i t y Q u e u e ( int M = 0 ) : no_deq ( 0 ), f i r s t ( 0 ) { a t t r i b u t e s. r e s i z e (M + M) ;

l i n k _ t o _ l i s t _ i n d e x. a s s i g n (M + M, 1) ;

l i n k _ t o _ l i s t _ i t e m. r e s i z e (M + M) ;

} } 5.12. 3. JSM_test.cpp:

#include i o s t r e a m #include a l g o r i t h m #include v e c t o r #include s e t #include s t r i n g #include sstream #include " mset. h" #include " c o n t e x t. h" using namespace s t d ;

using namespace s p a r s e _ c o n t e x t ;

void r e a d ( Context& K, s t r i n g fname ) { f r e o p e n ( fname. c _ s t r ( ), " r ", s t d i n ) ;

K. o b j e c t s. r e s i z e ( 0 ) ;


K.M = 0 ;

string s ;

while ( g e t l i n e ( c i n, s ) ) { istringstream is ( s ) ;

mset row ;

int a ;

while ( i s a ) { row. push_back ( a ) ;

K.M = max(K.M, a + 1 ) ;

} K. o b j e c t s. push_back ( row ) ;

} cin. clear () ;

} void r e a d _ a l l ( v e c t o r Context& pK, v e c t o r Context& nK, bool t r = true, int s u p p o r t = 3 5 ) { pK. r e s i z e ( 0 ) ;

nK. r e s i z e ( 0 ) ;

string suf = " tr " ;

if (! tr ) suf = " tst " ;

s t r i n g f o l d [ ] = {"MM/", "FM/", "MR/", "FR/" } ;

s t r i n g p = " data /" ;

s t r i n g supp = " 035 " ;

i f ( s u p p o r t == 2 ) supp = " 002 " ;

i f ( s u p p o r t == 5 ) supp = " 005 " ;

i f ( s u p p o r t == 1 0 ) supp = " 01 " ;

i f ( s u p p o r t == 3 0 ) supp = " 03 " ;

i f ( s u p p o r t == 2 0 ) supp = " 02 " ;

Context K;

f o r ( int i = 0 ;

i 4 ;

++i ) { s t r i n g d i r = p + f o l d [ i ] + "db. g r. f p. " + supp + "v a t t r s "+ s u f + "P" ;

r e a d (K, d i r ) ;

pK. push_back (K) ;

} f o r ( int i = 0 ;

i 4 ;

++i ) { s t r i n g d i r = p + f o l d [ i ] + "db. g r. f p. " + supp + "v a t t r s "+ s u f + "N" ;

r e a d (K, d i r ) ;

nK. push_back (K) ;

} int M = 0 ;

f o r ( int i = 0 ;

i pK. s i z e ( ) ;

++i ) { M = max(M, pK [ i ].M) ;

M = max(M, nK [ i ].M) ;

} f o r ( int i = 0 ;

i pK. s i z e ( ) ;

++i ) { pK [ i ].M = M;

nK [ i ].M = M;

} } mset c l o s u r e ( const v e c t o r Context& K, mset X) { bool updated = true ;

while ( updated ) { updated = f a l s e ;

f o r ( int i = 0 ;

i K. s i z e ( ) ;

++i ) { int s z = X. s i z e ( ) ;

X = K[ i ]. c l o s u r e (X) ;

i f (X. s i z e ( ) != s z ) updated = true ;

i f (X. s i z e ( ) == K[ i ].M) break ;

} i f (K. s i z e ( ) == 1 ) break ;

} return X;

} double s t a b i l i t y ( const mset& X, const Context& K) { int n = 5 0, r e t = 0 ;

mset s u b s e t ;

f o r ( int i t = 0 ;

i t n ;

++i t ) { rand_subset (X, 0. 5, s u b s e t ) ;

i f (K. c l o s u r e ( s u b s e t ) == X) ++r e t ;

} return ( double ) r e t / n ;

} mset n e x t _ c l o s u r e ( const mset& X, const v e c t o r Context& K) { int m = K [ 0 ].M;

f o r ( int i = m 1 ;

i = 0 ;

i ) { mset Y;

bool ok = true ;

f o r ( int j = 0 ;

j X. s i z e ( ) ;

++j ) { i f (X[ j ] == i ) { ok = f a l s e ;

break ;

} e l s e i f (X[ j ] i ) Y. push_back (X[ j ] ) ;

else break ;

} i f ( ok ) { Y. push_back ( i ) ;

Y = c l o s u r e (K, Y) ;

ok = true ;

int j = 0, k = 0 ;

while ( j X. s i z e ( ) && k Y. s i z e ( ) ) { i f (X[ j ] = i | | Y[ k ] = i ) break ;

i f (X[ j ] != Y[ k ] ) { ok = f a l s e ;

break ;

} ++j ;

++k ;

} i f ( j X. s i z e ( ) ) i f (X[ j ] i ) ok = f a l s e ;

i f ( k Y. s i z e ( ) ) i f (Y[ k ] i ) ok = f a l s e ;

i f ( ok ) return Y;

} } return X;

} void maximize ( v e c t o r mset& x, bool minimize = f a l s e ) { s o r t ( x. b e g i n ( ), x. end ( ) ) ;

int s z = 1 ;

f o r ( int i = 1 ;

i x. s i z e ( ) ;

++i ) { i f ( x [ i ] != x [ i 1 ] ) { x [ sz ] = x [ i ] ;

++s z ;

} } x. r e s i z e ( sz ) ;

sz = 0;

f o r ( int i = 0 ;

i x. s i z e ( ) ;

++i ) { bool ok = true ;

f o r ( int j = 0 ;

j x. s i z e ( ) ;

++j ) { i f ( ! minimize ) { i f ( j != i && i s _ s u b s e t ( x [ j ], x [ i ] ) ) { ok = f a l s e ;

break ;

} } else { i f ( j != i && i s _ s u b s e t ( x [ i ], x [ j ] ) ) { ok = f a l s e ;

break ;

} } } i f ( ok ) { x [ sz ] = x [ i ] ;

++s z ;

} } x. r e s i z e ( sz ) ;

} v e c t o r mset f i n d _ s h a r e d _ h y p o t h e s e s ( const v e c t o r Context& pK, const v e c t o r Context& nK) { v e c t o r mset r e t ;

v e c t o r mset neg ;

f o r ( int i = 0 ;

i nK. s i z e ( ) ;

++i ) { f o r ( int j = 0 ;

j nK [ i ]. o b j e c t s. s i z e ( ) ;

++j ) { neg. push_back (nK [ i ]. o b j e c t s [ j ] ) ;

} } maximize ( neg ) ;

mset X, nX ;

while ( ( nX = n e x t _ c l o s u r e (X, pK) ) != X) { X = nX ;

bool ok = true ;

f o r ( int j = 0 ;

j neg. s i z e ( ) ;

++j ) { i f ( i s _ s u b s e t ( neg [ j ], X) ) { ok = f a l s e ;

break ;

} } i f ( ok ) { r e t. push_back (X) ;

i f ( r e t. s i z e ( ) % 50 == 0 ) c o u t ". " ;

} } c o u t e n d l ;

return r e t ;

} mset next_closure_JSM ( const mset& X, const Context& K) { int m = K.M;

f o r ( int i = m 1 ;

i = 0 ;

i ) { mset Y;

bool ok = true ;

f o r ( int j = 0 ;

j X. s i z e ( ) ;

++j ) { i f (X[ j ] == i ) { ok = f a l s e ;

break ;

} e l s e i f (X[ j ] i ) Y. push_back (X[ j ] ) ;

else break ;

} i f ( ok ) { Y. push_back ( i ) ;

Y = K. c l o s u r e (Y) ;

ok = true ;

int j = 0, k = 0 ;

while ( j X. s i z e ( ) && k Y. s i z e ( ) ) { i f (X[ j ] = i | | Y[ k ] = i ) break ;

i f (X[ j ] != Y[ k ] ) { ok = f a l s e ;

break ;

} ++j ;

++k ;

} i f ( j X. s i z e ( ) ) i f (X[ j ] i ) ok = f a l s e ;

i f ( k Y. s i z e ( ) ) i f (Y[ k ] i ) ok = f a l s e ;

i f ( ok ) return Y;

} } return X;

} v e c t o r mset f i n d _ h y p o t h e s e s ( const Context& pK, const Context& nK, double stab_thr ) { v e c t o r mset r e t ;

v e c t o r mset neg ;

f o r ( int j = 0 ;

j nK. o b j e c t s. s i z e ( ) ;

++j ) { neg. push_back (nK. o b j e c t s [ j ] ) ;

} maximize ( neg ) ;

Context K, Kt ;

f o r ( int i = 0 ;

i neg. s i z e ( ) ;

++i ) K. o b j e c t s. push_back ( neg [ i ] ) ;

f o r ( int i = 0 ;

i pK. o b j e c t s. s i z e ( ) ;

++i ) K. o b j e c t s. push_back (pK. o b j e c t s [ i ] ) ;

K.M = pK.M;

int M = K.M;

Kt.M = K. o b j e c t s. s i z e ( ) ;

f o r ( int j = 0 ;

j M;

++j ) { Kt. o b j e c t s. push_back ( mset ( ) ) ;

} f o r ( int i = 0 ;

i K. o b j e c t s. s i z e ( ) ;

++i ) { f o r ( int j = 0 ;

j K. o b j e c t s [ i ]. s i z e ( ) ;

++j ) { int a = K. o b j e c t s [ i ] [ j ] ;

Kt. o b j e c t s [ a ]. push_back ( i ) ;

} } mset X, nX ;

while ( ( nX = next_closure_JSM (X, Kt ) ) != X) { X = nX ;

bool done = f a l s e ;

f o r ( int i = 0 ;

i X. s i z e ( ) ;

++i ) i f (X[ i ] neg. s i z e ( ) ) done = true ;

i f ( done ) break ;

mset Z ;

i f (X. s i z e ( ) 0 ) { Z = K. o b j e c t s [X [ 0 ] ] ;

f o r ( int i = 1 ;

i X. s i z e ( ) ;

++i ) Z = g e t _ i n t e r s e c t i o n ( Z, K. o b j e c t s [X[ i ]]) ;

} i f ( stab_thr 1 e5 | | s t a b i l i t y ( Z, K) stab_thr ) r e t. push_back (Z) ;

i f ( r e t. s i z e ( ) % 50 == 0 ) c o u t ". " ;

} c o u t e n d l ;

return r e t ;

} int c l a s s i f y ( const v e c t o r mset& pH, const v e c t o r mset& nH, const mset & X) { int pos = 0 ;

f o r ( int i = 0 ;

i pH. s i z e ( ) ;

++i ) i f ( i s _ s u b s e t (X, pH [ i ] ) ) ++pos ;

int neg = 0 ;

f o r ( int i = 0 ;

i nH. s i z e ( ) ;

++i ) i f ( i s _ s u b s e t (X, nH [ i ] ) ) ++neg ;

i f ( pos 0 && neg == 0 ) return 1 ;

i f ( neg 0 && pos == 0 ) return 1;

return 0 ;

} int main ( ) { // f r e o p e n (" o u t p u t. t x t ", "w", s t d o u t ) ;

const double s t a b i l i t y _ t h r e s h o l d = 0. 6 5 ;

const int s u p p o r t = 2 0 ;

v e c t o r Context pK, nK ;

r e a d _ a l l (pK, nK, true, s u p p o r t ) ;

v e c t o r mset pH, nH ;

pH = f i n d _ s h a r e d _ h y p o t h e s e s (pK, nK) ;

maximize (pH, true ) ;

nH = f i n d _ s h a r e d _ h y p o t h e s e s (nK, pK) ;

maximize (nH, true ) ;

c o u t "no n e g a t i v e h y p o t h e s e =" nH. s i z e ( ) e n d l ;

c o u t "no p o s i t i v e h y p o t h e s e =" pH. s i z e ( ) e n d l ;

v e c t o r Context tpK, tnK ;

r e a d _ a l l ( tpK, tnK, f a l s e, s u p p o r t ) ;

int t o t a l = 0 ;

int e r r o r = 0 ;

int mis = 0 ;

f o r ( int i = 0 ;

i tpK. s i z e ( ) ;

++i ) { f o r ( int j = 0 ;

j tpK [ i ]. o b j e c t s. s i z e ( ) ;

++j ) { int r e s = c l a s s i f y (pH, nH, tpK [ i ]. o b j e c t s [ j ] ) ;

i f ( r e s == 0 ) ++mis ;

i f ( r e s == 1) ++e r r o r ;

++t o t a l ;

} f o r ( int j = 0 ;

j tnK [ i ]. o b j e c t s. s i z e ( ) ;

++j ) { int r e s = c l a s s i f y (pH, nH, tnK [ i ]. o b j e c t s [ j ] ) ;

i f ( r e s == 0 ) ++mis ;

i f ( r e s == 1 ) ++e r r o r ;

++t o t a l ;

} } c o u t " t o t a l " t o t a l " e r r o r s =" e r r o r " mis se d = " mis e n d l ;

c o u t " c l a s s i c JSM==================\n" ;

total = 0;

error = 0;

mis = 0 ;

f o r ( int i = 0 ;

i pK. s i z e ( ) ;

++i ) { pH = f i n d _ h y p o t h e s e s (pK [ i ], nK [ i ], s t a b i l i t y _ t h r e s h o l d ) ;

maximize (pH, true ) ;

c o u t "no p o s i t i v e h y p o t h e s e [ " i " ] =" pH.

s i z e ( ) e n d l ;

nH = f i n d _ h y p o t h e s e s (nK [ i ], pK [ i ], s t a b i l i t y _ t h r e s h o l d ) ;

maximize (nH, true ) ;

c o u t "no n e g a t i v e h y p o t h e s e [ " i " ] =" nH.

s i z e ( ) e n d l ;

int c t o t a l = 0 ;

int c e r r o r = 0 ;

int cmis = 0 ;

f o r ( int j = 0 ;

j tpK [ i ]. o b j e c t s. s i z e ( ) ;

++j ) { int r e s = c l a s s i f y (pH, nH, tpK [ i ]. o b j e c t s [ j ] ) ;

i f ( r e s == 0 ) ++cmis ;

i f ( r e s == 1) ++c e r r o r ;

++c t o t a l ;

} f o r ( int j = 0 ;

j tnK [ i ]. o b j e c t s. s i z e ( ) ;

++j ) { int r e s = c l a s s i f y (pH, nH, tnK [ i ]. o b j e c t s [ j ] ) ;

i f ( r e s == 0 ) ++cmis ;

i f ( r e s == 1 ) ++c e r r o r ;

++c t o t a l ;

} c o u t " t o t a l " c t o t a l " e r r o r s =" c e r r o r " m is sed =" cmis "===\n" ;

t o t a l += c t o t a l ;

mis += cmis ;

e r r o r += c e r r o r ;

} c o u t " t o t a l " t o t a l " e r r o r s =" e r r o r " mis se d = " mis e n d l ;

return 0 ;

}

Pages:     | 1 | 2 ||
 
 >>  ()





 
<<     |    
2013 www.libed.ru - -

, .
, , , , 1-2 .