Algorithmes en C

Cartoon -  
 Branham -
Salut,
j'aurais besoin d'aide pour ce projet.
Merci d'avance


SYNOPSIS graphes –dkpf [-o] [n] fichier
DESCRIPTION
Une des options au moins doit obligatoirement etre presente.Elles ne sont pas toutes mutuellement exclusives et certaines pourront etre demandées en meme temps.
Les graphes traités sont tous valués par des entiers,et peuvent contenir des aretes (i,i) ou i est un sommet.
Options

-o le resultat doit etre place dans un fichier de meme nom que le fichier d’entrée suffixe par .option
S’il y a plusieurs options,plusieurs fichiers devront etre crées.Ainsi la commende graphes –dp –o fic produira le fichier fic.d et fic.p
En cas d’absence de cette option les résultats seront affichés sur la sortie standart.

-d n plus courts chemins,ayant pour origine le sommet n.Si le graphe comporte des arcs de cout négatif on appliquera l’algo de Bellman-Ford.Si tous les arcs ont un cout positif,on appliquera l’algo de Dijkstra avec une file de priorité.

entrée fichier de type GRAPHE

sortie fichier de type LISTE contenant sur la i ème ligne la plus courte distance entre le sommet n et le sommet i suivie de la suite des sommets intermediaires sur le plus court chemin.S’il n’existe pas de plus court chemin entre n et i,la ligne sera vide.

exemple graphe oriente:
0->1 (poids 4),1->0(2),1->2(2),2->0(5),2->1(3)
graphe non oriente:
0--1(3),1--2(1),2--0(5)

-f plus courts chemins entre chaque couple de sommets,en appliquant l’algo de Warshall-Floyd.

entrée fichier de type GRAPHE

sortie fichier de type GRAPHE séparés par une ligne vide, le graphe des distances suivi du graphe des prédécesseurs sur un plus court chemin.

-p arbre recouvrant minimal par la méthode de Prim

entrée fichier de type GRAPHE

sortie fichier de type ARBRE

-k arbre recouvrant minimal par la méthode de Kruskal
Meme type de fichiers que pour l’option [-p]

FORMAT DES FICHIERS

Tous les entiers indiques sur une meme ligne sont separes par un unique caractère espace.Pas d’espace avant le premier ou après le dernier.
Toutes les lignes se terminent par \n

Les fichiers de format GRAPHE
Ces fichiers contiennent la description d’un graphe sous forme de matrice d’adjacence ou de listes d’adjacence.
première ligne : nombre de sommets

deuxième ligne : une lettre indiquant le type du graphe : o pour graphe orienté, n pour graphe non oriente

troisième ligne : une lettre indiquant le type de représentation du graphe, m pour matrice d’adjacence , l pour listes d’adjacence

lignes suivantes : les lignes de la matrice ou la suite des listes
Pour les graphes données en exemple
-Representation par matrice du graphe orienté
3
o
m
0 4 0
2 0 2
5 3 0

-representation par listes d’adjacence du graphe oriente
les arcs sont donnés sous forme de suites de 2 valeurs : cout sommet atteint
3
o
l
4 1
2 0 2 2
5 0 3 1


Cas d’un graphe non orienté
-Representation par matrice du graphe non orinente
On ne fournit que la matrice triangumaire supérieure
3
n
m
0 3 5
0 1
0

-Representation par listes d’ajacences du graphe non oriente :
un arc n’apparaît qu’une fois,associé à son extrémité de plus petit indice :
3
n
l
3 1 5 2
1 2

Remarques :
-si un sommet n’a pas d’arc sortant,la ligne correspondante dans les fichiers est réduite au caractère passage à la ligne.
-la plupart des algos fonctionnent le plus rapidement avec un type particulier de représentation en mémoire.A vous de convertir
A vous de convertir le sformats pour utiliser la representation en memoire la plus adaptée.

Les fichiers de format ARBRE

Première ligne : nombres d’arcs

Deuxieme ligne : poids de l’arbre

Lignes suivantes : sur chaque ligne ,un arc de l’arbre recouvrant (indique par un couple de sommets en ordre craoissant ),les differents couples etant tries dans l’ordre croissant.

Les fichiers de format LISTE

Sur chaque ligne,une liste de sommets

Pour tous les algos de distances ,lorsque la distance entre 2 sommets est infinie ,on affichera I
S’il existe un chemin non trivial(formé d’au moins un arc) d’un sommet à lui-meme ,le programme devra fournir la longueur du plus court ,et fournir la valeur 0 s’il n’y ap pas de chemin non trivial
En entrée ,l’absence d’arc est symbolisée par 0
Lorsqu’il y a plusieurs réponses possibles ,seule la plus petite dans l’ordre lexicographiqueest demandée.
Un graphe non oriente sera considere comme oriente dans les 2 sens.
Si le fichier en entrée est incorrect ,la sortie sera vide avec message d’erreur sur stderr.

4 réponses

Réponse 1 / 4
mamiemando Messages postés 33766 Date d'inscription   Statut Modérateur Dernière intervention   7 878
 
Une matrice se caractérise par les données qu'elle contient. Sauf qu'un tableau en C, on ne connait a priori pas sa taille sauf si on la passe en paramètre, donc il faut stocker le nombre de ligne et de colonne. Les cases de données seront allouées avec une fonction pour créer la matrice (l'équivalent du constructeur en C++), et détruite par une autre (par exemple dès que ut n'auras plus besoin de la matrice) (on parle en C++ de destructeur).

Ainsi, en C ça donne : 

#include <stdio.h>

struct matrix{
   unsigned int nb_rows;
   unsigned int nb_columns;
   double **data;
};

struct matrix new_matrix(unsigned int nrows,unsigned int ncolumns){
  unsigned int i;
  struct matrix m;
  m.nb_rows=nrows;
  m.nb_columns=ncolumns;
  m.data=(double **) malloc(sizeof(double *)*nrows);
  for(i=0;i<nrows;++i){
     m.data[i]=(double *) calloc(sizeof(double),ncolumns);
  }
  return m;
}

void del_matrix(struct matrix m){
  unsigned int i;
  for(i=0;i<m.nb_rows;++i){
     free(m.data[i]);
  }  
  free(m.data);
}

S'il y a des lignes que tu ne comprends pas n'hésite pas à demander.

Pour les listes c'est plus simple. On manipule des maillons qui stockent des données, et un maillon suivant (en supposant qu'ils stockent des doubles, mais ça peut être une adresse sur un type générique, ie un pointeur de type void *) : 

struct maillon{
  double data;
  struct maillon * next;
};

typedef maillon * list;



Bonne chance
1
Branham
 
super
0
Branham
 
!
0
Réponse 2 / 4
mamiemando Messages postés 33766 Date d'inscription   Statut Modérateur Dernière intervention   7 878
 
Oui alors l'idée c'est qu'on n'est pas là pour faire ton projet. Donc il faut cibler un peu le problème et nous dire sur quoi tu bloques, et là on se fera un plaisir de t'aider :-)
0
Réponse 3 / 4
Cartoon
 
Je sais bien mais est ce que tu pourrais m'indiquer,les champs que tu mettrais pour la sructure matrice et liste.
0
Réponse 4 / 4
LMD_MIAS Messages postés 46 Date d'inscription   Statut Membre Dernière intervention   5
 
bonsoir a tt j'arrive pas a programmer un graphe TAD
(" l'utilisateur doit entrez les ville et les distance+calcule largeur +pranfondeur +dijskraaaaaa")
tt ça en orienter objet
0
mamiemando Messages postés 33766 Date d'inscription   Statut Modérateur Dernière intervention   7 878
 
Merci d'ouvrir un nouveau sujet. Tu peux regarder du côté de la lib boost si tu es motivé.
https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/dijkstra_shortest_paths.html

La lib boost (plus précisemment la BGL) permet de construire facilement des graphes complètement génériques et ensuite d'appliquer des algorithmes de théorie des graphe dessus en particulier dijkstra. Par contre il faut être familier des template et la doc est parfois un peu légère. Pour l'installer sous debian : 
aptitude install libboost-dev libboost-doc

Bonne chance
0

Discussions similaires

algorithme résoudre ax²+bx+c=0
enimarix -
Utilisateur anonyme -

1 réponse
Écrivez un algorithme qui calcul l'équation du second degré à 2 inconnus
Cesar-boketa -
yg_be -

1 réponse
Bonsoir svp comment écrire un algorithme qui permet de cal
681453116 -
brucine -

1 réponse
Comment écrit-t-on un algorithme qui permet d'inverser une chaine de caractère
... -
jordane45 -

1 réponse
Algorithmes maximum et minimum
Dianakiss -
Chris 94 -

5 réponses