Skip to content
Snippets Groups Projects
relations.c 12.63 KiB
// relations.c : definit le point d'entree pour l'application .
//
typedef int bool;
#define false 0
#define true -1

#include "stdlib.h"
#include "memory.h"
#include "stdio.h"
#include "string.h"

////////////////////////////////////////
// Exercice 1: Classement des Relations

typedef enum{
	FRERE = 2, COUSIN, PARENT, ONCLE, EPOUX, AMI, VIT, CONNAIT,
	CHEF, COLLEGUE, LOCATAIRE, TRAVAILLE, PROPRIETAIRE, SITUE, DECOUVERT
}rtype;

bool est_lien_parente(rtype id){
	return (id == FRERE || id == COUSIN || id == PARENT || id == ONCLE); 
}
bool est_lien_professionel(rtype id){
	return (id == CHEF || id == COLLEGUE); 
}
bool est_lien_connaissance(rtype id){
	return (id == EPOUX || id == AMI || id == CONNAIT || id == VIT);
}

static char* RelationsTable[] = {
	[2] = "frère ou soeur de", [3] = "cousin ou cousine de", [4] = "père ou mère",
	[5] = "oncle ou tante de", [6] = "époux ou épouse de", [7] = "ami de",
	[8] = "vit avec", [9] = "connait", [10] = "supérieur de",
	[11] = "collègue de", [12] = "locataire de", [13] = "travaille à",
	[14] = "propriétaire de", [15] = "situé à", [16] = "découvert à"
};

// PRE CONDITION: id > 1 
char* toStringRelation(rtype id){
	return RelationsTable[id];
}

////////////////////////////////////////
// Exercice 2: Liste de pointeurs

typedef struct s_node{
	void *val;  // pointeur vers objet quelconque
	struct s_node *suiv;
}*listeg;

listeg listegnouv(){
	return NULL;
}
listeg adjtete(listeg lst, void *x){
	listeg new = malloc(sizeof(struct s_node));
	if (new == NULL) {
        fprintf(stderr, " malloc == NULL fonction adjtete(lst,x) \n");
        exit(EXIT_FAILURE);
    }
	new->val = x;
	new->suiv = lst;
	return new;
}
listeg adjqueue(listeg lst, void *x){
	listeg new = malloc(sizeof(struct s_node));
	if (new == NULL) {
        fprintf(stderr, " malloc == NULL fonction adjqueue(lst,x) \n");
        exit(EXIT_FAILURE);
    }
	new->val = x;
	new->suiv = NULL;
	if( lst != NULL ){
		listeg copy = lst;
		while(copy->suiv != NULL){
			copy = copy->suiv; 
		}
		copy->suiv = new;
		return lst;
	}else
		return new;
}
listeg suptete(listeg lst){
	listeg deuxieme = lst->suiv;
	free(lst);
	return deuxieme;
}

void *tete(listeg lst){
	return lst->val;
}
int longueur(listeg lst){
	int res = 0;
	if( lst == NULL )
		return res;
	res++;
	listeg copy = lst;
	while(copy->suiv != NULL){
		copy = copy->suiv; 
		res++;
	}
	return res;
}
bool estvide(listeg lst){
	return lst == NULL;
}
void detruire(listeg lst){
	if( estvide(lst) )
		return;
	if(lst->suiv == NULL){
		free(lst);
		return;
	}
	listeg copy = lst;
	while(copy != NULL){
		copy = copy->suiv;
		free(lst);
		lst = copy;
	}
}
listeg rech(listeg lst, void *x, int(*comp)(void *, void *)){
	listeg copy = lst;
	while(copy != NULL){
		if( comp(x, copy->val) ){
			return lst;
		}else{
			copy = copy->suiv;
		}
	}
	return NULL;
}

////////////////////////////////////////
// Exercice 3: Construction du graphe

#define LONG_NOM_MAX 64
typedef enum{
	PERSONNE=1, OBJET, ADRESSE, VILLE
}etype;
typedef struct s_entite{
	char nom[LONG_NOM_MAX]; // le nom de l entite p.ex " Peugeot 106 "
	etype ident; // l identifiant associe, p.ex OBJET
}*Entite;
//3.1 les structures de donnees
typedef struct s_sommet{
	struct s_node* larcs;
	Entite x;
}*Sommet;

