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.