Thread: C Programming **GRAPH**

So my professor informed the class that he will not be available to answer emails this weekend due to whatever reason, so im hoping that i will be able to get decent responses here

I have been implementing a graph, using vertex and adj_vertex structure types, and am having trouble linking the adjacency lists together. Below is the header file as well as the implementation.

======================HEADER======================

Code:

/* forward declarations so self-referential structures are simpler */
typedef struct vertex vertex_t;    /*use vertex_t*/
typedef struct adj_vertex adj_vertex_t;

struct vertex {
        char *name;             /*char pointer name*/
        adj_vertex_t *adj_list; /*pointer to adj_vertex_t type to a list of adj_vertex*/
        vertex_t *next;         /*pointer to vertex_t named next*/
};

struct adj_vertex {
        vertex_t *vertex;
        int edge_weight;
        adj_vertex_t *next;
};

/* This is the one function you really should implement as part of your
 * graph data structure's public API.
 *
 * `add_edge` adds the specified edge to the graph passed in via the first
 * argument. If either of the edge's vertices are not already in the graph,
 * they are added before their adjacency lists are updated. If the graph
 * is currently empty (i.e., *vtxhead == NULL), a new graph is created,
 * and the caller's vtxhead pointer is modified.
 *
 * `vtxhead`: the pointer to the graph (more specifically, the head of the
 *            list of vertex_t structures)
 * `v1_name`: the name of the first vertex of the edge to add
 * `v2_name`: the name of the second vertex of the edge to add
 * `weight` : the weight of the edge to add
 */
void add_edge (vertex_t **vtxhead, char *v1_name, char *v2_name, int weight);

vertex_t* add_vertex (vertex_t **vtxhead, char *v_name);
=========================END HEADER=================

=================GRAPH.C==========================
[mposch@ada 2_graphlab]$ nano graph.c
  GNU nano 2.0.9                                               File: graph.c

#include <stdlib.h>
#include <string.h>
#include "graph.h"

vertex_t* add_vertex(vertex_t **vtxhead, char *v_name)
{
        vertex_t *p, *vtx= malloc(sizeof(vertex_t));
        /*adj_vertex_t *adj_v;*/

        vtx->name = malloc((strlen(v_name)+1)*sizeof(char));
        strcpy(vtx->name,v_name);
        vtx->adj_list = NULL;
        vtx->next =NULL;

        return vtx;
}
void add_edge (vertex_t **vtxhead, char *v1_name, char *v2_name, int weight) {

vertex_t *iter, *p, *temp;
adj_vertex_t *adj_v;
int new =0, count;

        if (*vtxhead == NULL)
        {
        p =*vtxhead = add_vertex(vtxhead, v1_name);               /**vtxhead = p = add_vertex(vtxhead, v1_name);*/
        adj_v = p->adj_list = malloc(sizeof(adj_vertex_t));
        temp = p;

        p = p->next = add_vertex(vtxhead, v2_name);
        /*update adj lists*/
        adj_v->vertex=p;
        adj_v->edge_weight = weight;
        adj_v->next = NULL;

        adj_v = p->adj_list = malloc(sizeof(adj_vertex_t));
        adj_v-> vertex = temp;
        adj_v->edge_weight = weight;
        count =2;
        }
        else{
       for (iter= *vtxhead; iter != NULL; iter = iter->next)    /*if not null, then search to see if one of the names passed in matches any existing vertice*/
       {
                if (count >= 5)                                 /*if 5, all 5 vtx's added*/
                break;
               if(strcmp(iter->name,v1_name)!=0)
               new=1;

            if(strcmp(iter->name,v2_name)!=0)
                new=2;

       }/*end for*/

        if (new==1){
           temp = p;
           p = p->next = add_vertex (vtxhead, v1_name);
           count +=1;
          /* adj_v = p->adj_list = malloc(sizeof(adj_vertex_t));
           adj_v->vertex = temp;
           adj_v->edge_weight = weight;
           adj_v->next = NULL;
           adj_v = temp->adj_list = malloc(sizeof(adj_vertex_t));
           adj_v->vertex =p;
           adj_v->edge_weight = weight;
           */
        }
        if (new==2){
           temp = p;
           p = p->next = add_vertex (vtxhead, v2_name);
           count+=1;
          /* adj_v = p->adj_list = malloc(sizeof(adj_vertex_t));
   adj_v->vertex = temp;
           adj_v->edge_weight = weight;
           adj_v->next = NULL;

           adj_v = temp->adj_list = malloc(sizeof(adj_vertex_t));
           adj_v->vertex =p;
           adj_v->edge_weight = weight;
        */
        }

}/*end else*/

}