typedef struct s_arc{
	rtype t; 
	struct s_entite* x;
}*Arc;

typedef struct s_relations{
	listeg listDeRelations;
}*Relations;

//3.2 les constructeurs
Entite creerEntite(char *s, etype e){
	Entite newEntity = malloc(sizeof(struct s_entite));
	if (newEntity == NULL) {
        fprintf(stderr, " malloc == NULL fonction creerEntite(s,e) \n");
        exit(EXIT_FAILURE);
    }
	strcpy(newEntity->nom, s);
	newEntity->ident = e;
	return newEntity;
}
Sommet nouvSommet(Entite e){
	if(e == NULL){
		fprintf(stderr, " nouvSommet(e) erreur e == NULL ici fonction nouvSommet(e) \n");
    	exit(EXIT_FAILURE);
	}
	Sommet s = malloc(sizeof(struct s_sommet));
	if (s == NULL) {
        fprintf(stderr, " malloc == NULL fonction nouvSommet(e) \n");
        exit(EXIT_FAILURE);
    }
	s->x = e;
	s->larcs = listegnouv();
	return s;
}
Arc nouvArc(Entite e, rtype type){
	if(e == NULL){
		fprintf(stderr, " nouvSommet(e) erreur e == NULL ici fonction nouvArc(e,type) \n");
    	exit(EXIT_FAILURE);
	}
	Arc bow = malloc(sizeof(struct s_arc));
	if (bow == NULL) {
        fprintf(stderr, " malloc == NULL fonction nouvArc(e,type) \n");
        exit(EXIT_FAILURE);
    }
	bow->t = type;
	bow->x = e;
	return bow;
}
void relationInit(Relations *g){
	*g = malloc(sizeof(struct s_relations));
	if(*g == NULL){
		fprintf(stderr, " malloc == NULL function relationInit(*g) \n");
    	exit(EXIT_FAILURE);
	}
	(*g)->listDeRelations = listegnouv();
}
void relationFree(Relations *g){
	// il faut free g, il faut aussi free g->listeDeRelations (qui est un listeg), 
	// 999 et il faut free g->listeDeRelations->val (qui est un sommet),
	// 999 et il faut free g->listeDeRelations->val->x (qui est une entite),
	// 999 et il faut free g->listeDeRelations->val->larcs (qui est un listeg),
	// 999 et il faut free tous les g->listeDeRelations->val->larcs->val (qui sont des arcs),
	// 999 et il faut free tous les g->listeDeRelations->val->larcs->val->x (qui sont des entites)
	
	// commençont par tous les g->listeDeRelations->val->larcs->val->x et du val qui va avec
	free( ((Sommet)((*g)->listDeRelations->val))->x );
	listeg tete = (*g)->listDeRelations;
	printf("check 0 \n");
	while( tete != NULL ){
		listeg LarcsDuSommet = ((Sommet)(tete->val))->larcs;
		listeg LarcTete = LarcsDuSommet;
		while( LarcsDuSommet != NULL ){
			printf("check 1 \n");
			free(  ((Arc)( LarcsDuSommet->val ))->x  );
			printf("check 2 \n");
			free(  ((Arc)( LarcsDuSommet->val ))  );
			LarcsDuSommet = LarcsDuSommet->suiv;
		}
		printf("check 3 \n");
		detruire(LarcTete);
		printf("check 4 \n");
		free( ((Sommet)(tete->val)) );
		printf("check 5 \n");
		tete = tete->suiv;
	}
	detruire( (*g)->listDeRelations );
	free(*g);
}

//3.3 les comparaisons
int compEntite(void *e, void *string){
	if (e == NULL || string == NULL) {
        return 0;
    }
	if( strcmp( ((Entite)e)->nom, string ) == 0 ){
		return 1;
	}
	return 0;
}
int compSommet(void *s, void *string){
	if (s == NULL || string == NULL) {
        return 0;
    }
	if( strcmp( ((Sommet)s)->x->nom, string ) == 0 ){
		return 1;
	}
	return 0;
}
int compArc(void *a, void *string){
	if (a == NULL || string == NULL) {
        return 0;
    }
	if( strcmp( ((Arc)a)->x->nom, string ) == 0 ){
		return 1;
	}
	return 0;
}

