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
```