(*
The inputs to the program are two arrays: neighbors and threshold.
neighbors[i] is the set of neighbors of person i (people who send
information to person i) and threshold[i] is person i's threshold.
The function g[set] returns the people who revolt assuming that no
one outside the set revolts. g[set] results from applying the function
f on set repeatedly, eliminating people in succession, until a fixed
point is reached.
The heart of the program is function f. Given a set, f selects the
people in the set which satisfy the following criterion: if the set is
a subset of the person's neighbors, then the person is selected if the
number of people in the set is greater than the person's threshold; if
the set is not a subset of the person's neighbors, then the person is
selected if the number of people who revolt in the intersection of the set
and the person's neighbors is greater than the person's threshold.
Note that function f is defined iteratively in that it depends on
function g, which in turn depends on function f, etc. As the code is
written, no intermediate values of f and g are "stored", which makes
things slow for larger examples, but it is simple to change this.
To get the final result, one simply evaluates g on the set of everyone.
*)
f[set_] := Select[set,
If[SubsetQ[neighbors[#], set], Length[set] >= threshold[#],
Length[g[Intersection[set, neighbors[#]]]] >= threshold[#]] &];
g[set_] := FixedPoint[f, set];
(*kite*)
neighbors[1] = {1, 2, 3};
neighbors[2] = {1, 2, 3};
neighbors[3] = {1, 2, 3};
neighbors[4] = {3, 4};
threshold[1] = 3;
threshold[2] = 3;
threshold[3] = 3;
threshold[4] = 3;
g[{1, 2, 3, 4}]
{1, 2, 3}
(*square*)
neighbors[1] = {1, 2, 4};
neighbors[2] = {1, 2, 3};
neighbors[3] = {2, 3, 4};
neighbors[4] = {3, 4, 1};
threshold[1] = 3;
threshold[2] = 3;
threshold[3] = 3;
threshold[4] = 3;
g[{1, 2, 3, 4}]
{}
