• Choose a category
• All
• Classic-Fiction

* *

* --------------------------- Public Interface --------------------------- *

* *

*****************************************************************************/

int cover(Set *members, Set *subsets, Set *covering);

#endif

Example 7.4. Implementation of a Function for Set Covering

/*****************************************************************************

* *

* -------------------------------- cover.c ------------------------------- *

* *

*****************************************************************************/

#include

#include "cover.h"

#include "list.h"

#include "set.h"

/*****************************************************************************

* *

* --------------------------------- cover -------------------------------- *

* *

*****************************************************************************/

int cover(Set *members, Set *subsets, Set *covering) {

Set intersection;

KSet *subset;

ListElmt *member,

*max_member;

void *data;

int max_size;

/*****************************************************************************

* *

* Initialize the covering. *

* *

*****************************************************************************/

set_init(covering, subsets->match, NULL);

/*****************************************************************************

* *

* Continue while there are noncovered members and candidate subsets. *

* *

*****************************************************************************/

while (set_size(members) > 0 && set_size(subsets) > 0) {

/**************************************************************************

* *

* Find the subset that covers the most members. *

* *

**************************************************************************/

max_size = 0;

for (member = list_head(subsets); member != NULL; member =

list_next(member)) {

if (set_intersection(&intersection, &((KSet *)list_data(member))->set,

members) != 0) {

return -1;

}

if (set_size(&intersection) > max_size) {

max_member = member;

max_size = set_size(&intersection);

}

set_destroy(&intersection);

}

/**************************************************************************

* *

* A covering is not possible if there was no intersection. *

* *

**************************************************************************/

if (max_size == 0)

return 1;

/**************************************************************************

* *

* Insert the selected subset into the covering. *

* *

**************************************************************************/

subset = (KSet *)list_data(max_member);

if (set_insert(covering, subset) != 0)

return -1;

/**************************************************************************

* *

* Remove each covered member from the set of noncovered members. *

* *

**************************************************************************/

for (member = list_head(&((KSet *)list_data(max_member))->set); member !=

NULL; member = list_next(member)) {

data = list_data(member);

if (set_remove(members, (void**)&data) == 0 && members->destroy != NULL)

members->destroy(data);

}

/**************************************************************************

* *

* Remove the subset from the set of candidate subsets. *

* *

**************************************************************************/

if (set_remove(subsets, (void **)&subset) != 0)

return -1;

}

/*****************************************************************************

* *

* No covering is possible if there are still noncovered members. *

* *

*****************************************************************************/

if (set_size(members) > 0)

return -1;

return 0;

}

Questions and Answers

Q: Instead of implementing set_is_subset as shown, how could we use other set operations to determine if one set, S1 , is a subset of another set, S2 ? Why is set_is_subset provided?

A: In set notation, if S 1 ∩ S 2 = S 1, then S 1 ⊂ S 2. Therefore, we