//3.4 ajout d'entites et de relations
void adjEntite(Relations g, char *nom, etype t){
	g->listDeRelations = adjqueue(g->listDeRelations, nouvSommet(creerEntite(nom, t)));
}
// PRE CONDITION: id doit etre coherent avec les types des sommets correspondants a x et y
//                p.ex si x est de type OBJET, id ne peut pas etre une relation de parente
// PRE CONDITION: strcmp(nom1,nom2)!=0
void adjRelation(Relations g, char *nom1, char *nom2, rtype id){
	Sommet sommet1 = NULL;
	Sommet sommet2 = NULL;
	Entite deuxiemeEntite = NULL;
	listeg copy = g->listDeRelations;
	while( copy != NULL ){
		if( strcmp(((Sommet)(copy->val))->x->nom, nom1)==0 ){
			sommet1 = (Sommet)(copy->val);
		}
		if( strcmp(((Sommet)(copy->val))->x->nom, nom2)==0 ){
			sommet2 = (Sommet)(copy->val);
		}
		copy = copy->suiv;
	}
	sommet1->larcs = adjqueue(sommet1->larcs, (Arc)nouvArc(sommet2->x, id));
}

////////////////////////////////////////
// Exercice 4: Explorer les relations entre personnes

// 4.1 listes de relations
listeg en_relation(Relations g, char *x){
	return NULL;
}
listeg chemin2(Relations g, char *x, char *y){
	return NULL;
}
// 4.2 verifier un lien de parente
// PRE CONDITION: strcmp(x,y)!=0
bool ont_lien_parente(Relations g, char *x, char *y){
	return false;
}

// 4.3 tester connaissances
// PRE CONDITION: les sommets correspondants � x et y sont de type PERSONNE
// PRE CONDITION: strcmp(x,y)!=0
bool se_connaissent(Relations g, char *x, char *y){
	return false;
}
// PRE CONDITION: les sommets correspondants � x et y sont de type PERSONNE
// PRE CONDITION: strcmp(x,y)!=0
bool se_connaissent_proba(Relations g, char *x, char *y){
	return false;
}
// PRE CONDITION: les sommets correspondants � x et y sont de type PERSONNE
// PRE CONDITION: strcmp(x,y)!=0
bool se_connaissent_peutetre(Relations g, char *x, char *y){
	return false;
}

////////////////////////////////////////
// Exercice 5: Affichages
static char* etype_string[] = { [PERSONNE] = "personne", [OBJET] = "objet", [ADRESSE] = "adresse",
[VILLE] = "ville"};

void affichelg(listeg l, void(*aff)(void *)){
	while( l != NULL ){
		aff(l->val);
		l = l->suiv;
	}
}	

void afficheEntite(void *x){
	printf("%s :%s\n", ((Entite)x)->nom, etype_string[ ((Entite)x)->ident] );
}
void afficheArc(void *x){
	printf(" --%s-->", toStringRelation(((Arc)x)->t));
	afficheEntite( ((Arc)(x))->x );
}

////////////////////////////////////////
// Exercice 6: Parcours
void affiche_degre_relations(Relations r, char *x){
	
}

