Bellman Ford Algorithm implementation

[Seaghost]

So for my homework, I have to implement the bellman ford algorithm, with a given input.

Busan Daegu Daejeon Gangeung Gwangju Jeonju Jinju Pohang Seoul Wonjuk
Busan 0 108 INF INF INF INF 106 110 INF INF
Daegu 108 0 152 INF 211 INF 135 87 INF 219
Daejeon INF 152 0 INF INF 86 INF INF 161 INF
Gangeung INF INF INF 0 INF INF INF 237 INF 126
Gwangju INF 211 INF INF 0 99 161 INF INF INF
Jeonju INF INF 86 INF 99 0 INF INF 214 INF
Jinju 106 135 INF INF 161 INF 0 INF INF INF
Pohang 110 87 INF 237 INF INF INF 0 INF INF
Seoul INF INF 161 INF INF 214 INF INF 0 125
Wonju INF 219 INF 126 INF INF INF INF 125 0

Code:

/**

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

#define MAX_STR_LEN 256
#define MAX_LIMIT 9999

typedef struct Edge
{
    int source;
    int dest, weight;

}Edge;

typedef struct Graph
{
    int vert_n;
    int edge_n;

    struct Edge* edge;
}Graph;

struct Graph* createGraph(int V, int E);
void BellmanFord(struct Graph* graph, int source);
void out_res(int dist[], int n);
void print_name(int counter, char name[][MAX_STR_LEN]);

int main(int argc, char* argv[])
{
    FILE * fp;
    char *buffer;
    char *replc_str = NULL;

    int f_size = 0;
    int counter = 0;
    int c;
    int n = 0;
    int k = 0; 
    int temp = 0;
    int edge_n = 0;

    if (argc != 2)
    {
        printf ("Usage: ./scc filename\n");
        return -1;
    }

    fp = fopen (argv[1], "r");
    if (fp == NULL)
    {
        printf("failed to open file");
        return 0;
    }

    fseek (fp, 0L, SEEK_END);
    f_size = ftell(fp);
    fseek (fp, 0L, SEEK_SET); //or use rewind(fp);


    buffer = (char *) malloc(f_size);
    if (!buffer)
    {
        printf("Failed to allocate buffer!!\n");
    }

    while ((c = fgetc(fp)) != EOF)
    {       
        buffer[n++] = c;
        if( c != '\t' && c != ' ' && c != '\n' && c != '\r')
        {
            if(!isalpha(c))
            {
                counter++;
            }
        }
    }

    counter = sqrt(counter);

    n = 0;
    k = 0;
    c = 0;
    int (*adj_matrix)[counter] = malloc(sizeof * adj_matrix * counter);

    while(n < strlen(buffer))
    {
        if ((n < strlen(buffer) - 4) && (buffer[n] == 'I') && (buffer[n+1] == 'N') && (buffer[n+2] == 'F'))
        {
            adj_matrix[c][k] = MAX_LIMIT;
            n+=3;
            k++;
        }
        else if (isdigit(buffer[n]))
        {
            temp = 0;
            edge_n++;
            while(isdigit(buffer[n+temp]))
            {
                adj_matrix[c][k] = adj_matrix[c][k] * 10 + (buffer[n+temp] - '0');
                temp++;
            }
            if(temp > 1)
            {
                n+=temp;
                k++;
            }
            else
            {
                adj_matrix[c][k] = buffer[n] - '0';
                k++;
                n++;
            }
        }
        else
        {
            n++;
        }
        
        if(k > 9)
        {
            k = 0;
            c++;
        }
    }

    for(n = 0; n < counter; n++)
    {
        for(k = 0; k < counter; k++)
        {
            printf("%d ", adj_matrix[n][k]);
        }
            printf("\n");
    }

    printf("\n\n\n");
    char name[counter][MAX_STR_LEN];
    for(n = 0; n < counter; n++)
    {
        memset(name[n], '\0', sizeof(name[n]));
    }

    //print location string
    n = 0;
    while(1)
    { 
        if(isdigit(buffer[n]))
        {
           buffer[n] = '\0'; 
           break;
        }
        n++;       
    }

    c = 0;
    k = 0;
    for(n = 1; n < strlen(buffer); n++)
    {
        if(isupper(buffer[n]))
        {
            strncpy(name[c], buffer + k, n - k);
            k = n;
            c++;
        }
    }
    
    //calculate edge:
    edge_n -= counter;
    edge_n /= 2;

    //printf("Edgen: %d\n", edge_n);

    Graph* graph = createGraph(counter, edge_n);
    //print_name(counter, name);


    c = 0;
    temp = 0;
    
    for(temp = 0; temp < counter; temp++)
    {
        for(k = 0; k < counter; k++)
        {
            for(n = 0; n < counter; n++)
            {
                if(adj_matrix[k][n] < MAX_LIMIT)
                {
                    //printf("source: %d dest: %d weight: %d\n", k, n, adj_matrix[k][n]);
                    graph->edge[c].source = k;
                    graph->edge[c].dest = n;
                    graph->edge[c].weight = adj_matrix[k][n];

                    c++;
                }
            }
        }

        BellmanFord(graph, temp);
    }
    


     free(buffer);
    free(adj_matrix);

}

struct Graph* createGraph(int V, int E)
{
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->vert_n = V;
    graph->edge_n = E;
    graph->edge = (Edge*)malloc(graph->edge_n * sizeof(Edge));
    return graph;
}

void BellmanFord(struct Graph* graph, int source)
{
    int V = graph->vert_n;
    int E = graph->edge_n;
    int dist_src[V];
    int past_[V];
    int i, j, u, v, weight;

    //init single source 
    for(i = 0; i < V; i++)
    {
        dist_src[i] = MAX_LIMIT;
        past_[i] = 0;
    }
    dist_src[source] = 0;

    //relax
    for(i = 0; i < V-1; i++)
    {
        for(j = 0; j < E; j++)
        {
            u = graph->edge[j].source;
            v = graph->edge[j].dest;
            weight = graph->edge[j].weight;

            if ((dist_src[u] != MAX_LIMIT) && (dist_src[u] + weight < dist_src[v]))
            {
                dist_src[v] = dist_src[u] + weight;
                past_[v] = u;
            }
        }
    }

    //neg cycle check
    for(i = 0; i < E; i++)
    {
        u = graph->edge[i].source;
        v = graph->edge[i].dest;
        weight = graph->edge[j].weight;

        if (dist_src[u] != MAX_LIMIT && dist_src[u] + weight < dist_src[v])
        {
            printf("neg cycle\n");
        }
    }

    out_res(dist_src, V);
}
 
void out_res(int dist[], int n)
{
    int i;
 
    for (i = 0; i < n; ++i){
        printf("%d  ", dist[i]);
    }
    printf("\n");
}

void print_name(int counter, char name[][MAX_STR_LEN])
{
    int i;

    for(i = 0; i < counter; i++)
    {
        printf("%s", name[i]);
    }
    printf("\n");
}

I know its not exactly the cleanest of codes, but I'm really confused as why the output is not correct.

[Salem]

Your main is too long to be readable.
Your buffer has no \0 at the end, so strlen will be wrong.
Calling strlen every time around the loop is expensive.

Start with a very simple test case to verify your implementation.

[john.c]

Your problem is with this strange piece of syntax:

    int (*adj_matrix)[counter] = malloc(sizeof * adj_matrix * counter);

It's apparently a weird mixture of VLA and dynamic allocation.

And you don't need to slurp the whole file into a buffer to read it.
Try something like this:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <ctype.h>

#define MAX_LIMIT  999

void error_exit(const char *msg) {
    fprintf(stderr, "Error: %s\n", msg);
    exit(EXIT_FAILURE);
}

int count_names(const char *line) {
    int cnt = 0;
    bool in = false;
    for ( ; *line; line++) {
        if (isspace(*line)) {
            if (in) {
                cnt++;
                in = false;
            }
        }
        else
            in = true;
    }
    return cnt + in;
}

int **create_matrix(int size) {
    int **mat = malloc(size * sizeof *mat);
    if (!mat) error_exit("create_matrix");
    mat[0] = malloc(size * size * sizeof **mat);
    if (!mat[0]) error_exit("create_matrix");
    for (int i = 1; i < size; i++)
        mat[i] = mat[i - 1] + size;
    return mat;
}

void free_matrix(int **mat) {
    free(mat[0]);
    free(mat);
}

void print_matrix(int **adj_matrix, int size) {
    for (int r = 0; r < size; r++) {
        for (int c = 0; c < size; c++)
            if (adj_matrix[r][c] == MAX_LIMIT)
                printf("INF ");
            else
                printf("%3d ", adj_matrix[r][c]);
        printf("\n");
    }
}

void read_matrix(FILE *fp, int **adj_matrix, int size) {
    char line[1000];
    int row = 0;
    while (fgets(line, sizeof line, fp) && row < size) {
        int col = 0;
        char *pline = line;
        int n = 0;

        sscanf(pline, "%*s%n", &n);   // skip name

        for (;;) {
            int val = 0;
            pline += n;
            int ret = sscanf(pline, "%d%n", &val, &n); // try reading int
            if (ret == EOF)
                break;
            else if (ret == 1)
                adj_matrix[row][col] = val;
            else {
                sscanf(pline, "%*s%n", &n);   // skip INF
                adj_matrix[row][col] = MAX_LIMIT;
            }
            col++;
        }
        row++;
    }
}

int main(int argc, char **argv) {
    if (argc != 2) {
        printf ("Usage: ./scc filename\n");
        return -1;
    }
 
    FILE *fp = fopen(argv[1], "r");
    if (!fp) error_exit("Can't open input file");

    char line[1000];
    fgets(line, sizeof line, fp);
    int size = count_names(line);

    int **adj_matrix = create_matrix(size);

    read_matrix(fp, adj_matrix, size);

    print_matrix(adj_matrix, size);

    free_matrix(adj_matrix);

    return 0;
}

[Seaghost]

Thanks for the reply! Yeah my code is a huge mess. I know i can improve my input function, its just that i want to get the bellman ford function working. I have fixed the strlen thing, and a simple test case(1st line of input) returns weird results, with only the 3rd and 4th column being incorrect. I can't seem to find whats wrong with my bellman ford function.