-
Notifications
You must be signed in to change notification settings - Fork 0
/
maximum_partial.c
59 lines (54 loc) · 1.32 KB
/
maximum_partial.c
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
#include "maximum_partial.h"
/**
* \brief Searches the vertex with the less edges in a given graph
* \param g The source graph
* \param forbidden A set of vertices to ignore during the search
* \author Abdelkader Benameur
* \return The index of the found vertex
*/
int vertex_with_less_edges(graph g, subgraph forbidden)
{
int nbEdges;
int nbEdgesMin = NB_VERTICES*NB_VERTICES;
int index = -1;
int i,j;
for(i=0 ; i<g.n ; i++)
{
nbEdges = 0;
if(!forbidden[i])
{
for(j=i+1 ; j<g.n ; j++)
{
if(!forbidden[j] && g.edges[i][j]) nbEdges++;
}
if(nbEdges < nbEdgesMin)
{
nbEdgesMin = nbEdges;
index = i;
}
}
}
return index;
}
/**
* \brief Using an heuristic, generates a subgraph as close to maximum as possible
* \param g The source graph
* \param max The initialy empty subgraph to turn into a desert maximum subgraph
* \author Abdelkader Benameur
*/
//Complexity : theta(n^3)
void maximum_partial(graph g, subgraph max)
{
int index,i;
subgraph forbidden;
clock_t time = clock();
for(i=0 ; i<NB_VERTICES ; i++) forbidden[i] = 0;
while(!is_maximal(max,g))
{
index = vertex_with_less_edges(g,forbidden);
forbidden[index] = 1;
max[index] = 1;
if(!is_desert(max,g)) max[index] = 0;
}
printf("[maximum_partial/maximum_partial] Execution time : %fs\n",(double)time/CLOCKS_PER_SEC);
}