-
Notifications
You must be signed in to change notification settings - Fork 3
/
Clique.cc
124 lines (106 loc) · 2.22 KB
/
Clique.cc
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
112
113
114
115
116
117
118
119
120
121
122
123
124
#ifndef CLIQUE_CC
#define CLIQUE_CC
#include "Clique.h"
#include <cstdlib>
/*
* Returns the Gain for the Clique
* Gain = sum of all link costs - largest link cost
*/
int Clique::getGain(std::vector <Link> linkdata)
{
int gain=0;
int largest=getWeight(linkdata);
for(unsigned int c=0; c< LS.size(); c++)
{
int link_id = LS[c];
gain = gain + linkdata[link_id].getRequirement();
}
return gain - largest;
}
/*
* Returns the weight of a Clique
* Weight = Maximal Requirement (may need to be revised)
*/
int Clique::getWeight(std::vector <Link> linkdata)
{
int max=0;
for(unsigned int c=0; c<LS.size(); c++)
{
int link_id = LS[c];
int requirement = linkdata[link_id].getRequirement();
if(requirement > max)
max = requirement;
}
return max;
}
/*
* Returns true if the two cliques are equivalent
*/
bool Clique::equivalentClique(Clique c2)
{
/* Check for each link_id of c1 in c2 */
for(unsigned int c=0; c< LS.size(); c++)
if(!c2.exists(LS[c]))
return false;
for(unsigned int c=0; c< c2.size(); c++)
if(!exists(c2.getLink(c)))
return false;
return true;
}
/*
* Checks if the given link_id already exists
* within the clique
*/
bool Clique::exists(int link_id)
{
for(unsigned int l=0;l<LS.size();l++)
if(LS[l] == link_id)
return true;
return false;
}
/*
* Returns true if c1 and c2 intersect
*/
bool Clique::intersect(Clique c2)
{
for(unsigned int c=0;c<LS.size();c++)
if(c2.exists(LS[c]))
return true;
for(unsigned int c=0;c<c2.size();c++)
if(exists(c2.getLink(c)))
return true;
return false;
}
/*
* Returns a link_id from the clique
*/
int Clique::getLink(unsigned int l)
{
if(l > LS.size())
{
std::cout << "Error, you are trying to access memory outside of the clique" << std::endl;
exit(255);
}
else
return LS[l];
}
/*
* Adds the link_id to the clique iff it is unique
*/
void Clique::addLink(int link_id)
{
if(!exists(link_id))
LS.push_back(link_id);
}
void Clique::display()
{
for(unsigned int l=0; l < LS.size(); l++)
{
std::cout << LS[l];
if(l != LS.size()-1)
std::cout << ",";
}
std::cout << std::endl;
}
/* ---- Private Functions ---- */
#endif