You selected matroid2022.pl
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% simulating matoroid
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% matroid2022.pl
% 11 Jan 2022
% By Kenryo Indo

% index function for list members
%----------------------------------------------------------------
% from menu.pl(27 Aug 2006)

list_projection( [ ], [ ], [ ]).
list_projection( [ 0 | A ], [ _ | Y ], Z ):-
	 list_projection( A, Y, Z ).
list_projection( [ 1 | A ], [ X | Y ], [ X | Z ] ):-
	 list_projection( A, Y, Z ).

% alias: selecting members from a list with index label
%----------------------------------------------------------------

group( Gid, L, G ):-
	 \+ var( L ),
	 list_projection( X, L, G ),
	 atomic_list_concat( X, Gid ).

% list equivalence as a set (e.g., same_members/2 of SWI-prolog)
%----------------------------------------------------------------

are_same_members( W, Z ):-
	 subset( W, Z ),
	 subset( Z, W ).

% recursive function in a generic form
%----------------------------------------------------------------
% from icaart2014c.pl(30 Dec 2013, 4 Feb 2014) with a modification

function( [ ], [ ], _).

function( [ Y | F ], [ X | D ], Axiom ):- 
	 function( F, D, Axiom ),
	 atomic( Axiom ),
	 Goal =.. [ Axiom, X, F, Y ],
	 call( Goal ).

function( [ Y | F ], [ X | D ], Axiom ):- 
	 function( F, D, Axiom ),
	 Axiom =.. [ Functor, P ],
	 Goal =.. [ Functor, X, F, Y, P ],
	 call( Goal ).

% a utility for showing members list
%----------------------------------------------------------------
	 
concatenate_for_each_list_of_members( F, T ):-
	 findall( P, ( 
		 member( X, F ), 
		 ( 
			 X = [ ]
		 ->	 P='null' 
		 ;	 atomic_list_concat( X, P ) 
	 	 ) 
	 ), T ). 

% Logical implication: If _ then _
%----------------------------------------------------------------

:- op( 1050, xfy, ==> ). 

A ==> B:-
	 \+ ( call( A ), \+ call( B ) ).

/*

?- A = (a, v ==> c,d), A=..B.
A =  (a, v==>c, d),
B = [==>,  (a, v),  (c, d)].

*/


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% hypergraph
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

axiom_of_hypergraph( X, _, X->Y, S ):-
	 group( _, S, Y ),
	 member( X, Y ).
	 
hypergraph( S, F ):-
	 function(
		 F, 
		 S, 
		 axiom_of_hypergraph( S )
	 ).

hypergraph( F ):-
	 hypergraph( [ a, b, c ], F ).

/*

?- hypergraph( F ), F = [ a->[ a ] | _ ], writeln( F ), fail.
[(a->[a]),(b->[b]),(c->[c])]
[(a->[a]),(b->[b,c]),(c->[c])]
[(a->[a]),(b->[a,b]),(c->[c])]
[(a->[a]),(b->[a,b,c]),(c->[c])]
[(a->[a]),(b->[b]),(c->[b,c])]
[(a->[a]),(b->[b,c]),(c->[b,c])]
[(a->[a]),(b->[a,b]),(c->[b,c])]
[(a->[a]),(b->[a,b,c]),(c->[b,c])]
[(a->[a]),(b->[b]),(c->[a,c])]
[(a->[a]),(b->[b,c]),(c->[a,c])]
[(a->[a]),(b->[a,b]),(c->[a,c])]
[(a->[a]),(b->[a,b,c]),(c->[a,c])]
[(a->[a]),(b->[b]),(c->[a,b,c])]
[(a->[a]),(b->[b,c]),(c->[a,b,c])]
[(a->[a]),(b->[a,b]),(c->[a,b,c])]
[(a->[a]),(b->[a,b,c]),(c->[a,b,c])]
false.

*/


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Family of subsets
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

power_set( S, D ):-
	 findall( A, group( _, S, A ), D ).

family_of_subsets( I, S, F ):-
	 power_set( S, D ), 
	 list_projection( I, D, F ).


