Let's write β

プログラミング中にできたことか、思ったこととか

グラフデータ構造を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)]

となります。