OKlibrary  0.2.1.6
Heuristics.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 20.5.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/Graphs/Lisp/Basic.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/Graphs/Lisp/Bicliques/BasicNotions.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")$
00025 
00026 
00027 /* *********************
00028    * Greedy approaches *
00029    *********************
00030 */
00031 
00032 /* G is a graph with loops, and returned is a biclique partition composed 
00033    purely of maximal bicliques:
00034 */
00035 greedy_bcp_gl(G) := block([listB : [], restE : G[2], restG : G],
00036   while not(emptyp(restE)) do block(
00037    [B : [{first_element(first_element(restG[2]))},{second_element(first_element(restG[2]))}], newMB],
00038     newMB : maximal_bc_gl(B,restG),
00039     listB : cons(newMB,listB),
00040     restE : setdifference(restE,map(setify,cartesian_product(newMB[1],newMB[2]))),
00041     restG : [lunion(restE),restE]
00042   ),
00043   return(reverse(listB)))$
00044