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?