int main(){
	int i,j;
	
	printf("test toStringRelation(16) == %s \n", toStringRelation(16));
	printf("test est_lien_parente : %d   %d   %d \n",est_lien_parente(COUSIN),est_lien_parente(LOCATAIRE),
	est_lien_parente(EPOUX));
	printf("test est_lien_professionel : %d   %d   %d \n", est_lien_professionel(LOCATAIRE),
	est_lien_professionel(CHEF), est_lien_professionel(COLLEGUE));
	printf("test est_lien_connaissance : %d   %d   %d \n", est_lien_connaissance(AMI),
	est_lien_connaissance(CONNAIT), est_lien_connaissance(COLLEGUE));
	
	listeg liste = listegnouv();
	int x5 = 5, x4 = 4, x19 = 19, x3 = 3, x33 = 33;
	int *px5, *px4, *px19, *px3, *px33;
	px5 = &x5;   px4 = &x4;   px19 = &x19;   px3 = &x3;   px33 = &x33;
	int x0 = 0; int* px0 = &x0;
	liste = adjqueue(liste, &px5);
	liste = adjtete(liste, &px4);
	liste = adjqueue(liste, &px19);
	liste = adjtete(liste, &px3);
	liste = adjqueue(liste, &px33);
	liste = adjtete(liste, &px0);
	liste = suptete(liste);
	listeg copy = liste;
	for(int i=0; i<4; i++){
		printf("liste->val == %d \n", **(int**)copy->val);
		copy = copy->suiv;
	}
	printf("tete(liste) == %d \n", **(int**)tete(liste));
	
	detruire(liste);
	
	Relations r; relationInit(&r);
	// ajouter les entites de l'exemple
	char *tabe[] ={"KARL","LUDOVIC","CELINE","CHLOE","GILDAS","CEDRIC","SEVERINE",
		"PEUGEOT 106" ,"1, RUE DE LA RUE","STRASBOURG" };
	for (i = 0; i < 7; i++) 
		adjEntite(r, tabe[i], PERSONNE);
	adjEntite(r, tabe[7], OBJET);
	adjEntite(r, tabe[8], ADRESSE);
	adjEntite(r, tabe[9], VILLE);
	// ajouter les relations de l'exemple
	adjRelation(r, tabe[0], tabe[1], FRERE);
	adjRelation(r, tabe[0], tabe[2], AMI);
	adjRelation(r, tabe[0], tabe[3], CONNAIT);
	adjRelation(r, tabe[0], tabe[5], COUSIN);
	adjRelation(r, tabe[0], tabe[7], PROPRIETAIRE);
	adjRelation(r, tabe[0], tabe[8], PROPRIETAIRE);
	adjRelation(r, tabe[3], tabe[4], VIT);
	adjRelation(r, tabe[5], tabe[6], EPOUX);
	adjRelation(r, tabe[5], tabe[8], LOCATAIRE);
	adjRelation(r, tabe[7], tabe[8], DECOUVERT);
	adjRelation(r, tabe[8], tabe[9], SITUE);
	
	affichelg( ((Sommet)(r->listDeRelations->val))->larcs, afficheArc );
	printf("\n %s \n", ((Arc)(((Sommet)(r->listDeRelations->val))->larcs->val))->x->nom  );
	//relationFree(&r);
	return 0;
	
	// explorer les relations
	printf("%s est en relation avec:\n", tabe[0]);
	affichelg(en_relation(r, tabe[0]),afficheArc);
	printf("\n");

	for (i = 0; i < 7; i++) for (j = i + 1; j < 10; j++)
	{
		printf("<%s> et <%s> ont les relations communes:\n", tabe[i], tabe[j]);
		listeg ch = chemin2(r, tabe[i], tabe[j]);
		affichelg(ch, afficheEntite);
		printf("\n");
		detruire(ch);
	}
	printf("\n\n");

	for (i = 0; i < 10; i++) for (j = i + 1; j < 10; j++)
	{
		printf("<%s> et <%s> ont lien de parente: %s\n",
			tabe[i], tabe[j], ont_lien_parente(r, tabe[i], tabe[j]) ? "vrai" : "faux");
	}
	printf("\n");
	for (i = 0; i < 7; i++)
	{
		for (j = i + 1; j < 7; j++)
		{
			printf("<%s> et <%s> se connaissent: %s\n",
				tabe[i], tabe[j], se_connaissent(r, tabe[i], tabe[j]) ? "vrai" : "faux");
			printf("<%s> et <%s> se connaissent tres probablement: %s\n",
				tabe[i], tabe[j], se_connaissent_proba(r, tabe[i], tabe[j]) ? "vrai" : "faux");
			printf("<%s> et <%s> se connaissent peut etre: %s\n",
				tabe[i], tabe[j], se_connaissent_peutetre(r, tabe[i], tabe[j]) ? "vrai" : "faux");
		}
		printf("\n");
	}

	affiche_degre_relations(r, tabe[3]);

	relationFree(&r);

	printf("\nPRESS RETURN\n");
	char buff[64]; fscanf(stdin, "%s", buff);
    return 0;
}