======================end graph.c==================

in main, i am using calls like
add_edge(&vlist_head, "Chicago", "Plainfield", 30);
add_edge(&vlist_head, "Chicago", "OakPark", 8);
add_edge(&vlist_head, "OakPark", "Evanston", 14);
add_edge(&vlist_head, "Evanston", "Schaumburg", 24);
add_edge(&vlist_head, "Schaumburg", "Chicago", 30);
add_edge(&vlist_head, "Evanston", "Chicago", 12);

to create the graph. My issue is linking the adj_lists for each vertex. As far as i understand, you only have to specify the edge between vertices in one direction, meaning if you specify an edge from A to B, you do not need to re-specify for B to A. The correct output should be (in no specific order):
Adjacency list:
Chicago: OakPark(8) Evanston(12) Schaumburg(30) Plainfield(30)
OakPark: Chicago(8) Evanston(14)
Evanston: Chicago(12) OakPark(14) Schaumburg(24)
Schaumburg: Chicago(30) Evanston(24)
Plainfield: Chicago(30)



However my output is as folllows:
Adjacency list:
Chicago: Plainfield(30)
Plainfield: Chicago(30)
OakPark:
Evanston:
Schaumburg:

if my attempt of linking (done in the strcmp loop) is uncommented, my output is :
Adjacency list:
Chicago: Plainfield(30)
Plainfield: OakPark(8)
OakPark: Evanston(14)
Evanston: Schaumburg(24)
Schaumburg: Evanston(24)

Please can anyone give me some sort of rundown on what concept i am missing?

As a general note, you should use include guards in all your header files. Google will explain more.

Also, in add_edge, you never initialize count. It's not a big deal on the first run, when *vtxhead is NULL, but after that, it's got some bogus stack value (it's not remembered between function calls).

You only want to set new1 or new2 if you've traversed the entire list and that name isn't in there. Also, this setup doesn't handle both names being new. new can only be 1 or 2, thus you can't add 2 new names at once (except in your first case).

That's all I have time for at the moment.

thanks for the reply. I know i am not initializing count, for some reason i seg fault if count or *p is initialized

Okay, I think the best thing to do is tackle this top-down. That means start with the highest level and fill in layer by layer until it's all done. Start writing the add_edge routine as just comments or pseudo code. Single lines/sentences that describe one thing to do. Then, each one of those becomes a function. Wash, rinse, repeat. To get you started, adding an edge involves:

Code:

finding the current vertex if it exists (call it v1)
creating one if it doesnt (still call it v1)
adding the other vertex (v2) to the adjacency list of v1

Do the same process for v2.

I think I just noticed you don't traverse the adj_list and add the new neighbor, you simply overwrite the current list. A good trick for list management, since you don't care about order, is simply prepending it (putting it at the beginning):

Code:

list_t *add_node_to_list(list_t *head, list_t *new_node)
{
    new_node->next = head;
    return new_node;
}

int main(void)
{
    list_t *main_list = NULL;  // this initializes the list to empty
    list_t *node;

    node = new_node("foobar");  // create a new node "foobar"
    main_list = add_node_to_list(main_list, node);  // stick it at the beginning of main_list
...
}

thanks again for another response! Im gunna try to tackle this issue of "overwritting" my list right now, and now that you say that it makes sense, just gotta find out exactly how/where its being overwritten.
Thanks AGAIN ill post my progress.