I'm stuck with creating an arc between two nodes, could someone provide me with a pseudo code, which will help me to continue? I can't understand how to populate the adjacency list of each node pointer of the City array. From what I understand, the id_tail should be the vertex of the first node of the adjacency list, while the id_head should be the vertex of the destination node. Below is the code, in which I inserted some test functions.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTICES 20
#define DIM 50
#define NUM_NODES_TEST 11
typedef struct node
{
int vertex_id;
struct node* link;
}Node;
typedef struct
{
char name[DIM];
int population;
char country[DIM];
Node* list_adj;
}City;
void load_city_test(City graph[]);
void load_directed_graph_test(City graph[], int num_nodes);
void create_arc(City graph[], int id_tail, int id_head, int num_nodes);
void print_list_adj(City graph[], int num_nodes);
int main()
{
City graph[MAX_VERTICES];
int num_nodes = 0;
load_city_test(graph);
for (int i = 0; i < NUM_NODES_TEST; ++i) {
printf("%s\n", graph[i].name);
}
load_directed_graph_test(graph, NUM_NODES_TEST);
print_list_adj(graph, NUM_NODES_TEST);
}
void load_city_test(City graph[])
{
strcpy(graph[0].name, "Cagliari");
strcpy(graph[0].country, "Italy");
graph[0].population = 300000;
graph[0].list_adj = NULL;
strcpy(graph[1].name, "Zurich");
strcpy(graph[1].country, "Switzerland");
graph[1].population = 400000;
graph[1].list_adj = NULL;
strcpy(graph[2].name, "Lyon");
strcpy(graph[2].country, "France");
graph[2].population = 500000;
graph[2].list_adj = NULL;
strcpy(graph[3].name, "Genoa");
strcpy(graph[3].country, "Italy");
graph[3].population = 800000;
graph[3].list_adj = NULL;
strcpy(graph[4].name, "Rome");
strcpy(graph[4].country, "Italy");
graph[4].population = 4000000;
graph[4].list_adj = NULL;
strcpy(graph[5].name, "New York");
strcpy(graph[5].country, "USA");
graph[5].population = 8500000;
graph[5].list_adj = NULL;
strcpy(graph[6].name, "Bilbao");
strcpy(graph[6].country, "Spain");
graph[6].population = 350000;
graph[6].list_adj = NULL;
strcpy(graph[7].name, "Berlin");
strcpy(graph[7].country, "Germany");
graph[7].population= 3500000;
graph[7].list_adj = NULL;
strcpy(graph[8].name, "London");
strcpy(graph[8].country, "Great Britain");
graph[8].population = 8700000;
graph[8].list_adj = NULL;
strcpy(graph[9].name, "Miami");
strcpy(graph[9].country, "USA");
graph[9].population = 450000;
graph[9].list_adj = NULL;
strcpy(graph[10].name, "Tokyo");
strcpy(graph[10].country, "Japan");
graph[10].population = 13700000;
graph[10].list_adj = NULL;
}
void load_directed_graph_test(City graph[], int num_nodes)
{
load_city_test(graph);
create_arc(graph, 0, 1, num_nodes);
create_arc(graph, 0, 4, num_nodes);
create_arc(graph, 1, 0, num_nodes);
create_arc(graph, 1, 2, num_nodes);
create_arc(graph, 2, 1, num_nodes);
create_arc(graph, 2, 3, num_nodes);
create_arc(graph, 4, 0, num_nodes);
create_arc(graph, 4, 1, num_nodes);
create_arc(graph, 4, 5, num_nodes);
create_arc(graph, 4, 6, num_nodes);
create_arc(graph, 5, 1, num_nodes);
create_arc(graph, 6, 7, num_nodes);
create_arc(graph, 8, 9, num_nodes);
create_arc(graph, 9, 8, num_nodes);
create_arc(graph, 9, 10, num_nodes);
}
void create_arc(City graph[], int id_tail, int id_head, int num_nodes)
{
Node* newnode;
newnode = malloc(sizeof(Node));
if (!newnode)
printf("Not allocated!\n");
else{
for (int i = 0; i < num_nodes; ++i) {
newnode->vertex_id = id_tail;
graph[i].list_adj = newnode;
/*I'm stuck here*/
}
}
}
void print_list_adj(City graph[], int num_nodes)
{
for (int i = 0; i < num_nodes; ++i) {
printf("%s\n", graph[i].name);
}
}
After the first answer, I wrote this code, but I can't understand how to use the number of nodes, passed as parameter in the function.
void create_arc(City graph[], int id_tail, int id_head, int num_nodes)
{
Node *newnode = malloc(sizeof(Node)), *prec = NULL, *curr = graph[id_tail].list_adj;
while (curr && curr->vertex_id < id_head){
prec = curr;
curr = curr->link;
}
newnode = malloc(sizeof(Node));
if (!newnode)
return;
newnode->vertex_id = id_head;
if (!prec){ //insert on top
newnode->link = graph[id_tail].list_adj;
grafo[id_tail].list_adj = newnode;
} else{ //insert middle or tail
prec->link = newnode;
newnode->link = curr;
}
}
City graph[] is your whole graph, but each City reference adjacent nodes via City.list_adj
and you would treat Node/struct node as a linked list
So I would alter create_arc in this manner:
// shorthand reference
// initialize new node
Node *newnode = malloc(sizeof(Node));
if(newnode == NULL ) {abort();} // prefer spelling out the test.
newnode->vertex_id = tail;
newnode->link=NULL; // not necessary
// insert our new arc at the head of the linked list
City *current = &(graph[head]);
newnode->link = current->list_adj;
current->list_adj = newnode;
Step by step:
City.list_adj -> NULLCity.list_adj -> NULL , insert0 -> NULLCity.list_adj -> insert0 -> NULLCity.list_adj -> insert0 -> NULL , insert1 -> Insert0 ...City.list_adj -> insert1 -> insert0 -> NULL
...You could also try inserting at the end of the list, but you would have to search for the list end.
For inserting in order you would have to alter the code the following way:
City *current = &(graph[head]);
// list is size 0 no need to look further
if(current->list_adj == NULL) {
current->list_adj = newnode;
return;
}
// insert at the head of the list
if(current->list_adj->vertex_id > head) {
newnode->link = current->list_adj;
current->list_adj = newnode;
return;
}
// look at the rest of the list to find
Node *insert_point = current->list_adj;
while(insert_point->link != NULL) {
if(insert_point->link->vertex_id > head) { break; }
insert_point = insert_point->link;
}
newnode->link = insert_point->link;
insert_point->link = newnode;