OKlibrary  0.2.1.6
RecursiveSplitting.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 20.6.2009 (Swansea) */
00002 /* Copyright 2009 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00022 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/Basics.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/Transversals/Basics.mac")$
00026 
00027 
00028 /* ************************************
00029    * Finding all minimal transversals *
00030    ************************************
00031 */
00032 
00033 /* The transversal hypergraph via the independence hypergraph: */
00034 /* RENAME: transversal_hg_ind */
00035 transversal_hyp_ind(G, Ind) := ecomp_hyp(Ind(G))$
00036 transversal_hg_ind(G, Ind) := transversal_hyp_ind(G, Ind)$
00037 
00038 /* The transversal hypergraph of a hypergraph G, via recursive splitting: */
00039 /* RENAME: transversal_hg_rs */
00040 transversal_hyp_rs(G) := [G[1],transversal_ses_rs(min_elements(G[2]))]$
00041 transversal_hg_rs(G) := transversal_hyp_rs(G)$
00042 /* The transversal hypergraph of a set-system S: */
00043 transversal_ses_rs(S) := block([M : listify(S),l, h,S1,S2],
00044  l : length(M),
00045  if l = 0 then return({{}})
00046  elseif l = 1 then return(singletons(M[1]))
00047  elseif l = 2 then return(block([I : intersection(M[1],M[2])],
00048   union(singletons(I), 
00049         upairs(setdifference(M[1],I), setdifference(M[2],I))))),
00050  h : floor(l/2),
00051  S1 : rest(M,-h),
00052  S2 : rest(M,l-h),
00053  return(min_elements(cunion(transversal_ses_rs(S1),transversal_ses_rs(S2)))))$
00054 
00055 /* Given a monoton hypergraph generator mongen(n) (monoton w.r.t. the
00056    hyperedge sets), where mongen(n+1) has (exactly) one node more than
00057    mongen(n), and this node occurs in all new edges, compute the
00058    list of (repetition-free, complete) transversal lists for n = n_0, ..., N.
00059    Prerequisite: T0 is a list of all transversals of mongen(n_0).
00060 */
00061 transversals_mongen_rs_init(N,mongen_,n0,T0) := 
00062  block([G0 : mongen_(n0), res : [T0]],
00063   for n : n0+1 thru N do block(
00064   [G1 : mongen_(n), E, T1a : [], T1b, T1c : [], Td : [], T1, newv],
00065    E : setdifference(G1[2], G0[2]),
00066    [T1a, Td] : partition_list_epo(T0, lambda([H], transversal_p(H,E))),
00067    newv : single_element(setdifference(G1[1],G0[1])),
00068    T1b : add_element_l(newv, Td),
00069    E : setdifference2e(E, newv),
00070    for H in Td do block([Ed : subset(E, lambda([e],disjointp(e,H))), Tr],
00071      Tr : listify(transversal_ses_rs(setdifference2(Ed,H))),
00072      T1c : append(T1c, add_elements_l(H,Tr))
00073    ),
00074    T1 : append(T1b,listify(min_elements(append(T1a,T1c)))),
00075    if oklib_monitor then print(n,length(T1)),
00076    res : cons(T1,res),
00077    T0 : T1, G0 : G1
00078   ),
00079   return(reverse(res)))$
00080 transversals_mongen_rs(N,mongen_) := 
00081   transversals_mongen_rs_init(N,mongen_,0,listify(transversal_ses_rs(mongen_(0)[2])))$
00082 
00083