Posted on by Kalkicode
Code Graph

Find indegree and outdegree of a directed graph in c

C program for Find indegree and outdegree of a directed graph. Here problem description and other solutions.

// C program for
// Show degree of vertex in directed graph 
#include <stdio.h>
#include <stdlib.h>

struct AjlistNode
{
	int id;
	// Vertices id
	struct AjlistNode *next;
};
struct Vertices
{
	int data;
	struct AjlistNode *next;
	struct AjlistNode *last;
};
struct Graph
{
	int size;
	struct Vertices *node;
};
//set node key value
void setData(struct Graph *g)
{
	if (g->node != NULL)
	{
		int index = 0;
		for (int index = 0; index < g->size; index++)
		{
			// Set vertic node data
			g->node[index].data = index;
			// Set NULL Value
			g->node[index].next = NULL;
			g->node[index].next = NULL;
		}
	}
	else
	{
		printf("Vertic Node is Empty");
	}
}
// Return new graph
struct Graph *newGraph(int size)
{
	if (size < 1)
	{
		printf("\n Invalid graph size ");
		exit(0);
	}
	struct Graph *g = (struct Graph *)
	malloc(sizeof(struct Graph));
	g->size = size;
	g->node = (struct Vertices *)
	malloc(sizeof(struct Vertices) *size);
	setData(g);
	return g;
}
// Connect two nodes
void connect(struct Graph *g, int start, int last)
{
	// First create Adjacency node
	struct AjlistNode *edge = (struct AjlistNode *)
	malloc(sizeof(struct AjlistNode));
	if (edge != NULL)
	{
		edge->id = last;
		edge->next = NULL;
		if (g->node[start].next == NULL)
		{
			g->node[start].next = edge;
		}
		else
		{
			// Add edge at the end
			g->node[start].last->next = edge;
		}
		// Get last edge 
		g->node[start].last = edge;
	}
	else
	{
		printf("\n Memory overflow to create edge");
	}
}
// Add Edge from Two given Nodes
void addEdge(struct Graph *g, int start, int last)
{
	if (start < g->size && last < g->size)
	{
		connect(g, start, last);
	}
	else
	{
		//not valid Vertices
		printf("Invalid Node Vertices %d  %d", start, last);
	}
}
// Display Adjacency list of vertex
void printGraph(struct Graph *g)
{
	if (g != NULL)
	{
		struct AjlistNode *temp = NULL;
		for (int index = 0; index < g->size; index++)
		{
			printf("\n Adjacency list of vertex %d  :", index);
			temp = g->node[index].next;
			// Display edge
			while (temp != NULL)
			{
				printf("  %d", g->node[temp->id].data);
				temp = temp->next;
			}
		}
	}
	else
	{
		printf("Empty Graph");
	}
}
// Find indegree and outdegree of 
// each nodes of a given graph
void findDegree(struct Graph *g, int indegree[], int outdegree[])
{
	struct AjlistNode *temp = NULL;
	int length = 0;
	for (int i = 0; i < g->size; ++i)
	{
		temp = g->node[i].next;
		length = 0;
		while (temp != NULL)
		{
			// Update indegree
			indegree[temp->id]++;
			temp = temp->next;
			length++;
		}
		// Set outdegree value
		outdegree[i] = length;
	}
}
void showDegree(struct Graph *g)
{
	if (g->node != NULL && g->size > 0)
	{
		int indegree[g->size];
		int outdegree[g->size];
		// Set zero degree
		for (int i = 0; i < g->size; i++)
		{
			indegree[i] = 0;
			outdegree[i] = 0;
		}
		// Find degree
		findDegree(g, indegree, outdegree);
		printf("\n\n");
		// Display result
		for (int i = 0; i < g->size; ++i)
		{
			printf("Node [%d] indegree [%d] outdegree [%d]\n", 
                   i, indegree[i], outdegree[i]);
		}
	}
	else
	{
		printf("Empty Graph");
	}
}
int main()
{
	// 6 implies the number of nodes in graph
	struct Graph *g = newGraph(6);
	// Connected two node with Edges
	addEdge(g, 0, 1);
	addEdge(g, 0, 2);
	addEdge(g, 0, 5);
	addEdge(g, 2, 3);
	addEdge(g, 3, 1);
	addEdge(g, 4, 0);
	addEdge(g, 4, 1);
	addEdge(g, 5, 0);
	addEdge(g, 5, 2);
	printGraph(g);
	// Test
	showDegree(g);
	return 0;
}

Output

 Adjacency list of vertex 0  :  1  2  5
 Adjacency list of vertex 1  :
 Adjacency list of vertex 2  :  3
 Adjacency list of vertex 3  :  1
 Adjacency list of vertex 4  :  0  1
 Adjacency list of vertex 5  :  0  2

Node [0] indegree [2] outdegree [3]
Node [1] indegree [3] outdegree [0]
Node [2] indegree [2] outdegree [1]
Node [3] indegree [1] outdegree [1]
Node [4] indegree [0] outdegree [2]
Node [5] indegree [1] outdegree [2]

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment