greedy set cover algorithm

Question

So, I picked up this code from

How do I make my implementation of greedy set cover faster?

I am trying to understand sets and set cover so, I modify this a bit.

U = set([1,2,3,4])
R = U
S = [set([1,2]), 
     set([1]), 
     set([1,2,3]), 
     set([1]), 
     set([3]), 
     set([1,2]), 
     set([3]), 
     set([1,2,3])]
w = [1, 1, 1, 1, 1, 1, 1, 1]

C = []
costs = []

def findMin(S, R):
    minCost = 99999.0
    minElement = -1
    for i, s in enumerate(S):
        try:
            cost = w[i]/(len(s.intersection(R)))
            if cost < minCost:
                minCost = cost
                minElement = i
        except:
            # Division by zero, ignore
            pass
    return S[minElement], w[minElement]

while len(R) != 0:
    S_i, cost = findMin(S, R)
    C.append(S_i)
    R = R.difference(S_i)
    costs.append(cost)

print "Cover: ", C
#print "Total Cost: ", sum(costs), costs

As can be seen U has values 1,2,3,4. None of the sets have 4 in them. I don't understands weights, so have put them as 1.

Expected output: set([1,2]), set([3]), set([1,2,3]), or Something which covers the maximum available.

No output, it goes into an infinite loop. – Omair . Sep 19 '13 at 12:28 — Omair ., Sep 19 '13 at 12:28

score 1 · Accepted Answer · answered Sep 19 '13 at 12:16

The problem with your code is that there is no cover, because there's an extra 4. My understanding is that by definition, the set cover problem specifies that the union of all sets in S must be equal to U. So that extra 4 shouldn't be there.

Since your program doesn't halt until it finds a perfect cover (i.e. as long as len(R) != 0) it will never halt on this input. You're passing invalid input to the algorithm.

On a side note, I would strongly recommend against a blanket except clause to test for zero division. That's not a good use of try/except; I think this is a case where you should look before you leap.

Thanks! I guess I get the idea. One thing that comes to mind is if I add a set([4]) automatically in S, based on the rest of the input. I should be good. Also, excuse my nonsense reuse of code. :-) — Omair ., Sep 19 '13 at 14:20

greedy set cover algorithm

1 Answers1