How to write a C Program Depth First Search in C Programming Language ?
Solution For C Program :
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//file name
char str[] = "sample.col\0";
//declare enum without specific name
enum {
G_PROPERTY = 'p',
G_EDGE = 'e',
BUF_SIZE = 64
};
struct node {
unsigned id;
struct node *next;
};
struct graph {
unsigned nOfNodes;
unsigned nOfEdges;
struct {
unsigned length;
struct node *first;
struct node *last;
} *nodes;
int (*add_edge)(struct graph*, unsigned, unsigned);
//gr->addEdge()
};
//allocate memory for graph and initialize graph
struct graph *init_graph (void);
//add edge to graph
int graph_add_edge (struct graph *g, unsigned from, unsigned to);
//parse graph
int parse_graph (FILE *file, struct graph *g);
//parse property file, called from parse_graph()
int parse_property_line (char line[], struct graph *g);
//parse edge, called from parse_graph()
int parse_edge (char line[], struct graph *g);
void print_graph (struct graph *g);
//interactive
int interactive (struct graph *g);
//depth search
int depth_first_search (struct graph *g, unsigned from, unsigned to);
//verbose
int verbose = 0;
int main (void) {
//open file
FILE *file = fopen("sample.col", "r");
//declare and assign variable for graph
struct graph *g = init_graph();
//parse graph
parse_graph(file, g);
//close file
fclose(file);
//interaction
while (interactive(g)) {
//
}
//return 0
return 0;
}
int parse_graph (FILE *file, struct graph *g) {
//check if file parameter is null
if (file == NULL) {
return 1;
}
//declare and assign variable for line
char line[BUF_SIZE] = {};
while (fgets(line, (sizeof line) / sizeof(char), file) != NULL) {
switch (line[0]) {
case G_PROPERTY:
parse_property_line(line, g);
break;
case G_EDGE:
parse_edge(line, g);
break;
default:
if (verbose == 1) {
printf("[DEBUG] failure in line: %s", line);
}
break;
}
}
//return 0
return 0;
}
int parse_property_line (char line[], struct graph *g) {
//delcare and assign variable for number of nodes
unsigned nOfNodes = 0;
unsigned nOfEdges = 0;
//scan readed line and check, if line format is correct
if (sscanf(line, "p edge %u %u", &nOfNodes, &nOfEdges) < 2) {
return 1;
}
//print number of nodes to console
//printf("Number of nodes: %u\nNumber of edges: %u\n", nOfNodes, nOfEdges);
//check, if graph is already initialized
if (g->nOfNodes != 0) {
//print to console
puts("Warning: file contains two property lines.");
//return 2
return 2;
}
//alocate memory for node list
g->nodes = calloc((nOfNodes), sizeof *g->nodes);
//check, if nodes could be allocated successfully
if (g->nodes == NULL) {
//print error to console
perror("parse_property_line");
//exit with error code
exit(EXIT_FAILURE);
}
//set number of nodes
g->nOfNodes = nOfNodes;
//set number of edges
g->nOfEdges = nOfEdges;
return 0;
}
int parse_edge (char line[], struct graph *g) {
//declare variables for from and to nodes
unsigned from = 0;
unsigned to = 0;
//scan readed line and check, if line format is correct
if (sscanf(line, "e %u %u", &from, &to) < 2) {
return 1;
}
//printf("Edge from %u to %u\n", from, to);
//add edge to graph
return graph_add_edge(g, from, to);
}
struct graph *init_graph (void) {
struct graph *g = malloc(sizeof *g);
//check, if malloc was successful
if (g == NULL) {
//error function from stdio.h, prints error message to console
perror("init_graph");
//exit with error code
exit(EXIT_FAILURE);
}
//set number of nodes and edges to 0, because graph doesnt have nodes and edges yet
g->nOfNodes = 0;
g->nOfEdges = 0;
//clear node list
g->nodes = NULL;
//return graph struct
return g;
}
int graph_add_edge (struct graph *g, unsigned from, unsigned to) {
//check, if node is in graph
if (g->nOfNodes < from || g->nOfNodes < to) {
//print to console
printf("Edge from %u to %u isnt in graph.\n", from, to);
//return 1
return 1;
}
//check, if edge is already in graph to avoid redundancy
for (struct node *n = g->nodes[from - 1].first; n != NULL; n = n->next) {
if (n->id == to) {
//print warning to console
printf("Warning: redundant edge (%u, %u).\n", from, to);
//return with error code
return 1;
}
}
//allocate memory for node
struct node *n = malloc(sizeof *n);
//check, if allocation was successful
if (n == NULL) {
//print error message to console
perror("graph_add_edge");
//exit with error code
exit(EXIT_FAILURE);
}
//set if to to edge
n->id = to;
//set next node to null, because node doesnt have an next node yet
n->next = NULL;
//check, if we insert the first node in graph
if (g->nodes[from - 1].length == 0) {
//set node to first node
g->nodes[from - 1].first = n;
//set node to last node
g->nodes[from - 1].last = n;
} else {
//set neighboor node
g->nodes[from - 1].last->next = n;
//set new last node in graph
g->nodes[from - 1].last = n;
}
//increment count of neighboor nodes for node
g->nodes[from - 1].length++;
//increment count of edges
//g->nOfEdges++;
//success, return 0
return 0;
}
void print_graph (struct graph *g) {
//print to console
printf("-------- Graph with %u nodes and %u edges --------\n", g->nOfNodes, g->nOfEdges);
//iterate through graph
for (unsigned from = 1; from <= g->nOfNodes; from++) {
//iterate through nodes, start with from - 1, because first node in file specification is 1
for (struct node *n = g->nodes[from - 1].first; n != NULL; n = n->next) {
//print to console
printf("\t(%u, %u)\n", from, n->id);
}
}
//print to console
printf("-------- END of Graph --------\n");
}
/**
* depth first search
*
* @link https://de.wikipedia.org/wiki/Tiefensuche
*
* @param g graph
* @param from from node for edge
* @param to to node for edge
*
* @return 0 on success
*/
int depth_first_search (struct graph *g, unsigned from, unsigned to) {
//array with visited nodes
int visited[g->nOfNodes];
//set every item of visited array to 0
memset(visited, 0, sizeof visited);
//array with parent nodes
unsigned parent_array[g->nOfNodes];
//set every item of parent array to 0
memset(parent_array, 0, sizeof parent_array);
//declare array for stack
unsigned stack[g->nOfNodes];
//declare and assign number for stack pointer, points to stack index
unsigned stackpointer = 0;
//set current visited node
stack[stackpointer++] = from;
//set node as visitied, 0 means not visited, 1 means visited, from - 1 because first node number starts with 1, but c array with 0
visited[from - 1] = 1;
//iterate through stack
while (stackpointer > 0) {
//set current node
unsigned current = stack[--stackpointer];
//check, if we have found node
if (current == to) {
//print to console
printf("Path found: ");
//iterate through graph, from current element to root element and print path
for (unsigned n = current; parent_array[n - 1] != 0; n = parent_array[n - 1]) {
//print to console
printf(" <= %u", parent_array[n - 1]);
}
printf("\n");
//return 0, because we have found node in graph
return 0;
} else {
//iterate through neighboor nodes (edges from node)
for (struct node *n = g->nodes[current - 1].first; n != NULL; n = n->next) {
//check, if node was already visited
if (!visited[n->id - 1]) {
//add node to stack
stack[stackpointer++] = n->id;
//set node to visited
visited[n->id - 1] = 1;
//set parent node
parent_array[n->id - 1] = current;
}
}
}
}
//print to console
printf("No path from %u to %u.\n", from, to);
//return 1, because we couldnt found node in graph
return 1;
}
int interactive (struct graph *g) {
//declare buffer variable
char buffer[BUF_SIZE];
//print to console
puts("Enter a command [p - print graph, q - quit, s <from> <to> - depth first search]: \n");
//read string from console
fgets(buffer, sizeof buffer, stdin);
switch (buffer[0]) {
//print graph
case 'p':
print_graph(g);
return 1;
//quit
case 'q':
return 0;
//search
case 's':
{
//declare and assign variables for from and to
unsigned from = 0;
unsigned to = 0;
if (sscanf(buffer, "s %u %u", &from, &to) == 2) {
depth_first_search(g, from, to);
}
return 1;
}
default:
return 1;
}
}