OKlibrary  0.2.1.6
MaintainingBound.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 20.6.2009 (Swansea) */
00002 /* Copyright 2009, 2010, 2011 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/Satisfiability/Lisp/ClauseSets/Statistics.mac")$
00026 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/Transversals/Basics.mac")$
00027 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/Statistics.mac")$
00028 
00029 
00030 /* *************************************
00031    * Finding size-bounded transversals *
00032    *************************************
00033 */
00034 
00035 /* Computing a list of transversals of length at most B of a list L of sets,
00036    via branching on vertices (note that transversals don't need to be
00037    minimal). All inclusion-minimal transversals are listed; a non-minimal
00038    transversal is left out iff on its associated branch in
00039    the search tree it happens that one occurring vertex completely disappears
00040    as a result of removing all hyperedges containing some (other) vertex.
00041    If B is the transversal number of L, then (thus) exactly all transversals
00042    of minimum length are found.
00043 */
00044 /* Prerequisite: B is a natural number >= 0. */
00045 /* RENAME: transversals_bv (for branching on "vertices", not just on
00046    "elements"); perhaps also "set system" should be in the name (as "ses").
00047 */
00048 transversals_be(L,B) := if emptyp(L) then [{}]
00049  elseif empty_element_p(L) then []
00050  elseif B=0 then [] 
00051  elseif B=1 then create_list({x},x,listify(lintersection(L))) else
00052  block([a : first_element(first(L))],
00053    return(append(
00054     add_element_l(a,transversals_be(remove_with_element_l(L,a),B-1)),
00055     transversals_be(setdifference2e(L,a),B))))$
00056 
00057 /* The variation where L is kept sorted in ascending order by length (so that
00058    the empty clause and unit-clauses are easily detected):
00059 */
00060 /* RENAME: transversals_bvs (possibly transversals_bvs_ses) */
00061 transversals_bes(L,B) := transversals_bes_(sort_length(L),B)$
00062 transversals_bes_(L,B) := if emptyp(L) then [{}]
00063  else block([H : first(L)],
00064   if emptyp(H) or B=0 then return([]),
00065   if B=1 then return(create_list({x},x,listify(lintersection(L)))),
00066   block([a : first_element(H)],
00067    if length(H) = 1 then
00068      return(add_element_l(a,transversals_bes_(remove_with_element_l(L,a),B-1)))
00069    else
00070      return(append(
00071       add_element_l(a,transversals_bes_(remove_with_element_l(L,a),B-1)),
00072       transversals_bes_(sort_length(setdifference2e(L,a)),B)))))$
00073 
00074 
00075 /* ********************************
00076    * Finding minimum transversals *
00077    ********************************
00078 */
00079 
00080 /* Here we consider the applications of the the previous algorithms. */
00081 
00082 /* Given a hypergraph G without empty hyperedge and a (known) 
00083    lower bound lb on the size of a minimum transversal, compute the list of
00084    minimum transversals by using B = lb, B+1, ...
00085 */
00086 minimum_transversals_lbbvs_hg(G,lb) := block(
00087  [L : sort_length(listify(G[2])), M],
00088   if oklib_monitor then 
00089     print("minimum_transversals_lbbvs_hg: ", length(lunion(L)), length(L), lb),
00090   M : transversals_bes(L,lb),
00091   while emptyp(M) do (
00092     if oklib_monitor then printf(true,"~d ",lb),
00093     lb : lb + 1, M : transversals_bes(L,lb)
00094   ),
00095   if oklib_monitor then printf(true,"~%"),
00096   return(M))$
00097 minimum_transversals_bvs_hg(G) := minimum_transversals_lbbvs_hg(G,0)$
00098 
00099 /* The "decomposed list of all minimum transversals" of a hypergraph G is the
00100    list L of hypergraphs of minimum transversals of disjoint_union_rep_hg(G).
00101    Prerequisite: G does not contain the empty hyperedge.
00102 */
00103 decomp_minimum_transversals_bvs_hg(G) := block([D : disjoint_union_rep_hg(G)],
00104  map("[", map(first,D), map(setify,map(minimum_transversals_bvs_hg, D))))$
00105 /* Extracting the number of minimum transversals of the components: */
00106 extract_num_minimum_transversals_decomp(L) := map(nhyp_hg,L)$
00107 /* Extracting the size of minimum transversals of the components: */
00108 extract_size_minimum_transversals_decomp(L) := 
00109  map(lambda([G],length(choose_element(G[2]))), L)$
00110 /* The size, total number of minimum transversals, and the number of
00111    connected components, computed using decomposition:
00112 */
00113 stat_minimum_transversals_bvsdecomp_hg(G) := block(
00114  [T : decomp_minimum_transversals_bvs_hg(G)],
00115   [sum_l(extract_size_minimum_transversals_decomp(T)),
00116    prod_l(extract_num_minimum_transversals_decomp(T)),
00117    length(T)])$
00118 /* Extracting the set of minimum transversals from the decomposed list: */
00119 extract_minimum_transversals_decomp(L) :=
00120  map(lunion,uaapply(cartesian_product, map(second,L)))$
00121 /* Computing the set of all minimum transversals, using decomposition: */
00122 minimum_transversals_bvsdecomp_hg(G) :=
00123  extract_minimum_transversals_decomp(decomp_minimum_transversals_bvs_hg(G))$
00124    
00125 /* For the hypergraph generator gen_(n), applied to n = 1, ..., N, compute
00126    via stat_minimum_transversals_bvsdecomp_hg the transversal number, the
00127    number of minimum transversals, and the number of connected components, and
00128    store them together with n, the number of vertices and the number of
00129    hyperedges in the list L (which needs to be passed unevaluated).
00130    In case the hyperedge-set changes from n to n+1, these numbers are also
00131    printed out. L is not initialised, and results are appended to the
00132    beginning. So L should be normally be initialised to [], and reading off
00133    the results happens via reverse(L).
00134    For the correct computation of the number of connected components it is
00135    assumed, that the vertex-sets weakly monotonically increase with n.
00136 */
00137 minimum_transversals_decomp_gen(N,gen_, _L) := block(
00138  [G0 : [false,false], nver, nhyp, s, add],
00139   for n : 1 thru N do block([G1 : gen_(n)],
00140     if G1[2] # G0[2] then (
00141       s : stat_minimum_transversals_bvsdecomp_hg(G1),
00142       nver : nver_hg(G1), nhyp : nhyp_hg(G1), add : 0,
00143       print(n, nver, nhyp, s)
00144     )
00145     else block([new_nver : nver_hg(G1)],
00146       add : add + new_nver - nver, nver : new_nver
00147     ),
00148     _L :: cons([n, nver, nhyp, [s[1],s[2],s[3]+add]], ev(_L)),
00149     G0 : G1
00150   ),
00151   N)$
00152 /* Remark: This form of computation is especially appropriate if the
00153    hypergraphs are "sparse", and decompose into relatively small components.
00154 */
00155 
00156 
00157 /* *********************************
00158    * Monotone hypergraph sequences *
00159    *********************************
00160 */
00161 
00162 /* Given a monoton hypergraph generator mongen(n) (monoton w.r.t.
00163    the hyperedge sets), such that MT0 is a non-empty list of (all) the minimum
00164    transversals of mongen(0), and where mongen(n+1) has (exactly) one node
00165    more than mongen(n), and this node occurs in all new edges, compute the
00166    list of lists of (all) minimum transversals for n = 0, ..., N.
00167    The algorithm uses the set of (all) minimum transversals from the previous
00168    step in the obvious way.
00169 */
00170 minimum_transversals_mongen(N,mongen_,MT0) := 
00171  block([L : [MT0], t : length(first(MT0)), G0 : mongen_(0)],
00172   for n : 1 thru N do block(
00173   [G1 : mongen_(n), E, MT1],
00174    E : setdifference(G1[2], G0[2]),
00175    MT1 : sublist(MT0, lambda([T],transversal_p(T, E))),
00176    if emptyp(MT1) then block(
00177     [a : single_element(setdifference(G1[1],G0[1]))],
00178      t : t + 1,
00179      MT1 : append(
00180        add_element_l(a,MT0),
00181        transversals_bes(sort_length(listify(setdifference2e(G1[2],a))),t))),
00182    if oklib_monitor then print(n,t,length(MT1)),
00183    L : cons(MT1,L),
00184    MT0 : MT1, G0 : G1
00185   ),
00186   return(reverse(L)))$
00187 
00188 
00189 /* *********************************
00190    * Stratification of hypergraphs *
00191    *********************************
00192 */
00193 
00194 /* Computing the set of minimum transversals of a hypergraph G through
00195    stratification via the list L of vertices.
00196    Note that an empty hyperedge in G is ignored.
00197 */
00198 minimum_transversals_stratabvs_hg(G,L) :=
00199  block([mongen : hg2hgmongen(G,L), MT0 : [{}], G0 : [{},{}], t : 0],
00200   for n : 1 thru length(L) do block(
00201   [G1 : mongen(n), E, MT1],
00202    E : setdifference(G1[2], G0[2]),
00203    MT1 : sublist(MT0, lambda([T],transversal_p(T, E))),
00204    if emptyp(MT1) then block(
00205     [a : single_element(setdifference(G1[1],G0[1]))],
00206      t : t + 1,
00207      MT1 : append(
00208        add_element_l(a,MT0),
00209        transversals_bes(sort_length(listify(setdifference2e(G1[2],a))),t))
00210    ),
00211    MT0 : MT1, G0 : G1
00212   ),
00213   MT0)$
00214 /* Using the given order of vertices: */
00215 minimum_transversals_stratabvs_ohg(G) :=
00216  minimum_transversals_stratabvs_hg(ohg2hg(G),G[1])$
00217 
00218 /* Heuristics: Using vertex degrees (highest first). */
00219 minimum_transversals_stratavdegbvs_hg(G) :=
00220  minimum_transversals_stratabvs_hg(G, map(first,sorted_vertex_degrees_hg(G)))$
00221 minimum_transversals_stratavdegbvs_ohg(G) :=
00222  minimum_transversals_stratabvs_hg(G, map(first,sorted_vertex_degrees_ohg(G)))$
00223 
00224