#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>

struct graph {
    int **adj;
    int size;
};

struct graph *create_graph(int size);
void free_graph(struct graph *g);
struct graph *load_graph(const char *fname);
void print_graph(const struct graph *g);
void copy_graph(struct graph *dest, const struct graph *src);
void mult_graph(struct graph *res, const struct graph *g1, const struct graph *g2);
void pow_graph(struct graph *res, const struct graph *g, int exp);


int main(int argc, char **argv) {
    int len;
    struct graph *g, *g2;

    if(argc != 3) {
        fprintf(stderr, "usage: gpaths <path length> <filename>\n");
        return -1;
    }

    if(!isdigit(argv[1][0])) {
        fprintf(stderr, "argument should be a number, the desired path length\n");
        return -1;
    }

    len = atoi(argv[1]);

    if(!(g = load_graph(argv[2]))) {
        return -1;
    }
    g2 = create_graph(g->size);

    printf("adjacency matrix (paths of length 1):\n");
    print_graph(g);

    pow_graph(g2, g, len);

    printf("paths of length %d:\n", len);
    print_graph(g2);

    free_graph(g);
    free_graph(g2);

    return 0;
}

/* --- create_graph() ---
 * allocates a graph with the specified number of vertices
 */
struct graph *create_graph(int size) {
    struct graph *g;
    int i;

    if(!(g = malloc(sizeof *g))) {
        return 0;
    }

    if(!(g->adj = malloc(size * sizeof(int*)))) {
        free(g);
        return 0;
    }

    for(i=0; i<size; i++) {
        if(!(g->adj[i] = malloc(size * sizeof(int)))) {
            int j;
            for(j=0; j<i; j++) {
                free(g->adj[j]);
            }
            free(g->adj);
            free(g);
            return 0;
        }
    }

    g->size = size;
    return g;
}

/* --- free_graph() ---
 * frees the memory allocated to a graph g
 */
void free_graph(struct graph *g) {
    int i;
    for(i=0; i<g->size; i++) {
        free(g->adj[i]);
    }
    free(g->adj);
    free(g);
}

/* --- load_graph() ---
 * creates a graph and initializes it by loading a graph definition
 * file that contains an adjacency matrix in the format:
 * 
 * 0010
 * 0100
 * 1001
 * 0110
 */
struct graph *load_graph(const char *fname) {
    int i, j, sz = -1;
    FILE *fp;
    static char line[1024];
    struct graph *g;

    if(!(fp = fopen(fname, "r"))) {
        return 0;
    }

    i = 0;
    while(fgets(line, 1024, fp)) {
        char *ptr = line + strlen(line) - 1;
        if(*ptr == '\n') *ptr = 0;

        if(sz == -1) {
            sz = strlen(line);
            g = create_graph(sz);
        } else {
            if(i >= sz) {
                fprintf(stderr, "warning: more rows than columns, ignoring the rest\n");
                break;
            }

            if(strlen(line) != sz) {
                fprintf(stderr, "invalid file format, variable line lengths\n");
                fclose(fp);
                free_graph(g);
                return 0;
            }
        }

        for(j=0; j<sz; j++) {
            if(line[j] == '0' || line[j] == '1') {
                g->adj[i][j] = line[j] - '0';
            } else {
                fprintf(stderr, "invalid file format, unrecognized character: '%c'\n", line[j]);
                fclose(fp);
                free_graph(g);
                return 0;
            }
        }
        i++;
    }

    if(i < sz - 1) {
        fprintf(stderr, "invalid file format, more columns than rows\n");
        fclose(fp);
        free_graph(g);
        return 0;
    }

    fclose(fp);
    return g;
}

/* --- print_graph() ---
 * prints the adjacency matrix in tabular form
 */
void print_graph(const struct graph *g) {
    int i, j;

    fputs("   ", stdout);
    for(i=0; i<g->size; i++) {
        printf("%2d ", i+1);
    }
    putchar('\n');
    fputs("  +", stdout);
    for(i=0; i<g->size; i++) {
        fputs("---", stdout);
    }
    putchar('\n');

    for(i=0; i<g->size; i++) {
        printf("%2d|", i+1);
        for(j=0; j<g->size; j++) {
            printf("%2d ", g->adj[i][j]);
        }
        putchar('\n');
    }
    putchar('\n');
}

/* --- copy_graph() ---
 * copies the adjacency matrix of src to dest, sizes must be the same
 */
void copy_graph(struct graph *dest, const struct graph *src) {
    int i, j;

    assert(dest->size == src->size);

    for(i=0; i<dest->size; i++) {
        for(j=0; j<dest->size; j++) {
            dest->adj[i][j] = src->adj[i][j];
        }
    }
}

/* --- mult_graph() ---
 * multiplies the adjacency matrices of g1 and g2 with boolean operations
 * (* -> AND, + -> OR) and returns the result in res, all sizes must be the same
 */
void mult_graph(struct graph *res, const struct graph *g1, const struct graph *g2) {
    int i, j, k;

    assert(g1->size == g2->size && g1->size == res->size);

    for(i=0; i<res->size; i++) {
        for(j=0; j<res->size; j++) {
            res->adj[i][j] = 0;
            for(k=0; k<res->size; k++) {
                res->adj[i][j] = res->adj[i][j] || (g1->adj[i][k] && g2->adj[k][j]);
            }
        }
    }
}

/* --- pow_graph() ---
 * raises the adjacency matrix of graph g to the power exp and returns the
 * result in res, res and g must be of the same size.
 */
void pow_graph(struct graph *res, const struct graph *g, int exp) {
    int i;
    struct graph *tmp;

    assert(res->size == g->size);

    tmp = create_graph(res->size);
    copy_graph(res, g);
    for(i=0; i<exp-1; i++) {
        mult_graph(tmp, res, g);
        copy_graph(res, tmp);
    }

    free_graph(tmp);
}