Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef SEGMENT_GRAPH
00020 #define SEGMENT_GRAPH
00021
00022 #include <algorithm>
00023 #include <cmath>
00024 #include "disjoint-set.h"
00025
00026
00027 #define THRESHOLD(size, c) (c/size)
00028
00029 typedef struct {
00030 float w;
00031 int a, b;
00032 } edge;
00033
00034 bool operator<(const edge &a, const edge &b) {
00035 return a.w < b.w;
00036 }
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048 universe *segment_graph(int num_vertices, int num_edges, edge *edges,
00049 float c) {
00050
00051 std::sort(edges, edges + num_edges);
00052
00053
00054 universe *u = new universe(num_vertices);
00055
00056
00057 float *threshold = new float[num_vertices];
00058 for (int i = 0; i < num_vertices; i++)
00059 threshold[i] = THRESHOLD(1,c);
00060
00061
00062 for (int i = 0; i < num_edges; i++) {
00063 edge *pedge = &edges[i];
00064
00065
00066 int a = u->find(pedge->a);
00067 int b = u->find(pedge->b);
00068 if (a != b) {
00069 if ((pedge->w <= threshold[a]) &&
00070 (pedge->w <= threshold[b])) {
00071 u->join(a, b);
00072 a = u->find(a);
00073 threshold[a] = pedge->w + THRESHOLD(u->size(a), c);
00074 }
00075 }
00076 }
00077
00078
00079 delete threshold;
00080 return u;
00081 }
00082
00083 #endif