LinuxQuestions.org
Help answer threads with 0 replies.
Home Forums Tutorials Articles Register
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 10-23-2003, 07:18 AM   #1
bprasanth_20
Member
 
Registered: Oct 2003
Posts: 42

Rep: Reputation: 15
Question implementing a graph


please help me. i am not getting display of graph properly.

/*graph.h*/

#ifndef GRAPH_H
#define GRAPH_H

#include <stdlib.h>

#include "list.h"
#include "set.h"

typedef struct AdjList_ {

void *vertex;
Set adjacent;

} AdjList;

typedef struct Graph_ {

int vcount;
int ecount;

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

List adjlists;

} Graph;

typedef enum VertexColor_ {white, gray, black} VertexColor;

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

void graph_destroy(Graph *graph);

int graph_ins_vertex(Graph *graph, const void *data);

int graph_ins_edge(Graph *graph, const void *data1, const void *data2);

int graph_rem_vertex(Graph *graph, void **data);

int graph_rem_edge(Graph *graph, void *data1, void **data2);

int graph_adjlist(const Graph *graph, const void *data, AdjList **adjlist);

int graph_is_adjacent(const Graph *graph, const void *data1, const void *data2);

#define graph_adjlists(graph) ((graph)->adjlists)

#define graph_vcount(graph) ((graph)->vcount)

#define graph_ecount(graph) ((graph)->ecount)

#endif
 
Old 10-23-2003, 07:19 AM   #2
bprasanth_20
Member
 
Registered: Oct 2003
Posts: 42

Original Poster
Rep: Reputation: 15
/*graph.c*/

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

#include "graph.h"
#include "list.c"
#include "set.c"

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;

}

void graph_destroy(Graph *graph) {

AdjList *adjlist;

while (list_size(&graph->adjlists) > 0) {

if (list_rem_next(&graph->adjlists, NULL, (void**)&adjlist) == 0) {

set_destroy(&adjlist->adjacent);

if (graph->destroy != NULL)
graph->destroy(adjlist->vertex);

free(adjlist);

}

}

list_destroy(&graph->adjlists);

memset(graph, 0, sizeof(Graph));

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;

}
 
Old 10-23-2003, 07:20 AM   #3
bprasanth_20
Member
 
Registered: Oct 2003
Posts: 42

Original Poster
Rep: Reputation: 15
/*implementation of graphs*/

#include "graph.c"


int data_match (void *key1, void *key2)
{

if(key1 == key2)
return 1;

else
return 0;

}

int list_display(List *list)
{

ListElmt *element;

printf("\nThe vertices in the graph are : ");
for(element = list_head(list); element != NULL; element = list_next(element))
printf("%d ", list_data(element));

}

int main()
{

int choice, num, sour, dest, flag = 0;
Graph *graph;

printf("\n\n\n*****IMPLEMENTATION OF GRAPHS***\n");

start: printf("\n1. Initialize a graph");
printf("\n2. Insert a vertex in the graph");
printf("\n3. Insert an edge in the graph");
printf("\n4. Delete a vertex from the graph");
printf("\n5. Delete an edge from the graph");
printf("\n6. Display the graph");
printf("\n7. Destroy the graph");
printf("\n8. Exit");
printf("\n Enter your choice : ");

choice: scanf("%d", &choice);

if(choice == 8)
return -1;

if (choice > 8)
{
printf("No such choice. Enter choice again : ");
goto choice;
}

if(choice != 1 && flag == 0)
{
printf("Unless a graph is created, this operation is invalid.\n");
goto start;
}

switch(choice)
{

case 1:

if (flag == 1)
{
printf("\nA graph is in use. Destroy it before initialing a new graph.\n");
goto start;
}

graph = malloc(sizeof(Graph));
graph_init(graph, data_match, NULL);

printf("\nThe graph is initialized.\n");

flag = 1;

goto start;

case 2:

printf("\nEnter the vertex to be inserted in the graph : ");
scanf("%d", &num);

if (graph_ins_vertex(graph, num) == 1)
printf("The vertex already exists.\n");
else
printf("The new vertex is inserted in the graph.\n");

goto start;

case 3:

printf("\nEnter the source vertex : ");
scanf("%d", &sour);

printf("Enter the terminating vertex : ");
scanf("%d", &dest);

if (graph_ins_edge(graph, sour, dest) == -1)
printf("Either one of the vertices may be wrong or the edge already exists.\n");
else
printf("The new edge is inserted in the graph.\n");

goto start;

case 4:

printf("\nEnter the vertex to be removed : ");
scanf("%d", &num);

if (graph_rem_vertex(graph, &num) == 0)
printf("The vertex is removed.\n");
else
printf("Either edges incident to/from the vertex may not be deleted or it is not present.\n");

if (graph->vcount == 0)
{
flag = 0;
printf("The graph is empty. The graph is destroyed.\n");
graph_destroy(graph);
}

goto start;

case 5:

printf("\nEnter the source vertex of the edge to be removed : ");
scanf("%d", &sour);

printf("Enter the terminating vertex of the edge to be removed : ");
scanf("%d", &dest);

if (graph_rem_edge(graph, sour, &dest) == 0)
printf("The edge is removed.\n");
else
printf("Either one of the vertices may be wrong or the edge does not exist.\n");

goto start;

case 6:

printf("\nThe graph is decribed as follows :");
list_display(&graph_adjlists(graph));

goto start;

case 7:

graph_destroy(graph);
printf("\nThe graph is destroyed.\n");

flag = 0;

goto start;


}

}
 
