Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

Problem with insert vertex to a graph. (corrected code format)

moranmoran ChinaPosts: 1Member

I have a graph algorithm and want to use it to realize the shortest path problem, but I have trouble when I insert vertex to graph. The first vertex can be inserted successfully, but I seems that I can't insert more. I wrote some printf() function to see where did the problem happen, but I can't see it. Can anyone help me? Here's the code:

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

/ List element structure */
typedef struct ListElmt_
{
    void *data;
    struct ListElmt_ *next;
} ListElmt;

/* List structure */
typedef struct List_
{
    int size;
    int (*match)(const void *key1, const void *key2);
    void (*destroy)(void *data);
    ListElmt *head;
    ListElmt *tail;
} List;

/* Set structure */
    typedef List Set;

/* Graph element structure */
typedef struct AdjList_
{
    void *vertex;
    Set adjacent;
}AdjList;

/* Graph structure */
typedef struct Graph_
{
    int vcount;
    int ecount;
    int (*match)(const void *key1, const void *key2);
    void (*destroy)(void *data);
    List adjlists;
}Graph;

/* Define a structure for vertices in shortest-path problem .*/
typedef struct PathVertex_
{
    void *data;
    double weight;

    VertexColor color;
    double  d;

    struct PathVertex_ *parent;
}PathVertex;

/ *Match function to initialize list, set and graph. */
int _match(const void *key1, const void *key2)
{
    if(key1 == key2)
        return 0;
    else
        return 1;
}

/* Destroy function to initialize list, set and graph. */
void _destroy(void *data)
{
    free(data);
}

#define list_head(list) ((list) -> head)
#define list_tail(list) ((list) -> tail)
#define list_data(element) ((element) -> data)
#define list_next(element) ((element) -> next)

/*list_init*/
void list_init(List *list,void (*destroy)(void *data)) {
    list -> size = 0;
    list -> destroy = destroy;
    list -> head = NULL;
    list -> tail = NULL;

    return;
}

int list_ins_next(List *list, ListElmt *element, const void *data)
 {
    ListElmt      *new_element;

    if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL)
        return -1;

    new_element -> data = (void *)data;
    if(element == NULL) {
        if (list_size(list) == 0)
            list -> tail = new_element;

        new_element -> next = list -> head;
        list -> head = new_element;
    }
    else {

        if (element -> next == NULL)
                    list -> tail = new_element;

        new_element -> next = element -> next;
        element -> next = new_element;
    }

list -> size++;

return 0;
}

void set_init(Set *set, int (*match)(const void *key1, const void *key2), void (*destroy)(void *data))
{
    list_init(set, destroy);
    set -> match = match;
    return;
}

//graph_init
void graph_init(Graph *graph, int (*match)(const void *key1, const void *key2), void(*destroy)(void *data))
{
        graph -> vcount = 0;
        graph -> ecount = 0;
        graph -> match = match;
        graph -> destroy = destroy;

        list_init(&graph -> adjlists, NULL);

        return;
}

int graph_ins_vertex(Graph *graph, const void *data)
{
    ListElmt *element;
    AdjList *adjlist;
    int retval;

    for(element = list_head(&graph -> adjlists); element != NULL; element = list_next(element))
        {
    if(graph -> match(data, ((AdjList *)list_data(element)) -> vertex))
        return 1;
}

if((adjlist = (AdjList *)malloc(sizeof(AdjList))) == NULL)
    return -1;


adjlist -> vertex = (void *)data;
set_init(&adjlist -> adjacent, graph -> match, NULL);
if((retval = list_ins_next(&graph -> adjlists, list_tail(&graph -> adjlists), adjlist)) != 0)
{
    return retval;
}

graph -> vcount++;
return 0;
}

int main()
{
    Graph _graph;
    Graph *graph = &_graph;
    PathVertex pvertex1,
                *pathvertex1 = &pvertex1;
    char city[6] = {'a','b','c','d','e','f'};
    int i = 0;

    int (*match)(const void *key1, const void *key2);
    void (*destroy)(void *data);

    /*Match and destroy function. Use void pointer to realize.*/
    match = &_match;
    destroy = &_destroy;

    /* Initialize graph. */
    graph_init(graph, match, destroy);

    /* Insert vertex to graph. */
    for(i; i < 6; ++i)
    {
        pathvertex1 -> data = &_city[i];
        graph_ins_vertex(graph, (const PathVertex *)pathvertex1);
    }

    return 0;
}
Tagged:
Sign In or Register to comment.