Bonjour, quelqu'un saurait faire une fonction qui lit une liste de listes d'adjacences à partir d'un fichier CSV.  Attention: si le graphe est non-dirigé la fonction doit s'assurer que les adjacences sont bien mentionnées 2 fois.

je ne comprends vraiment pas comment faire.

Je sais lire le fichier csv, et créer ma liste mais je n'arrive pas à mettre les adjacences...

Il y a plein de façons pour représenter ça et ça dépend du python que vous connaissez (ou que   vous avez appris). Sans montrer du code, difficile d'avoir une idée de votre niveau et imaginer quoi essayer d'expliquer...

Nous sommes débutants. 
j'avais fait ça :

def lire_liste_adjacences(nom_fichier):
    liste_adjacences = {}
    with open(nom_fichier, 'r', newline='') as fichier_csv:
        lecteur_csv = csv.reader(fichier_csv)
        for ligne in lecteur_csv:
            sommet_a, *adjacents = ligne
            
            if sommet_a not in liste_adjacences:
                liste_adjacences[sommet_a] = []
                
            for sommet_b in adjacents:
                if sommet_b not in liste_adjacences:
                    liste_adjacences[sommet_b] = []
                
                liste_adjacences[sommet_a].append(sommet_b)
                liste_adjacences[sommet_b].append(sommet_a)  
    
    return [adjacences for sommet, adjacences in sorted(liste_adjacences.items())]

pour un fichier csv contenant :

b,a
c,b
d,a,c
e,d
f,e
g,a,f

elle me renvoie :

[['b', 'd', 'g'],
 ['a', 'c'],
 ['b', 'd'],
 ['a', 'c', 'e'],
 ['d', 'f'],
 ['e', 'g'],
 ['a', 'f']]

mais pour un fichier csv contenant :

1,2,3,4,5,6,7
2,1
3,1
4,1
5,1
6,1
7,1

elle me renvoie :

[['2', '3', '4', '5', '6', '7', '2', '3', '4', '5', '6', '7'],
 ['1', '1'],
 ['1', '1'],
 ['1', '1'],
 ['1', '1'],
 ['1', '1'],
 ['1', '1']]

Ce n'est pas bon mais je n'arrive pas à changer pour que ça convienne pour différents types d'éléments des listes 

MarieLilou a écrit:

Ce n'est pas bon mais je n'arrive pas à changer pour que ça convienne pour différents types d'éléments des listes 

Si ça sort [1, 1] pour le sommet N, çà veut dire qu'il y a plusieurs fois le même sommet dans la liste des nœuds adjacents à N. Ce qui arrive lorsqu'on oublie de tester si un sommet n'est pas déjà dans la liste d'adjacence de N avant de l'y insérer... (ou d'utiliser des set à la place de listes).

Je ne vois pas comment est réalisée la condition: "la fonction doit s'assurer que les adjacences sont bien mentionnées 2 fois". Le code force la chose mais ne vérifie pas grand chose.

note: le premier fichier contient b, a mais pas de a, b...

Pour le reste, qu'ils se nomment avec lettres a, b, c, .... ou chiffres 1, 2, 3,... pour python ça reste des chaines de caractères de longueur 1.

-
Edité par mps 16 février 2024 à 18:53:37

Je ne sais pas si tu connais les dictionnaires. C'est ce que j'aurais utilisé.

Pour chaque sommet, je crée une entrée avec le sommet comme clé et une liste ou un set pour valeur.

Pour un graphe non orienté, avec les sommets a et b, j'ajouterais a dans la liste de b, et b dans la liste de a

Après, on peut construire une matrice NxN en connaissant le nombre de clés dans ce dictionnaire.

MarieLilou a écrit:

Nous sommes débutants.

Ça explique qu'on vous donne des exercices à faire, pour apprendre !

Faut s'y faire, en programmation, on vous donne à faire des trucs que vous n'avez pas déjà fait, et vous devez trouver.

MarieLilou a écrit:

pour un fichier csv contenant :

b,a
c,b
d,a,c
e,d
f,e
g,a,f

elle me renvoie :

[['b', 'd', 'g'],
 ['a', 'c'],
 ['b', 'd'],
 ['a', 'c', 'e'],
 ['d', 'f'],
 ['e', 'g'],
 ['a', 'f']]

Il faudrait que vous vous donniez la peine d'expliquer

• comment sont codées les données en entrée.  Est ce que la ligne d,a,c signifie que les voisins de d sont  a et c ?
• ce que signifie la structure de données en sortie.

Parce que bon, je  ne comprends pas le rapport entre les deux.

---

Si il s'agit de lire des listes, à raison d'une par ligne, dans un fichier csv, c'est pas compliqué

import csv

def lire_listes_adjacence(nom_fichier):
    liste = []
    with open(nom_fichier, 'r', newline='') as fichier_csv:
        lecteur_csv = csv.reader(fichier_csv)
        for ligne in lecteur_csv:
            liste.append(ligne)
    return liste

lire_listes_adjacence("g1.csv")

avec le fichier ci-dessus, ça donne

[['b', 'a'], ['c', 'b'], ['d', 'a', 'c'], ['e', 'd'], ['f', 'e'], ['g', 'a', 'f']]

Ca lit un fichier de listes d'adjacence, et ça retourne une liste de listes. C'est ce qui est spécifié dans le premier message.  Si il faut faire autre chose, il faut dire quoi.

Maintenant, si on veut un dictionnaire qui faire correspondre à chaque (nom de) sommet, la liste de ses voisins, c'est possible aussi, et c'est pas très différent

def lire_graphe(nom_fichier):
    dict = {}
    with open(nom_fichier, 'r', newline='') as fichier_csv:
        lecteur_csv = csv.reader(fichier_csv)
        for sommet,*liste_voisins  in lecteur_csv:
            dict[sommet] = liste_voisins
    return dict

lire_graphe("g1.csv")

sur le même fichier, ça donne (en le présentant proprement)

{
 'b': ['a'], 
 'c': ['b'], 
 'd': ['a', 'c'], 
 'e': ['d'], 
 'f': ['e'], 
 'g': ['a', 'f']
}

On peut ensuite "symétriser" si on veut en tirer un graphe non orienté. Exercice.  Indication : ça se fait après avoir lu, pas pendant.

PS: comme il s'agit de graphes, et non de cartes https://fr.wikipedia.org/wiki/Carte_combinatoire  l'ordre des voisins d'un sommet n'est pas défini, et on devrait donc en faire un ensemble plutôt qu'une liste.

-
Edité par michelbillaud 4 mars 2024 à 20:40:15