AlanDeniseEricLauren: Find the minimal subset/submap satisfying some property.

[ algorithms, bsd3, library ] [ Propose Tags ] [ Report a vulnerability ]

Find the minimal subset/submap satisfying some arbitrary property.


[Skip to Readme]

Modules

  • ADEL

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.1.0.0, 0.1.0.1
Dependencies base (>=4.8.2.0 && <4.9), containers (>=0.5.6.2 && <0.6), MonadRandom (>=0.4.2.3 && <0.5), mtl (>=2.2.1 && <2.3), random (>=1.1 && <1.2), random-shuffle (>=0.0.4 && <0.1), vector (>=0.11.0.0 && <0.12) [details]
License BSD-3-Clause
Copyright 2016 Echo Nolan
Author Echo Nolan
Maintainer echo@echonolan.net
Category Algorithms
Home page http://github.com/enolan/AlanDeniseEricLauren
Uploaded by EchoNolan at 2016-08-24T06:15:53Z
Distributions
Reverse Dependencies 1 direct, 0 indirect [details]
Downloads 2000 total (5 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs not available [build log]
All reported builds failed as of 2016-10-24 [all 11 reports]

Readme for AlanDeniseEricLauren-0.1.0.1

[back to package description]

AlanDeniseEricLauren is an implementation of the ADEL algorithm for efficiently finding the minimal subset of an input set satisfying some arbitrary upward-closed property. "Upward-closed" means if the property is true of some set S it is true of all supersets of S. My implementation is trivially extended to maps (dictionaries).

This can be used for e.g. narrowing down bugs by finding the minimal subset of a complex failing test case that still exhibits the issue. In addition, I provide a method for finding the minimal set of changes between a known-good and known-bad example needed to trigger a bug. (Equivalently, a set where the property is false and a set where it's true.)

The ADEL algorithm is due to Philippe Laborie in his paper "An Optimal Iterative Algorithm for Extracting MUCs in a Black-box Constraint Network" published in ECAI 2014. doi:10.3233/978-1-61499-419-0-1051. The paper is available at http://ebooks.iospress.nl/publication/37115.

The project's homepage is https://github.com/enolan/AlanDeniseEricLauren. Bug reports and PRs can be submitted there.

As of August 2016, I am looking for work. If your company needs a good programmer, my email is echo@echonolan.net. My resume is available here.