Sampling Inspired by Group Hyperedge Testing (SIGHT)

A bare-bones implementation of the 'Sampling Inspired by Group Hyperedge Testing' (SIGHT) algorithm for finding a defective set.

This is a bare-bones implementation of the 'Sampling Inspired by Group Hyperedge Testing' (SIGHT) algorithm for finding a defective set from a universal set of N elements in log(N) trials. Multiple calls to this function comprise statistically independent trials.

Included with the algorithm implementation are a dummy fitness function and 'defective sets' to test the algorithm. See the accompanying algorithm, Random Chemistry (RC), which can also be used to find defective sets in log(N) trials. RC uses the same dummy fitness function and defective sets, for easy comparison, and is available on the File Exchange at: https://www.mathworks.com/matlabcentral/fileexchange/72720-random-chemistry-rc. Both algorithms have been successfully applied to identify small sets of transmission lines whose simultaneous failures cause cascading blackouts in power grid simulations (see reference below).

DISCLAIMER: This implementation is designed to be easy to read and understand, but is NOT optimized for efficiency and omits all the book-keeping and options under development that are contained in our working code. This should really be viewed as readable pseudo-code that runs.

COPYRIGHT: Laurence A. Clarfeld and Margaret J. Eppstein, Department of Computer Science, Univ. of Vermont
DATE: 8/26/2019

You are free to use or modify this code for research purposes, as long as you reference the website where you obtained the code.
IF YOU PUBLISH ANYTHING USING THIS CODE OR ALGORITHM, PLEASE REFERENCE THE FOLLOWING PAPER:
Clarfeld, L.A., and Eppstein, M.J. "Group-Testing on Hypergraphs with Variable-Cost Tests: A Power Systems Case Study", arXiv:1909.04513 [physics.soc-ph] (Preprint). September 9, 2019. Available from: https://arxiv.org/abs/1909.04513