From f618466c25d43f3bae9e40920273bf77de1e1149 Mon Sep 17 00:00:00 2001
From: leochanj105 <leochanj@live.unc.edu>
Date: Mon, 19 Oct 2020 23:09:30 -0400
Subject: initial sd-vbs

initial sd-vbs

add sd-vbs

sd-vbs
---
 SD-VBS/benchmarks/multi_ncut/src/c/segment-graph.c | 95 ++++++++++++++++++++++
 1 file changed, 95 insertions(+)
 create mode 100644 SD-VBS/benchmarks/multi_ncut/src/c/segment-graph.c

(limited to 'SD-VBS/benchmarks/multi_ncut/src/c/segment-graph.c')

diff --git a/SD-VBS/benchmarks/multi_ncut/src/c/segment-graph.c b/SD-VBS/benchmarks/multi_ncut/src/c/segment-graph.c
new file mode 100644
index 0000000..13b219b
--- /dev/null
+++ b/SD-VBS/benchmarks/multi_ncut/src/c/segment-graph.c
@@ -0,0 +1,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;
+}
+
-- 
cgit v1.2.2