-2

I'm trying to make my own Weighed Graph structure, basing on struct scheme found in net but for some reason i get segfault when I try to execute the code, debugger said that issue is in AddVertex method but unfortunetly, i cannot find it by myself.

 #ifndef graph_h
#define graph_h


typedef struct graphCDT
         *graphADT;


typedef struct vertexTag {
      char *element;
      int visited;
      struct edgeTag *edges;
      struct vertexTag *next;
} vertexT;

typedef struct edgeTag {
     int weight;
     struct vertexTag *connectsTo;
     struct edgeTag *next;
} edgeT;

typedef struct graphCDT {
     vertexT *vertices;
} graphCDT;

#endif


#include "graph.h"
#include "dbg.h"

#include <stdlib.h>
#include <assert.h>

static int RecIsReachable(void *dest,
                          vertexT *startP)
{
  edgeT *edgeP;


  if (startP->visited)
    return 0;


  if (startP->element == dest)
    return 1;


  startP->visited = 1;


  for (edgeP = startP->edges;
           edgeP != NULL;
           edgeP = edgeP->next) {
    if (RecIsReachable(dest, edgeP->connectsTo))
      return 1;
  }


  return 0;
}


int GraphIsReachable(graphADT graph,
                     void *dest,
                     void *source)
{
  vertexT *vertP;
  vertexT *startP = NULL;


  for (vertP = graph->vertices;
           vertP != NULL;
           vertP = vertP->next) {
    vertP->visited = 0;
    if (vertP->element == source)
      startP = vertP;
  }


  if (startP == NULL)
    return 0;


  return RecIsReachable(dest, startP);
}






void AddVertex(graphADT graph, char *element) {

     if(graph == NULL) {
         graph = calloc(1, sizeof(graphADT));
         graph->vertices->element = element;
     } else {

     vertexT *temp = graph->vertices;
     vertexT *n =  calloc(1,sizeof(graphADT));
     n->element = element;

     while(temp != NULL) {
        temp = temp->next;
        }

      temp->next = n;
      n->next = NULL;
     }
}

void AddEdge(graphADT graph,
             int w,
             char *elem1,
             char *elem2) {



      vertexT *to = graph->vertices;
      vertexT *from = graph->vertices;


      while(to != NULL) {
               to = to->next;
               if(to->element == elem2) {
                       break;
               }
         }

        while(from != NULL) {
               from = from->next;
               if(from->element == elem1) {
                       break;
               }
         }
       check(to->element == elem2, "Unnable to found graph which contains elem2");
       check(from->element == elem1, "Unnable to found graph which contains elem1");

      edgeT *temp = from->edges;
      edgeT *temp2 = to->edges;

      while(temp != NULL) {
            temp = temp->next;
      }
      temp->connectsTo = to;
      temp->weight = w;

      while(temp2 != NULL) {
            temp2 = temp2->next;
      }
      temp2->connectsTo = from;
      temp2->weight = w;
error:
   return;

}
int main()
{
    char *test1 = "p";
    char *test2 = "d";
    char *test3 = "t";
    char *test4 = "w";
    char *test5 = "s";
    char *test6 = "x";

    graphADT graph = NULL;
    AddVertex(graph, test1);
    AddVertex(graph, test2);
    AddVertex(graph, test3);
    AddVertex(graph, test4);
    AddVertex(graph, test5);
    AddVertex(graph, test6);

    AddEdge(graph,2,test1, test2);
    AddEdge(graph,3,test1, test3);
    AddEdge(graph,4,test2, test4);
    AddEdge(graph,5,test5,test1);
    AddEdge(graph,6,test6, test3);

    return 0;
}

2 Answers 2

0

Use this type implementation

void ResizeGraph(struct Graph *g) {
    g->array = realloc(g->array , g->v+1);
    if(!g->array) {
        printf("Memory Error");
        return;
    }
    g->array[g->v].head = NULL;
    g->v = g->v+1;
}
-1

Your graphCDT structure has a pointer to vertexT structure, but you forgot to allocate memory for it before using. Add graph->vertices = calloc(1, sizeof(vertexT)); to AddVertex function:

void AddVertex(graphADT graph, char *element) {
     if(graph == NULL) {
         graph = calloc(1, sizeof(graphADT));
         graph->vertices = calloc(1, sizeof(vertexT));
         graph->vertices->element = element;
     } else {
     <...>

Just a quick look, there might be similar errors elsewhere, hope you get an idea to find them by yourself.

3
  • 1
    Also, sizeof(graphADT) in the first calloc() is wrong; that's the size of the pointer, not the size of the structure. As the structure is currently defined, the two sizes may be the same, but it's still a logic error. May 27, 2014 at 14:25
  • Thanks for answer, I'll try it. I thought that allocating memory for struct that contains other structures deals with each of them and additional allocating isn't necessary. May 27, 2014 at 14:26
  • Allocating memory for graph does allocate space for the vertices member, but it only allocates space for the pointer itself; it doesn't allocate a second block of memory to which vertices can point. May 27, 2014 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.