1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
#include <iostream>
#include "MyHashSet.h"
bool Included (const MyHashSet *setCover, const MyHashSet &W);
int MySetCover(const MyHashSet &W, MyHashSet setsArr[], int arrSize);
bool AllVisited(MyHashSet setsArr[], int arrSize);
// Creates a set cover and return the minimum number of subsets including the
// whole W.
// W is the set representing the world of elements.
// Sets arr are a lot of hash sets.
// Arrsize is the size of the setsArr.
int MySetCover(const MyHashSet &W, MyHashSet setsArr[], int arrSize)
{
int minimalSoFar=0;
int currentSize=0;
// Returns -1 if there is not a set cover.
int numberOfSets=0;
// We initialize it 100 so that it will work for the first iteration.
int minimumSize=100;
MyHashSet* setCover = new MyHashSet;
while (!Included(setCover, W))
{
// If we already visited all of setArr, there is no set cover.
if (AllVisited(setsArr, arrSize))
return -1;
// 1/ Looking for the Ui that gets most elements inside all that were
// not taken in W until A includes W.
// ie : the Ui that makes the set W.reduce(A.union(Ui)) minimal.
for (int i=0; i<arrSize; i++)
{
if (setsArr[i].IsVisited())
continue;
MyHashSet* tempUnion = setCover->Union(setsArr[i]);
MyHashSet* toAdd = W.Reduce(*tempUnion);
currentSize = toAdd->Size();
if (currentSize < minimumSize)
{
minimalSoFar = i;
minimumSize = currentSize;
}
delete tempUnion;
delete toAdd;
}
// 2/ Adding the best candidate so far and setting visited to true.
MyHashSet* setCoverUnion = setCover->Union(setsArr[minimalSoFar]);
delete setCover;
MyHashSet* setCover = new MyHashSet;
// 3/ Copy it to the "final set cover".
for (int i=0; i<HASH_SIZE; i++)
{
MyLinkedList* ll = setCoverUnion->GetLinkedList(i);
MyLinkedList::Iterator* it1 = new MyLinkedList::Iterator(ll);
while (it1->HasNext())
{
setCover->Add(it1->Next());
}
delete ll;
delete it1;
}
// 4/ Delete the temporary setCoverUnion.
delete setCoverUnion;
// Attention ICI.
setsArr[minimalSoFar].SetVisited();
numberOfSets++;
minimalSoFar=0;
minimumSize = 100;
}
delete setCover;
return numberOfSets;
}
// Check if all the subsets have been visited return true if yes.
bool AllVisited(MyHashSet setsArr[], int arrSize)
{
for (int i=0; i<arrSize; i++)
{
if (!setsArr[i].IsVisited())
return false;
}
return true;
}
// Returns true iff W is included in A.
bool Included (const MyHashSet *setCover, const MyHashSet &W)
{
// We need to check that everything that's inside W is also in setCover.
for (int i=0; i<HASH_SIZE; i++)
{
MyLinkedList* ll = W.GetLinkedList(i);
MyLinkedList::Iterator it(ll);
while (it.HasNext())
{
// Adding element of current list.
if (!setCover->InHashSet(it.Next()))
{
delete ll;
return false;
}
}
delete ll;
}
// W is included in A.
return true;
} |
