How to write a C Program - C Parse Graph From .col File in C Programming Language ?
Solution For C Program:
#include<stdio.h>
#include<stdlib.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);
//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);
//print graph
print_graph(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");
}