/*

?- family_of_subsets( I, [x,y,z], F ), violation_of_closedness( upward, F, V ).
I = [0, 0, 0, 0, 0, 1, 1, 0],
F = [[x, z], [x, y]],
V = union([x, z], [x, y], [z, x, y]) ;
I = [0, 0, 0, 0, 0, 1, 1, 0],
F = [[x, z], [x, y]],
V = union([x, y], [x, z], [y, x, z]) .

?- family_of_subsets( I, [x,y,z], F ), \+ violation_of_closedness( _, F, _ ).
I = [0, 0, 0, 0, 0, 0, 0, 0],
F = [] ;
I = [0, 0, 0, 0, 0, 0, 0, 1],
F = [[x, y, z]] ;
I = [0, 0, 0, 0, 0, 0, 1, 0],
F = [[x, y]] ;
I = [0, 0, 0, 0, 0, 0, 1, 1],
F = [[x, y], [x, y, z]] ;
...

?- findall( 1, (family_of_subsets( I, [x,y,z], F ), \+ violation_of_closedness( _, F, _ )), L ), length( L, N).
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],
N = 90.

?- S=[x,y,z], findall( 1, (family_of_subsets( I, S, F ), \+ violation_of_closedness( _, F, _ ), subset( [[],S], F )), L ), length( L, N).
S = [x, y, z],
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],
N = 29.

*/


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Matroid : Generation-and-test rule
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
/* def. matroid (independent set axiom)
1. The empty set is independent.
2. The downward-closedness (or heriditary);
3. The augmentation property (or the exchange axiom );
*/

'1. The empty set is independent.'( F ):-
	 member( [ ], F ).

'2. The downward-closedness.'( F ):-
	 member( X, F ),
	 group( _, X, Y )
	 ==> 
	 member( Y, F ).
	 % i.e., Every subset of an independent set is independent 

'3. The augmentation property.'( F ):-
	% i.e., 
	 'A and B are two independent sets'( A, B, F ), 
	 'A has more elements than B'( A, B )
	 ==> 
	 'There exists x in A-B such that B U {x} is independent.'( A, B, _, F ).

'A and B are two independent sets'( A, B, F ):-
	 member( A, F ),
	 member( B, F ).
%	 subset( [ A, B ], F ).  % not generative

'A has more elements than B'( A, B ):-
	 subset( B, A ),
	 \+ subtract( A, B, [ ] ).

'There exists x in A-B such that B U {x} is independent.'( A, B, X, F ):-
	 subtract( A, B, C ),
	 member( X, C ),
	 union( B, [ X ], U ),
	 member( U1, F ),
	 are_same_members( U, U1 ).

default_base_set_if_needed( S ):-
	 var( S )
	 ->	 S = [a,b,c] 
	 ;	 true.

'1. The empty set is independent.'( F, C ):-
	 ( '1. The empty set is independent.'( F ) -> C = 1 ; C = 0 ).

'2. The downward-closedness.'( F, C ):-
	 ( '2. The downward-closedness.'( F ) -> C = 1 ; C = 0 ).

'3. The augmentation property.'( F, C ):-
	 ( '3. The augmentation property.'( F ) -> C = 1 ; C = 0 ).

simulating_matroid( S, F, T, C ):-
	 default_base_set_if_needed( S ),
	 family_of_subsets( _, S, F ),
	 '1. The empty set is independent.'( F, C1 ),
	 '2. The downward-closedness.'( F, C2 ),
	 '3. The augmentation property.'( F, C3 ),
	 C = [ C1, C2, C3 ],
	 concatenate_for_each_list_of_members( F, T ).

simulating_matroid( S, F, T ):-
	 simulating_matroid( S, F, T, [ 1, 1, 1 ] ).
	 
simulating_matroid( S, F ):-
	 simulating_matroid( S, F, _ ).

