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
|
/********************************
Author: Sravanthi Kota Venkata
********************************/
#include <stdio.h>
#include <stdlib.h>
#include "segment.h"
// threshold function
#define THRESHOLD(size, c) (c/size)
int find(universe* u, int x)
{
int y=x;
while (y != u->elts[y].p)
y = u->elts[y].p;
u->elts[x].p = y;
return y;
}
void join(universe* u, int x, int y)
{
if (u->elts[x].rank > u->elts[y].rank)
{
u->elts[y].p = x;
u->elts[x].size += u->elts[y].size;
}
else
{
u->elts[x].p = y;
u->elts[y].size += u->elts[x].size;
if (u->elts[x].rank == u->elts[y].rank)
u->elts[y].rank++;
}
u->num--;
return ;
}
universe *segment_graph(int num_vertices, int num_edges, edge *edges, float c, F2D* edgeWeights, F2D* in, I2D* ind,
universe* u)
{
float threshold[num_vertices];
int i, a, b, j, k;
//universe *u;
//F2D *edgeWeights;
I2D *indices;
edgeWeights = fResetHandle(edgeWeights,1,num_edges);
for(i=0; i<num_edges; i++)
asubsref(edgeWeights,i) = edges[i].w;
// sort edges by weight
indices = fResortIndices(edgeWeights,1, in, ind);
// make a disjoint-set forest
//u = (universe*)malloc(sizeof(universe));
//u->elts = (uni_elt*)malloc(sizeof(uni_elt)*num_vertices);
u->num = num_vertices;
for(i=0; i<num_vertices; i++)
{
u->elts[i].rank = 0;
u->elts[i].size = 1;
u->elts[i].p = i;
}
// init thresholds
for (i = 0; i < num_vertices; i++)
arrayref(threshold,i) = THRESHOLD(1,c);
// for each edge, in non-decreasing weight order...
for (i = 0; i < num_edges; i++)
{
edge *pedge = &edges[ asubsref(indices,i) ];
// components conected by this edge
a = find(u, pedge->a);
b = find(u, pedge->b);
if (a != b)
{
if ((pedge->w <= arrayref(threshold,a)) && (pedge->w <= arrayref(threshold,b)))
{
join(u, a, b);
a = find(u, a);
arrayref(threshold,a) = pedge->w + THRESHOLD(u->elts[a].size, c);
}
}
}
//fFreeHandle(edgeWeights);
//iFreeHandle(indices);
return u;
}
|
