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 ReadG(); 						// the function to read the inputs
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;

	ReadG();
	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
	and determine whether add or discard the edge
	**/

	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) {
		T += Union(Edges[edge_num].a, Edges[edge_num].b);// check whether add or discard the edge
		edge_num++;
	}

}

void ReadG() {

	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.

Delete this entry (admin only).