-1

I implemented a program which is supposed to find minimum spanning tree using Prim. The graph's edges are described in a file.

So first of all, the program reads this file and stocks edges in a data structure. After that, it runs the algorithm. Here is the full code :

      #include <stdio.h>


    #include <stdlib.h>

      #define MAXVERTICES 1000
      #define INFINITY 99999
      #define TAILLEMAX 100

      struct vertex {
            int visited, predecessor;
            int dist;   // distance qui sépare ce noeud de la distance minimale d'un autre noeud
      };

      int treeEdge[MAXVERTICES][2], mstCost; // tableau des 'aretes' qui constituent l'arbre couvrant
      int graphEdge[MAXVERTICES][MAXVERTICES], nodeCount; // matrice d'adjacences (couts séparant chaque sommet des autres sommets)
      struct vertex node[MAXVERTICES];  // tableau de sommets numérotés de 1 à n

      /* construct the input graph */

      void buildGraph() {
            int source, dest, weight, test;
            char temp[TAILLEMAX];

        FILE* fichier = NULL;
        fichier = fopen("inst_v100.txt", "r");
        if (fichier != NULL)
        {
            fgets(temp, TAILLEMAX, fichier); // sauter ligne
            fscanf(fichier,"%s%d",temp,&nodeCount); // nbr de sommets
            fgets(temp, TAILLEMAX, fichier);
            fgets(temp, TAILLEMAX, fichier);

            while (1)
            {
                    test = fscanf(fichier,"%d%d%d",&source,&dest,&weight);
                    if(test==0)
                        break;
                    /* update weight of the edge */
                    graphEdge[source][dest] = weight;
                    graphEdge[dest][source] = weight;
                    fgets(temp, TAILLEMAX, fichier); // sauter ligne
            }
        }
        fclose(fichier);
        return;
  }



    /* all vertices are visited or not */
      int allVisited() {
            int i;
            for (i = 0; i < nodeCount; i++)
                    if (node[i].visited == 0)
                            return 0;
            return 1;
      }

      /* construct minimum spanning tree */
      int buildTree() {
            int i = 0, count = 0, currentNode, mindist;
            while (i < nodeCount) {
                    node[i].visited = 0;
                    node[i].predecessor = 0;
                    node[i].dist = INFINITY;
                    i++;
    }

        node[0].visited = 1;
        node[0].dist = 0;

        currentNode = 0;
        while (allVisited() == 0) {
                for (i = 0; i < nodeCount; i++) {  // pour le sommet courant, chercher la distance min qui le sépare de chaque sommet

                        /* Find the adjacent vertices and update the edge lenght */
                        if(graphEdge[currentNode][i] > 0 && node[i].visited == 0) {
                                if (graphEdge[currentNode][i] < node[i].dist) {
                                        node[i].predecessor = currentNode;
                                        node[i].dist = graphEdge[currentNode][i];
                                }
                        }
                }

                mindist = INFINITY;
                /* trouver l'arete avec le poids minimum */
                for (i = 0; i < nodeCount; i++) {
                        if (node[i].dist < mindist && node[i].visited == 0) {
                                mindist = node[i].dist;
                                currentNode = i;
                        }
                }
                /* Mark the vertex as visited - edge with min cost */
                node[currentNode].visited = 1;
                treeEdge[count][0] = node[currentNode].predecessor;
                treeEdge[count][1] = currentNode;

                /* calculate cost of MST */
                mstCost = mstCost + graphEdge[treeEdge[count][0]][treeEdge[count][1]];
                count++;
        }
        return count;
  }

  int main() {
        int i, count1;

        /* construct graph */
        buildGraph();
        count1 = buildTree();
        printf("MST is composed of below edges:\n");
        for (i = 0; i < count1; i++) {
                printf("%d<->%d\n", treeEdge[i][0], treeEdge[i][1]);
        }
        printf("\n");
        printf("Cost of Minimum Spanning Tree: %d\n", mstCost);
        return 0;
  }

Awkwardly, when the execution starts, the program sends a SIGSEV signal.

could you help me figure out the mistake i'm doing ? Thank's in advance.

codeless
  • 145
  • 5
  • 14
  • "When the execution starts"??? Couldn't you come up with a slightly more accurate description??? – barak manos Dec 26 '14 at 08:17
  • it means when i start the programs'execution, sorry for my bad english, that's why i cant' explain efficiently. @SouravGhosh I'll add some details about the content of the file, i should've precised that the contains more than 4950 line. – codeless Dec 26 '14 at 08:20
  • 1
    `gdb` is your friend. At the very least we'll need to know **where** the program is crashing. It could be as simple as the file not being found, and the program [segfaulting in `fclose(NULL)`](http://stackoverflow.com/questions/16922871/why-glibcs-fclosenull-cause-segmentation-fault-instead-of-returning-error). – NPE Dec 26 '14 at 08:21
  • gdb says the error is in this line : treeEdge[count][0] = node[currentNode].predecessor; – codeless Dec 26 '14 at 08:25
  • I din't look hard enough, but i cannot see and bound check for `count` and `nodeCount`. – Sourav Ghosh Dec 26 '14 at 09:10

1 Answers1

0

Problem Solved.

In fact if you look closely, i used fgets and fscanf and it caused ambiguity. The solution was using fgets (to store the line read in a string), then sscanf to take informatio needed from that string.

It gives something like this :

    fgets(the_string, MAXLENGTH, file);
    sscanf(the_string,"%d",&number_wanted);

thank you very much anyway, and i hope my answer will be helpful for other people with same problem.

codeless
  • 145
  • 5
  • 14