/*

?- simulating_matroid( [a,b], F ).
F = [[]] ;
F = [[], [a]] ;
F = [[], [b]] ;
F = [[], [b], [a]] ;
F = [[], [b], [a], [a, b]].

?- S=[a,b], family_of_subsets( I, S, F ), simulating_matroid( S, F, T, C ), C \=[1,1,1], nl, write( C:F ), fail.

[0,1,1]:[]
[0,0,1]:[[a,b]]
[0,0,1]:[[a]]
[0,0,1]:[[a],[a,b]]
[0,0,1]:[[b]]
[0,0,1]:[[b],[a,b]]
[0,0,1]:[[b],[a]]
[0,0,1]:[[b],[a],[a,b]]
[1,0,0]:[[],[a,b]]
[1,0,1]:[[],[a],[a,b]]
[1,0,1]:[[],[b],[a,b]]
false.

?- S=[a,b], family_of_subsets( I, S, F ), simulating_matroid( S, F, T, C ), C =[1,1,0], 'A and B are two independent sets'( A, B, F ), 'A has more elements than B'( A, B ), \+ 'There exists x in A-B such that B U {x} is independent.'( A, B, X, F ).
false.

?- S=[a,b], findall( T, simulating_matroid( S, _, T ), L ), nth1(J, L, T ), nl, write( J : T ), fail.

1:[null]
2:[null,a]
3:[null,b]
4:[null,b,a]
5:[null,b,a,ab]
false.


?- S=[a,b,c], findall( T, simulating_matroid( S, _, T ), L ), nth1(J, L, T ), nl, write( J : T ), fail.

1:[null]
2:[null,a]
3:[null,b]
4:[null,b,a]
5:[null,b,a,ab]
6:[null,c]
7:[null,c,a]
8:[null,c,a,ac]
9:[null,c,b]
10:[null,c,b,a]
11:[null,c,b,a,ab]
12:[null,c,b,a,ac]
13:[null,c,b,a,ac,ab]
14:[null,c,b,bc]
15:[null,c,b,bc,a]
16:[null,c,b,bc,a,ab]
17:[null,c,b,bc,a,ac]
18:[null,c,b,bc,a,ac,ab]
19:[null,c,b,bc,a,ac,ab,abc]
false.

*/

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Matroid : A recursiive construction
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

list_of_checked_members( F, L ):-
	 findall( Y, member( Y -> _, F ), L ).

list_selected_members( F, H ):-
	 findall( Y, member( Y -> 1, F ), H ).

hemi_violation_of_matroid( 'no empty set', [ ] -> 0,  _ ) .

hemi_violation_of_matroid( 'not downward-closed', X -> 1, F ) :-
	 group( _, X, Y ),
	 member( Z -> 0, F ),
	 are_same_members( Z, Y ).

hemi_violation_of_matroid( 'not downward-closed', X -> 0, F ) :-
	 member( G -> 1, F ),
	 group( _, G, H ),
	 are_same_members( H, X ).

hemi_violation_of_matroid( 'no augmentation property', U -> 1, F ) :-
	 member( V -> 1, F ), 
	 member( [ A, B ], [ [ U, V ], [ V, U ] ] ), 
	 'A has more elements than B'( A, B ),
	 list_selected_members( F, H ), 
	 (
		 'There exists x in A-B such that B U {x} is independent.'( A, B, X, H )
	 ==>
		 member( Z -> 0, F ),
		 are_same_members( Z, [ X | B ] )
	 ). 

hemi_violation_of_matroid( 'no augmentation property', X -> 0, F ) :-
	 member( A -> 1, F ), 
	 member( B -> 1, F ), 
	 'A has more elements than B'( A, B ),
	 list_selected_members( F, H ), 
	 (
		 'There exists x in A-B such that B U {x} is independent.'( A, B, Y, H )
	 ==>
		 are_same_members( [ Y | B ], X )
	 ). 

axiom_of_matroid( X, F, X -> V ):-
	 member( V, [ 0, 1 ] ),
	 \+ hemi_violation_of_matroid( _, X -> V, F ).

matroid( S, F, T ):-
	 power_set( S, D ), 
	 function(
		 F, 
		 D, 
		 axiom_of_matroid
	 ),
	 list_selected_members( F, T ).

matroid( S, T ):-
	 matroid( S, _, T ).


/*

?- S=[a,b], findall( T, matroid( S, _, T ), L ), nth1(J, L, T ), nl, write( J : T ), fail.

1:[[]]
2:[[],[b]]
3:[[],[a]]
4:[[],[b],[a]]
5:[[],[b],[a],[a,b]]
false.

% comparison

?- S=[a,b], findall( T, simulating_matroid( S, T, _ ), L ), nth1(J, L, T ), nl, write( J : T ), fail.

1:[[]]
2:[[],[a]]
3:[[],[b]]
4:[[],[b],[a]]
5:[[],[b],[a],[a,b]]
false.

?- S=[a,b], matroid( S, F, T ), member(V, F ), hemi_violation_of_matroid( A, V, F ).
false.


?- S = [a,b,c], findall( 1, (matroid( S, T )), L ), length( L, N ).
S = [a, b, c],
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],
N = 19.

?- S = [a,b,c], matroid( S, T ),  \+ simulating_matroid( S, T ).
false.

?- S = [a,b,c], simulating_matroid( S, T ), \+ matroid( S, T ).
false.

*/



%%% end of program



return to front page.