Creating adjacency matrix from graph

Question

I am trying to create an adjacency matrix from a graph file.

I need to read in a text file containing the number of vertices, then lists the graph format

Ex:

5
0 3 2
1 0 2
1 2 2
1 4 1

The first column of numbers is for the id of source vertex, the second column is for the id of target vertex, and the third column is the weight of edge

So this should return the matrix

0 2 0 2 0
2 0 2 0 1
0 2 0 0 0
2 0 0 0 0
0 1 0 0 0

So far I have read the text file and gotten the number of vertices but I'm not sure on what to do from here.

My current code:

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

int main (){

    printf("Enter the file contianing the graph\n");

    char filename[20];
    FILE *myFile;
    scanf("%s",filename);
    myFile = fopen (filename,"r");

    int number_of_nodes, number_of_edges;
    int source_id[100], target_id[100], weight[100];
    int matrix[100][100];
    int i;      
    if (myFile == NULL){
        printf("File not found! Exiting...\n");
        return -1;
    }
    else{
        fscanf(myFile, "%d", &number_of_nodes);
        printf("There are %d vertices.\n", number_of_nodes);
        for(i = 0; i < (sizeof (source_id) / sizeof ( source_id[0] )); i++)
        {
 if( fscanf(myFile, "%d %d %d", &source_id[i], &target_id[i], &weight[i]) != 3)
           break;

        }
        number_of_edges = i;  

        for (i = 0; i<99;i++){
        for (int j = 0; j< 99; i++){
        matrix[i][j]=0;
        }
        }

        for (i = 0;  i < number_of_edges; i++){
          int x = source_id[i];
          int y = target_id[i];
          matrix[x][y] = weight[i];
          matrix[y][x] = weight[i];
          }

          for (int y = 0; y < (number_of_nodes-1); y++){
            for (int x = 0; x < (number_of_nodes -1); x++){
              printf(matrix[x][y]);
              printf(" \n");
            } 
         } 

    }


    fclose(myFile);

    return 0;
}

Answer 1

Since you only posted the code for reading the file, I'll just comment on and improve that part.

First, you can define your variables in a better way. In the below code I removed your numberArray and instead, defined a number_of_nodes and three separate arrays for sources, targets and weights. This makes it easier to refer to these data later.

Second, since you don't have the number of items (edges) in the file, you must check if a read is successful by looking at the return value of fscanf(). It returns the number of elements that are successfully read. In your case, you're reading 3 numbers at a time, so you can just compare the return value with 3. You would also like to store the value of i after exiting the loop, so you'll know later how many edges are actually read.

Third, using scanf("%s") is as bad as using gets() (Why is it bad?). You should probably look into limiting the input length, for example using scanf("%19s"). I didn't fix it in the below code as it's not a direct issue, but should be taken into account in your later development.

And finally, +1 for your file open check. It's a good practice to ensure that previous actions completed successfully before proceeding.

Here's my fixed code:

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

int main() {
    printf("Enter the file contianing the graph\n");

    char filename[20];
    FILE *myFile;
    scanf("%s", filename);
    myFile = fopen(filename, "r");

    int number_of_nodes, number_of_edges;
    int source_id[100], target_id[100], weight[100];

    int i;
    if (myFile == NULL) {
        printf("File not found! Exiting...\n");
        return -1;
    }
    else {
        fscanf(myFile, "%d", &number_of_nodes);
        printf("There are %d vertices.\n", number_of_nodes);
        for (i = 0; i < (sizeof(source_id) / sizeof(source_id[0])); i++) {
            if (fscanf(myFile, " %d %d %d", &source_id[i], &target_id[i], &weight[i]) != 3)
                break;
        }
        number_of_edges = i;
    }

    fclose(myFile);

    return 0;
}

---

For what to do next, I'll give you some tips instead of writing the full code directly. It's relatively easy if you get the point.

You would like to create a "matrix", or in the words of C, an array of arrays. To be simple, it should look like this

int matrix[100][100];

You can then initialize the matrix and reset it to zero:

// This is pseudo-code
for i = 0 to 99
  for j = 0 to 99
    matrix[i][j] = 0

And then based on what you have read from the file, you can assign the values to the zeroed-out matrix. Remember to assign two values (x to y and y to x)

for edge in edges
  x = edge.source
  y = edge.target
  matrix[x][y] = edge.weight
  matrix[y][x] = edge.weight

To print out the matrix, just go through it by row. Don't forget to print a newline after each row.

for y = 0 to (number_of_nodes - 1)
  for x = 0 to (same as above)
    print matrix[x][y] and a space
  print a newline

If you can understand all the above ideas, then you're good to go.