Avrei bisogno di un aiuto sempre inerente alla gestione dei voli...devo fare in modo che quando inserisco il nodo poi vengono inserite anche la relativa tratta cosi come il grafo viene stampato ti posto il codice:
dovrei tipo poter aggiungere questo: [id:19, city: Taranto] --> (id: 13, city: Catania, costo:60.67, distanza:479.69) per ora mi da solo questo:[id:19, city: Taranto]
Potete aiutarmi la funzioni di aggiungi nodo già c'è l'ho
C:
Grafo.c
C:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include <string.h>
#include <math.h>
#include "Graph.h"
#include "List.h"
#include "Queue.h"
#define BUFFER_SIZE 256
Graph initGraph(int nodes_count, char** cityNames) {
Graph G = (Graph)malloc(sizeof(struct TGraph));
assert(G != NULL);
G->adj = (List *)calloc(nodes_count, sizeof(List));
assert(G->adj != NULL);
G->nodes_count = nodes_count;
G->cityNames = cityNames;
return G;
}
void freeGraph(Graph G) {
if (G != NULL) {
if (G->nodes_count > 0) {
int i = 0;
for (i = 0; i < G->nodes_count; i++) {
G->adj[i] = freeList(G->adj[i]);
free(G->cityNames[i]);
}
}
free(G->adj);
free(G->cityNames);
free(G);
}
}
void addEdge(Graph G, int source, int target, double prezzo, double distanza) {
assert(G != NULL);
assert(source < G->nodes_count);
assert(target < G->nodes_count);
if (source != target) {
G->adj[source] = appendNodeList(G->adj[source], target, prezzo, distanza);
}
}
List removeEdge(Graph G, int source, int target) {
assert(G != NULL);
assert(source < G->nodes_count);
assert(target < G->nodes_count);
if (source != target) {
G->adj[source] = removeNodeList(G->adj[source], target);
}
return G->adj[source];
}
void addNode(Graph G, char* newCity) {
if (G != NULL) {
List * old=G->adj;
char** old_matrix = G->cityNames;
int i=0;
G->adj = (List *)calloc(G->nodes_count+1, sizeof(List));
assert(G->adj != NULL);
G->cityNames = (char**)calloc(G->nodes_count+1, sizeof(char*));
assert(G->cityNames != NULL);
for(i=0;i<G->nodes_count;i++){
G->adj[i]=old[i];
G->cityNames[i] = old_matrix[i];
}
G->nodes_count += 1;
G->adj[G->nodes_count-1] = NULL;
G->cityNames[G->nodes_count-1] = (char*) calloc(strlen(newCity)+1, sizeof(char));
assert(G->cityNames[G->nodes_count-1] != NULL);
strcpy(G->cityNames[G->nodes_count-1], newCity);
}
}
void removeNodeByIndex(Graph G, int node_to_remove) {
if (G != NULL) {
if(node_to_remove >= G->nodes_count || node_to_remove < 0){
// il nodo da rimuovere non appartiene al grafo
return;
}
int i = 0;
int x = 0;
List *tmp = G->adj;
char** old_matrix = G->cityNames;
G->adj = (List *)calloc(G->nodes_count-1, sizeof(List));
assert(G->adj != NULL);
G->cityNames = (char**)calloc(G->nodes_count-1, sizeof(char*));
assert(G->cityNames != NULL);
for (i = 0; i < G->nodes_count; i++) {
if (i != node_to_remove) {
G->adj[x] = checkListRemoval(tmp[i], node_to_remove);
G->cityNames[x] = old_matrix[i];
x++;
} else {
free(old_matrix[i]);
G->adj[i] = freeList(tmp[i]);
}
}
free(tmp);
free(old_matrix);
G->nodes_count -= 1;
}
}
void removeNodeByString(Graph G, char* name){
removeNodeByIndex(G, getCityIndexByName(G, name));
return;
}
List checkListRemoval(List L, int node_to_remove) {
if (L != NULL) {
L->next = checkListRemoval(L->next, node_to_remove);
if (L->target == node_to_remove) {
List tmp = L->next;
free(L);
return tmp;
} else if (L->target > node_to_remove) {
L->target -= 1;
}
}
return L;
}
List bfs(Graph G, int source, int target, weightSelector selector){
assert(G != NULL); // controllo che il grafo non sia nullo
assert(source < G->nodes_count || target < G->nodes_count); // controllo che i vertici inseriti appartengano al grafo
Queue Q = initQueue();
int* visit_path = (int*)calloc(G->nodes_count, sizeof(int));
assert(visit_path != NULL);
double* current_weight = (double*) calloc(G->nodes_count, sizeof(double));
assert (current_weight != NULL);
// calloc inizializza gli interi a zero, che nella enum corrisponde a WHITE
GraphColor* visited = (GraphColor*) calloc(G->nodes_count, sizeof(GraphColor));
assert(visited != NULL);
enqueue(Q, source);
visited[source] = BLACK;
// il nodo di partenza e' raggiungibile da se stesso con un percoso nullo
visit_path[source] = source;
current_weight[source] = 0;
int target_found = 0;
int v;
while(!isEmptyQueue(Q) && !target_found){
// non occorre controllare che la coda abbiamo terminato l'operazione correttamente
// dato che in questo punto del codice sicuramente non e' vuota;
dequeue(Q, &v);
for(List iter = G->adj[v]; iter != NULL; iter = iter->next){
if(visited[iter->target] == WHITE){
enqueue(Q, iter->target);
// segno di aver visitato il vertice in cui termina l'arco
visited[iter->target] = BLACK;
// segno che il vertice in questione e' raggiungibile con un arco partendo dal vertice v
visit_path[iter->target] = v;
// bcalcolo il peso del percorso
current_weight[iter->target] = current_weight[v] + iter->peso[selector];
if(iter->target == target){
target_found = 1;
break;
}
}
}
}
freeQueue(Q);
List path = NULL;
if(target_found != 0) {
// genera il percorso da source a target(se presente) e lo inserisce in una lista
path = generatePath(visit_path, current_weight, source, target, selector);
}
free(visited);
free(visit_path);
free(current_weight);
return path;
}
List dijkstra(Graph G, int source, int target, weightSelector selector){
assert(G != NULL); // controllo che il grafo non sia nullo
double* dist = (double*) calloc(G->nodes_count, sizeof(double));
assert(dist != NULL);
// calloc inizializza i vertici a 0 il che equivale al colore bianco
GraphColor* visited = (GraphColor*) calloc(G->nodes_count, sizeof(GraphColor));
assert(visited != NULL);
int* visit_path = (int*) calloc(G->nodes_count, sizeof(int));
assert(visit_path != NULL);
int targetFound = 0;
for(int i=0; i<G->nodes_count; i++){
dist[i] = (i == source)? 0.0 : INFINITY;
}
int currentVertex;
int initialized;
for( ; ; ){
currentVertex = -1;
initialized = 0;
//cerchiamo il vertcice non visitato con distanza minima
for(int i=0; i<G->nodes_count; i++){
if(visited[i] == WHITE){
if(initialized == 0){
currentVertex = i;
initialized = 1;
}else{
if (dist[i] < dist[currentVertex]){
currentVertex = i;
}
}
}
}
if(initialized == 0/*in pratica equivale a dire: fino a che vi sono nodi raggiungibili*/){
break;
}
// nel caso la distanza minima sia INFINITY non esistono piu' percorsi esplorabili partendo dal nodo source
if(dist[currentVertex] == INFINITY){
break;
}
visited[currentVertex] = BLACK;
//esploriamo gli adiacenti del vertice analizzato
for(List iter = G->adj[currentVertex]; iter != NULL; iter = iter->next){
if(visited[iter->target] == WHITE){
dist[iter->target] = dist[currentVertex] + iter->peso[selector];
visit_path[iter->target] = currentVertex;
if(iter->target == target){
// il vertice target e' raggiungibile (quello appena trovato potrebbe non essere lo shortest path!)
targetFound = 1;
}
}else{
// nel caso un vertice viene raggiunto da un percorso dal peso inferiore
double tmpDist = dist[currentVertex] + iter->peso[selector];
if(tmpDist < dist[iter->target]){
visit_path[iter->target] = currentVertex;
dist[iter->target] = tmpDist;
}
}
}
}
List path = NULL;
if(targetFound == 1){
path = generatePath(visit_path, dist, source, target, selector);
}
free(dist);
free(visited);
free(visit_path);
return path;
}
List generatePath(int* visit_info, double* weight_info, int source, int target, weightSelector selector){
if(source == target){
return initNodeList(source, weight_info[source]*(selector == PRICE), weight_info[source]*(selector == DISTANCE));
}else{
List path = generatePath(visit_info, weight_info, source, visit_info[target], selector);
path = appendNodeList(path, target, weight_info[source]*(selector == PRICE), weight_info[source]*(selector == DISTANCE));
return path;
}
}
int getCityIndexByName(Graph G, char* key){
assert(G != NULL);
assert(G->cityNames != NULL);
int index = -1;
int i;
for(i=0; i<G->nodes_count; i++){
if(!strcmp(G->cityNames[i], key)){
index = i;
break;
}
}
return index;
}
int getCityIndex(Graph G, char* message){
if(G == NULL){
printf("Grafo non inizializzto\n");
return -1;
}
if(G->nodes_count == 0){
printf("Grafo vuoto\n");
return -1;
}
int choice;
do{
printf("\nMete disponibili:\n");
for(int i=0; i<G->nodes_count; i++){
printf("Nome: %s, id: %d\n", G->cityNames[i], i);
}
printf("\nSeleziona %s:", message);
scanf("%d", &choice);
if(choice < 0 || choice >= G->nodes_count){
printf("Scelta non valida.\n");
}
}while(choice < 0 || choice >= G->nodes_count);
return choice;
}
Graph populateGraph(){
Graph g = NULL;
char** nomiCitta = (char**) calloc(20, sizeof(char*));
assert(nomiCitta != NULL);
for(int i=0; i<20; i++){
nomiCitta[i] = (char*) calloc(60, sizeof(char));
assert(nomiCitta[i] != NULL);
}
strcpy(nomiCitta[0], "Napoli");
strcpy(nomiCitta[1], "Roma");
strcpy(nomiCitta[2], "Milano");
strcpy(nomiCitta[3], "Torino");
strcpy(nomiCitta[4], "Salerno");
strcpy(nomiCitta[5], "Praga");
strcpy(nomiCitta[6], "Bari");
strcpy(nomiCitta[7], "Londra");
strcpy(nomiCitta[8], "Cagliari");
strcpy(nomiCitta[9], "Venezia");
strcpy(nomiCitta[10], "Genova");
strcpy(nomiCitta[11], "Firenze");
strcpy(nomiCitta[12], "Palermo");
strcpy(nomiCitta[13], "Catania");
strcpy(nomiCitta[14], "Parma");
strcpy(nomiCitta[15], "Verona");
strcpy(nomiCitta[16], "Bergamo");
strcpy(nomiCitta[17], "Bolzano");
strcpy(nomiCitta[18], "Perugia");
strcpy(nomiCitta[19], "Taranto");
g = initGraph(20,nomiCitta); //popolo grafo
addEdge(g, getCityIndexByName(g, "Napoli"), getCityIndexByName(g, "Milano"), 41.00, 657.00);
addEdge(g, getCityIndexByName(g, "Napoli"), getCityIndexByName(g, "Roma"), 37.00, 198.00);
addEdge(g, getCityIndexByName(g, "Roma"), getCityIndexByName(g, "Milano"), 84.00, 478.00);
addEdge(g, getCityIndexByName(g, "Milano"), getCityIndexByName(g, "Londra"), 300.50, 1195.1);
addEdge(g, getCityIndexByName(g, "Torino"), getCityIndexByName(g, "Salerno"), 112.80 ,930.60);
addEdge(g, getCityIndexByName(g, "Salerno"), getCityIndexByName(g, "Praga"), 123.80,1544.00);
addEdge(g, getCityIndexByName(g, "Praga"), getCityIndexByName(g, "Salerno"), 111.80,15544.0);
addEdge(g, getCityIndexByName(g, "Praga"), getCityIndexByName(g, "Torino"), 128.44, 752.00);
addEdge(g, getCityIndexByName(g, "Bari"), getCityIndexByName(g, "Venezia"), 30.00, 602.45);
addEdge(g, getCityIndexByName(g, "Londra"), getCityIndexByName(g, "Firenze"), 1542.31, 141.00);
addEdge(g, getCityIndexByName(g, "Cagliari"), getCityIndexByName(g, "Firenze"), 537.11, 183.00);
addEdge(g, getCityIndexByName(g, "Venezia"), getCityIndexByName(g, "Catania"), 74.00, 1294.30);
addEdge(g, getCityIndexByName(g, "Genova"), getCityIndexByName(g, "Perugia"), 74.47, 312.76);
addEdge(g, getCityIndexByName(g, "Firenze"), getCityIndexByName(g, "Bari"), 189.00, 547.00);
addEdge(g, getCityIndexByName(g, "Palermo"), getCityIndexByName(g, "Londra"), 72.00, 1779.42);
addEdge(g, getCityIndexByName(g, "Catania"), getCityIndexByName(g, "Venezia"), 1.00, 1294.30);
addEdge(g, getCityIndexByName(g, "Parma"), getCityIndexByName(g, "Verona"), 66.80, 144.16);
addEdge(g, getCityIndexByName(g, "Verona"), getCityIndexByName(g, "Praga"), 122.00, 813.28);
addEdge(g, getCityIndexByName(g, "Bergamo"), getCityIndexByName(g, "Palermo"), 81.00, 878.69);
addEdge(g, getCityIndexByName(g, "Bolzano"), getCityIndexByName(g, "Taranto"), 89.00, 820.96);
addEdge(g, getCityIndexByName(g, "Perugia"), getCityIndexByName(g, "Bolzano"), 110.56, 385.19);
addEdge(g, getCityIndexByName(g, "Taranto"), getCityIndexByName(g, "Catania"), 60.67, 479.69);
return g;
}
char* getCityName(char* message){
char buffer[BUFFER_SIZE];
char* new_string;
printf("insert the %s:", message);
scanf("%s", buffer);
new_string = (char*) calloc( strlen(buffer)+1, sizeof(char));
assert(new_string != NULL);
strcpy(new_string, buffer);
return new_string;
}
void PrintGraph(Graph G){
assert(G!=NULL);
for(int i=0; i<G->nodes_count; i++){
printf("[id:%d, city: %s] ", i, G->cityNames[i]);
for(List iter = G->adj[i];iter !=NULL;iter = iter->next){
printf("--> (id: %d, city: %s, costo:%3.2lf, distanza:%3.2lf)",iter->target, G->cityNames[iter->target], iter->peso[PRICE], iter->peso[DISTANCE]);
}
puts("");
}
return;
}
grafo.h
C:
#ifndef Graph_Graph_h
#define Graph_Graph_h
#include "List.h"
//struttura per il grafo
struct TGraph {
List *adj;
int nodes_count;
char** cityNames;
};
typedef struct TGraph* Graph;
// Dealloca l'intero grafo
void freeGraph(Graph G);
// Inizializza un nuovo grafo vuoto specificando in ingresso quanti nodi saranno nel grafo
Graph initGraph(int nodes_count, char** cityNames);
// Stampa il grafo
void PrintGraph(Graph G);
// Aggiunge un arco, specificando sorgente, target e peso
void addEdge(Graph G, int source, int target, double prezzo, double distanza);
// Rimuovi un arco specificando sorgente e target,restituisce la lista degli archi modifcata
List removeEdge(Graph G, int source, int target);
// Aggiungi un nodo
void addNode(Graph G, char* newCity);
// Rimuovi un nodo dal grafo, sistemando gli indici e riallocando la memoria
void removeNodeByIndex(Graph G, int node_to_remove);
//Rimuovo una cità
void removeNodeByString(Graph G, char* name);
List checkListRemoval(List L, int node_to_remove);
typedef enum{WHITE, GREY, BLACK} GraphColor;
// ricerca del percorso minimo dal vertice source a quello target
List bfs(Graph G, int source, int target, weightSelector selector);
// minimizza il percorso considerando il peso degli archi del grafo (funziona solo se tutti gli archi hanno peso positivo)
List dijkstra(Graph G, int source, int target, weightSelector selector);
// estrapola da visit_info il percorso da source a target
List generatePath(int* visit_info, double* weight_info, int source, int target, weightSelector selector);
// cerca il numero del vertice associato al nome di una particolare citta'
int getCityIndexByName(Graph G, char* key);
int getCityIndex(Graph G, char* message);
char* getCityName(char* message);
//funzione per popolare il grafo
Graph populateGraph(void);
#endif
main.c
C:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include <string.h>
#include <stdbool.h>
#include "Graph.h"
#include "List.h"
#include "Queue.h"
#include "Menu.h"
#include "ListPrenotazioni.h"
#include "ListUtente.h"
#define MAXDELETECITTA 7
#define BUFFER_SIZE 256
#define randomize srand(((unsigned int) time(NULL)))
#define random(x) rand()%x
int main(int argc, char** argv){
char city[10];
char cittaPartenza[10];
char cod_id[7];
int n=1,m=1;
char email[100];
char pwd[7];
ListPrenotazioni L = NULL;//per listPrenotazioni
ListUtente l = NULL;//per listUtente
randomize;
Graph g = populateGraph();
char mostPopularDestination = random(g->nodes_count);
char buffer_email[BUFFER_SIZE];
char buffer_password[BUFFER_SIZE];
// qui va inserita la DS per contenere gli utenti registrati, e la DS per contenere i voli prenotati da un utente
int loginChoice;
int adminChoice;
int userChoice;
int user1Choice;
int user2Choice;
bool continueLoop;
FILE *fp; /* dichiarazione puntatore al file "prova.txt"*/
struct prenotazione *lista=NULL;
fp = fopen("prova.txt","r");
if (fp == NULL) gestioneErrore();
lista = leggiFile(fp, lista);
fclose(fp);
do{
loginChoice = displayLoginMenu();
if(loginChoice == 0){ //azioni amministratore
continueLoop = true;
printf("Insert e-mail: ");
scanf("%s", buffer_email);
printf("Insert password (max 7 characters): ");
scanf("%s", buffer_password);
/*
Se l'admin non e' presente nella data structure degli admin --> continueLoop = false
In questo modo torna al menu di login e non vengono eseguite operazioni
*/
while(continueLoop){
adminChoice = displayAdminMenu();
switch (adminChoice){
case 0: // exit / logout
continueLoop = false;
break;
case 1: // stampa destinazioni
printf("\nThe destinations and the routes are as follows:\n");
PrintGraph(g);
break;
case 2: // inserisci destinazioni
addNode(g, getCityName("new destination"));
printf("\n~Operation successfully performed~\n");
break;
case 3: // cancella destinazioni
removeNodeByIndex(g, getCityIndex(g, "target city"));
printf("\n ~Operation successfully performed~ \n");
break;
default: /*Se l'utente sbaglia ad inserire il numero*/
printf("This button does not allow you to make choices! Try again!\n");
break;
}
}
}else if(loginChoice == 1){//azioni utenti
continueLoop = true;
while(continueLoop){
user1Choice = displayUserMenu1();
switch (user1Choice){
case 0: // exit / logout
continueLoop = false;
break;
case 1://effettuo iscrizione
for(int i=0; i<n; i++){
printf("\nInserti e-mail:\n");
scanf("%s",email);
printf("\nInsert password:\n");
scanf("%s",pwd);
l=insertTailUtente(l,email,pwd);
}
break;
case 2://effettuo accesso
printf("\nInsert e-mail:\n");
scanf("%s",email);
printf("\nInsert password:\n");
scanf("%s",pwd);
if(loginChoice == 1){//azioni utenti
continueLoop = true;
while (continueLoop){
userChoice = displayUserMenu();
switch (userChoice){
case 0:
continueLoop = false;
break;
case 1: // exit/logout
printListPrenotazione(lista);
break;
case 2: // effettua prenotazione
if(loginChoice == 1){//azioni utenti
continueLoop = true;
while (continueLoop){
user2Choice = displayUserMenu2();
switch (user2Choice){
case 0:
continueLoop = false;
break;
case 1://Prenotazione basata sulle rotte più economiche inserendo la città e la destinazione di partenza
//funzione per economiche
printf("Enter the number of reservations you wish to make\n");
scanf("%d",&m);
for (int i=0; i<m; i++){
printf("\nInsert citta:\n");
scanf("%s",city);
printf("\nInsert id:\n");
scanf("%s",cod_id);
L = insertTailPrenotazioni(L,city,cod_id);
}
break;
break;
case 2://Prenotazione basata sui percorsi più brevi inserendo la città di partenza e destinazione
//funzione per percorsi brevi
printf("Enter the number of reservations you wish to make\n");
scanf("%d",&m);
for (int i=0; i<m; i++){
printf("\nInsert citta:\n");
scanf("%s",city);
printf("\nInsert id:\n");
scanf("%s",cod_id);
L = insertTailPrenotazioni(L,city,cod_id);
}
break;
case 3://Prenotazione basata sulla destinazione più economica inserendo solo la città di partenza
//funzione per destinazione piu economica
printf("Enter the number of reservations you wish to make\n");
scanf("%d",&m);
for (int i=0; i<m; i++){
printf("\nInsert citta:\n");
scanf("%s",city);
printf("\nInsert id:\n");
scanf("%s",cod_id);
L = insertTailPrenotazioni(L,city,cod_id);
}
break;
case 4://Prenotazione basata sulla destinazione più popolare inserendo solo la città di partenza
printf("\nEnter city of start: ");
scanf("%s", cittaPartenza);
printf("\n The most popular destination is the following:\n");
mostPopularDestination = random(g->nodes_count);
char* cityName = g->cityNames[mostPopularDestination];
printf("id:%d city:%s\n",mostPopularDestination,cityName);
printf("Enter the number of reservations you wish to make\n");
scanf("%d",&m);
for (int i=0; i<m; i++){
printf("\nInsert citta:\n");
scanf("%s",city);
printf("\nInsert id:\n");
scanf("%s",cod_id);
L = insertTailPrenotazioni(L,city,cod_id);
}
break;
}
}
}
case 5: // vedi prenotazioni
printListPrenotazioni(L);
break;
default: /*Se l'utente sbaglia ad inserire il numero*/
printf("This button does not allow you to make choices! Try again!\n");
break;
}
}
}
}
}
}
else if(loginChoice == 2){
printf("Thank you goodbye!\n");
}else{
printf("This button does not allow you to make choices! Try again!\n");
}
}while(loginChoice != 2);
return 0;
}
Potete aiutarmi la funzioni di aggiungi nodo già c'è l'ho