Old 10-23-2003, 07:20 AM   #4
bprasanth_20
Member
 
Registered: Oct 2003
Posts: 42

Original Poster
Rep: Reputation: 15
int graph_ins_edge(Graph *graph, const void *data1, const void *data2) {

ListElmt *element;

int retval;

for (element = list_head(&graph->adjlists); element != NULL; element = list_next(element)) {

if(graph->match(data2, ((AdjList *)list_data(element))->vertex))
break;

}

if (element == NULL)
return -1;

for (element = list_head(&graph->adjlists); element != NULL; element = list_next(element)) {

if(graph->match(data1, ((AdjList *)list_data(element))->vertex))
break;

}

if (element == NULL)
return -1;

if ((retval = set_insert(&((AdjList *)list_data(element))->adjacent, data2)) != 0) {

return retval;

}

graph->ecount++;

return 0;

}

int graph_rem_vertex(Graph *graph, void **data) {

ListElmt *element,
*temp,
*prev;

AdjList *adjlist;

int found;

prev = NULL;
found = 0;

for (element = list_head(&graph->adjlists); element != NULL; element = list_next(element)) {

if (set_is_member(&((AdjList *)list_data(element))->adjacent, *data))
return -1;

if (graph->match(*data, ((AdjList *)list_data(element))->vertex)) {

temp = element;
found = 1;

}

if (!found)
prev = element;

}

if(!found)
return -1;

if(set_size(&((AdjList *)list_data(temp))->adjacent) > 0)
return -1;

if (list_rem_next(&graph->adjlists, prev, (void **)&adjlist) != 0)
return -1;

*data = adjlist->vertex;
free(adjlist);

graph->vcount--;

return 0;

}

int graph_rem_edge(Graph *graph, void *data1, void **data2) {

ListElmt *element;

for (element = list_head(&graph->adjlists); element != NULL; element = list_next(element)) {

if (graph->match(data1, ((AdjList *)list_data(element))->vertex))
break;

}

if (element ==NULL)
return -1;

if(set_remove(&((AdjList *)list_data(element))->adjacent, data2) != 0)
return -1;

graph->ecount--;

return 0;

}

int graph_adjlist(const Graph *graph, const void *data, AdjList **adjlist) {

ListElmt *element,
*prev;

prev = NULL;

for (element = list_head(&graph->adjlists); element != NULL; element = list_next(element)) {

if (graph->match(data, ((AdjList *)list_data(element))->vertex))
break;

prev = element;

}

if (element == NULL)
return -1;

*adjlist = list_data(element);

return 0;

}

int graph_is_adjacent(const Graph *graph, const void *data1, const void *data2) {

ListElmt *element,
*prev;

prev = NULL;

for (element = list_head(&graph->adjlists); element != NULL; element = list_next(element)) {

if (graph->match(data1, ((AdjList *)list_data(element))->vertex))
break;

prev = element;

}

if (element == NULL)
return 0;

return set_is_member(&((AdjList *)list_data(element))->adjacent, data2);

}
 
Old 10-24-2003, 11:44 PM   #5
bprasanth_20
Member
 
Registered: Oct 2003
Posts: 42

Original Poster
Rep: Reputation: 15
Question PLEASE HELP ME

please help me solve to solve the problem of displaying a graph in the program i sent as implementing a graph
 
  


Reply



Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
Implementing mmap Kumar Programming 0 09-08-2005 03:12 AM
implementing a firewall nitinatindore Linux - Security 1 01-04-2005 09:21 AM
implementing ping? pcdude Programming 4 11-03-2004 03:57 AM
Graph in Qt manjula_rajan Programming 0 03-18-2004 02:09 AM
Implementing GRsecurity int0x80 Linux - Security 13 09-30-2002 03:31 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 02:59 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration