Demo entry 6684250

C

Submitted by anonymous on Dec 14, 2017 at 15:57
Language: C. Code size: 5.4 kB.

```#include<stdio.h>
#include<stdlib.h>
#define MaxVertexNum 1000  			// maximum number of vertices
typedef int Vertex;
/**
*This project mainly use the Kruskal¡¯s Algorithm to satisfy the function needed
in the requirement paper. We define a struct to store the edge and a disjiont
set array to store the nodes.

*Each time we select a smallest weight edge to check whether add or discard this
edge by checking whether it satisfy the requirement for image segmentation and
whether construct a loop.

*And use the disjiont set array to implement the output function easily.
**/
typedef struct GNode *PtrToGNode;
struct GNode {
int Nv;							// total num of vertexs
int Ne;							// total num of edges
double c; 							// the constant c

};
typedef PtrToGNode LGraph;
PtrToGNode Graph;

typedef struct Edge *PtrToEdge;
struct Edge {
Vertex a;
Vertex b;
int weight;
};				// store the edges values
PtrToEdge Edges;
int edge_num = 0;

void Insert_Edge(LGraph Graph, int i);// the function to insert each edge
void ImageSegmentation();			// the main function
void PrintSegmentation(int index);	// the output function
int Find(int x);					// the operation in disjiont set
int Union(int a, int b);			// the operation in disjiont set
void sort_Edges();					// sort the edges according to the weight value

int* Node;				// the disjiont set array
int* MaxWeight;		// store the maxweight of the segment

int main(void) {
int i, j = 1;

sort_Edges();					// sort the edge's weight from small to big

ImageSegmentation();			// the main function in this project

for (j = 0; j < Graph->Nv;j++) {// make sure the disjiont set connect in smallest height for the convinience of output
if(Node[j]>=0)
while (Node[Node[j]]>=0)
Node[j] = Node[Node[j]];
}

for (i = 0; i<Graph->Nv; i++) {	// output the segments
if (Node[i]<0) {			// find each segments head vertex
PrintSegmentation(i);	// print each elements in the segment
}
}

return 0;
}

void ImageSegmentation() {
/**
* In this function we use the Kruskal¡¯s Algorithm
the T represent the edges number added in the whole graph
which should be fewer than Vertex-1

* Each loop we choose the smallest edge from the graph
**/

int i, T = 0;//T represent the edges added in the whole graph

for (i = 0; i<Graph->Nv; i++) {// initialize for the algorithm
Node[i] = -1;
MaxWeight[i] = 0;
}

while (T<Graph->Nv - 1 && edge_num<Graph->Ne) {
edge_num++;
}

}

Graph = (PtrToGNode)malloc(sizeof(struct GNode));
scanf("%d %d %lf", &Graph->Nv, &Graph->Ne, &Graph->c);
/*initialize the structure*/
Edges = (PtrToEdge)malloc(sizeof(struct Edge)*(Graph->Ne+1));
Node = (int*)malloc(sizeof(int)*(Graph->Nv+1));
MaxWeight = (int*)malloc(sizeof(int)*(Graph->Nv+1));

for (int i = 0; i<Graph->Ne; i++) {// initialize the edge weight
Edges[i].weight = -1;
}
/*For each loop read in an edge*/
for (int i = 0; i<Graph->Ne; i++) {
Insert_Edge(Graph, i);
}

}

void Insert_Edge(LGraph Graph, int i) {

int a, b, weight, temp;

scanf("%d %d %d", &a, &b, &weight);

if (a>b) {//make sure the Edge[i].a num is smaller then the b for the simplicity
temp = a;
a = b;
b = temp;
}

Edges[i].a = a;
Edges[i].b = b;
Edges[i].weight = weight;

}

int Find(int x) {
if (Node[x]<0)
return x;
else {
return Node[x] = Find(Node[x]);// with path compression
}
}

int Union(int a, int b) {

int fa, fb, temp = 0;
fa = Find(a);
fb = Find(b);
if (fa == fb)
return 0;

if (fa > fb) { //make sure fa is smaller than fb for the convinience of updating the information
fa = temp;
fa = fb;
fb = temp;
}

/*the double if gurantee the rule:
The dissimilarity D(C1, C2) of any two components C1 and C2 is larger than
the confidence H of any of C1 and C2*/
if (MaxWeight[fa] + Graph->c / -Node[fa]<Edges[edge_num].weight)
return 0;
if (MaxWeight[fb] + Graph->c / -Node[fb]<Edges[edge_num].weight)
return 0;

else {
/*update the information by replacing the node num in one segment and update the Confidence*/
Node[fa] += Node[fb];
Node[fb] = fa;
MaxWeight[fa] = Edges[edge_num].weight;//subsititute the max edge value
return 1;
}

}

void sort_Edges() {

int i, j, index;
struct Edge temp;

/*sort the edges according to the value of edge weight*/
for (i = 0; i<Graph->Ne; i++) {
index = i;
for (j = i + 1; j<Graph->Ne; j++) {
if (Edges[j].weight<Edges[index].weight) {
index = j;
}
}
temp = Edges[index];
Edges[index] = Edges[i];
Edges[i] = temp;
}
}

void PrintSegmentation(int index) {

int i, j, *printlist, num = 0;
/*allocate a print list for print the element*/
printlist = (int*)malloc(sizeof(int)*Graph->Nv);
int temp;

/*find all the elements in the same segment and store in the printlist*/
for (i = 0; i<Graph->Nv; i++) {
if (Node[i] == index || i == index) {
printlist[num] = i;
num = num + 1;
}
}

/*print out the results*/
printf("%d", printlist[0]);
for (i = 1; i<num; i++)
printf(" %d", printlist[i]);
printf("\n");

}
```

This snippet took 0.02 seconds to highlight.

Back to the Entry List or Home.