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;
} |
Partager