# グラフデータ構造をCで

グラフのデータ構造をCで...面倒..

```#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <stdbool.h>

struct edge {
int into;
int weight;
};

struct node {
bool visitedp;
int  distance;
struct graph *g;
//Index in graph
int  id;

struct edge **edges;
};

struct edge* mk_edge(int into, int weight)
{
struct edge* new_edge;
if((new_edge = (struct edge*)malloc(sizeof(struct edge))) == NULL) {
fprintf(stderr, "Failed to allocate edge\n");
return NULL;
}
new_edge->into = into;
new_edge->weight = weight;

return new_edge;
}

void showEdge(struct edge* e)
{
printf("(%d, %d)", e->into, e->weight);
}

struct node* mk_node(int id, int ecount, ...)
{
struct node* new_node;
if((new_node = (struct node*)malloc(sizeof(struct node))) == NULL) {
fprintf(stderr, "Failed to allocate new node\n");
return NULL;
}
new_node->id = id;
if((new_node->edges = (struct edge **)malloc(sizeof(struct edge*) * (ecount + 1))) == NULL) {
fprintf(stderr, "Failed to allocate edge list\n");
free(new_node);
return NULL;
}

va_list v_args;
int i;
va_start(v_args, ecount);
for(i = 0; i < ecount; i++) {
new_node->edges[i] = va_arg(v_args, struct edge*);
}
//NULLを最後のマークにつかう
new_node->edges[i] = NULL;
va_end(v_args);

return new_node;
}

void free_node(struct node* n)
{
free(n->edges);
free(n);
}

void showNode(struct node* n)
{
printf("id: %d edges: [", n->id);
int i;
for(i = 0; n->edges[i+1] != NULL; i++) {
showEdge(n->edges[i]);
putchar(',');
}
showEdge(n->edges[i]);
printf("]\n");
}

struct graph {
struct node **nodes;
int size;
};

struct graph* mk_graph(int ncount, ...)
{
struct graph *new_graph;
if((new_graph = (struct graph*)malloc(sizeof(struct graph))) == NULL) {
fprintf(stderr, "Failed to allocate new graph\n");
return NULL;
}
if((new_graph->nodes = (struct node**)malloc(sizeof(struct node *) * ncount)) == NULL) {
fprintf(stderr, "Failed to allocate node list\n");
return NULL;
}

new_graph->size = ncount;
va_list v_args;
int i;
va_start(v_args, ncount);
for(i = 0; i < ncount; i++) {
new_graph->nodes[i] = va_arg(v_args, struct node*);
}
va_end(v_args);

return new_graph;
}

void free_graph(struct graph* g)
{
int i;
for(i = 0; i < g->size; i++) {
free_node(g->nodes[i]);
}
free(g);
}

void showGraph(struct graph *g)
{
int i;
for(i = 0; i < g->size; i++) {
showNode(g->nodes[i]);
}
}

int main()
{
struct graph *g;
g = mk_graph(3,
mk_node(1, 2, mk_edge(2, 1), mk_edge(3, 2)),
mk_node(2, 1, mk_edge(1, 3)),
mk_node(3, 2, mk_edge(1, 1), mk_edge(2, 2)));
showGraph(g);
free_graph(g);
return 0;
}
```

ちゃんと

```./a.out
id: 1 edges: [(2, 1),(3, 2)]
id: 2 edges: [(1, 3)]
id: 3 edges: [(1, 1),(2, 2)]
```

となります。