OKlibrary  0.2.1.6
Basics.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 2.2.2008 (Swansea) */
00002 /* Copyright 2008, 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/Satisfiability/Lisp/ClauseSets/Statistics.mac")$
00026 
00027 
00028 /* Checking whether T is a transversal for set system S (S may be also
00029    a list of sets).
00030    Note that T doesn't need to be minimal.
00031 */
00032 transversal_p(T,S) := every_s(lambda([H], not disjointp(H,T)), S)$
00033 /* Checking for an exact transversal: */
00034 etransversal_p(T,S) := every_s(lambda([H], is(length(intersection(H,T))=1)), S)$
00035 
00036 
00037 /* ************************
00038    * Greedy approximation *
00039    ************************
00040 */
00041 
00042 /* Finding a "small" transversal by the obvious greedy approach;
00043    outputs false iff there is no transversal.
00044 */
00045 greedy_transversal_ohg(G) :=
00046  if empty_element_p(G[2]) then false else greedy_transversal_(G[2])$
00047 /* For a list S of sets not containing the empty set: */
00048 greedy_transversal_(S) := if emptyp(S) then {} else
00049  block([x : max_literal_degree_l_cl(S)[2]],
00050   adjoin(x, greedy_transversal_(remove_with_element_l(S,x))))$
00051 
00052