IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Génération aléatoire de graphes à degré contraint


Sujet :

Algorithmes et structures de données

  1. #1
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Juin 2017
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : Madagascar

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : Juin 2017
    Messages : 2
    Points : 2
    Points
    2
    Par défaut Génération aléatoire de graphes à degré contraint
    Comment peut-on générer uniformément un graphe aléatoire tel que les degrés sont dans un ensemble D inclus dans N, N ensemble des entiers naturels

  2. #2
    Rédacteur/Modérateur

    Avatar de yahiko
    Homme Profil pro
    Développeur
    Inscrit en
    Juillet 2013
    Messages
    1 423
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 1 423
    Points : 8 699
    Points
    8 699
    Billets dans le blog
    43
    Par défaut
    De façon naïve, je verrai le graphe comme une matrice carrée de dimension k, où k = le nombre de sommets.
    Pour chaque ligne, tu choisis un nombre aléatoire correspondant au degré du sommet associé à la ligne, et tu "coches" aléatoirement les cases de la ligne pour relier ce sommet à d'autres sommets.
    A noter qu'il te faut reporter par symétrie par rapport à la diagonale les cases cochées, car le graphe est non orienté, je présume. Et par conséquent, lors de l'étape précédente, il te faut tenir compte des cases déjà cochées sur la ligne.
    Et le tour et joué.
    Tutoriels et FAQ TypeScript

  3. #3
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 032
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 032
    Points : 9 331
    Points
    9 331
    Par défaut
    Il y a un risque avec la méthode proposée.
    Je traite le sommet 1, et je le lie avec différents sommets, aléatoirement.
    Idem le sommet 2, etc.

    Eventuellement, le sommet 1 aura été lié au sommet 100 ; idem, le sommet 2 aura été lié au sommet 100. etc etc.
    Et quand j'arrive au sommet 100, il est déjà lié à 30 ou 40 sommets, ou 99 sommets au pire, alors que le sommet 100 est sensé être lié à 20 sommets.

    Si effectivement la question initiale est celle-ci, alors on doit pouvoir trouver des solutions pour corriger cela. Mais il faudrait éclaircir la question.
    Graphe orienté ou non ?
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  4. #4
    Rédacteur/Modérateur

    Avatar de yahiko
    Homme Profil pro
    Développeur
    Inscrit en
    Juillet 2013
    Messages
    1 423
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : Juillet 2013
    Messages : 1 423
    Points : 8 699
    Points
    8 699
    Billets dans le blog
    43
    Par défaut
    Tout le problème d'une ébauche d'algo non testé.
    Oui, lorsqu'on coche, il faut vérifier le nombre de cases déjà cochées sur la colonne.

    En remarque, cette méthode naïve ne garantit pas la connexité du graphe ainsi généré. Si cette contrainte fait également partie de l'exercice, c'est autrement plus "touchy".
    Tutoriels et FAQ TypeScript

  5. #5
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    Août 2008
    Messages
    26 607
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2008
    Messages : 26 607
    Points : 188 574
    Points
    188 574
    Par défaut
    Pour ajouter un grain de théorie, le besoin ressemble à l'algorithme de génération de Watts et Strogatz (https://en.wikipedia.org/wiki/Watts_and_Strogatz_model). La différence est que ce dernier garantit un degré moyen. (Exemple d'implémentation : https://github.com/JuliaGraphs/Light...graphs.jl#L105.) Il y a peut-être moyen de jouer avec le paramètre de distribution et de retravailler légèrement les graphes pour atteindre la contrainte de degré ?
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  6. #6
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 329
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 329
    Points : 2 562
    Points
    2 562
    Billets dans le blog
    9
    Par défaut Génération aléatoire de graphes à degré contraint
    Bonjour,

    Pourquoi ne pas envisager un remplissage binaire et pseudo-aléatoire de la matrice d'adjacence ?
    Cela doit aller assez vite, puisque la matrice est symétrique (aij = aji) et ses termes diagonaux nuls (aii = 0) en l'absence de boucle.
    C'est pour l'essentiel ce que propose yahiko.

    Le codage des limitations imposée ne doit pas constituer d'obstacle insurmontable:
    # si l'on veut ne laisser subsister aucun sommet isolé, il suffit d'un remplissage préalable logeant au moins un point dans chaque ligne ou chaque colonne;
    # si l'on désire s'assurer du caractère hamiltonien du graphe, énoncer d'abord une permutation pseudo-aléatoire des (Ns) sommets qui définira le parcours exigé - c'est une version trop contraignante d'un graphe connexe;
    # le graphe deviendra cyclique dès que l'on joindra par une arête les points extrêmes de la chaîne précédente;
    # la simple connexité peut résulter de l'énumération d'une série de chaînes, avec critère d'arrêt approprié sur deux indices.

    Poursuivre ensuite l'ensemencement aléatoire de la matrice, en veillant à ce que le degré de tout sommet ne dépasse pas la limite convenue, et jusqu'à ce que le nombre total d'arêtes souhaité(Na) soit atteint.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  7. #7
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Juin 2017
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : Madagascar

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Enseignement

    Informations forums :
    Inscription : Juin 2017
    Messages : 2
    Points : 2
    Points
    2
    Par défaut
    Merci pour vos réponses. Je compte me servir de la liste d'adjacence pour résoudre le problème mais ca se complique. Si on limite les degrés à \Delta, je trouve la solution. Le problème est que D peut être du genre {3,5,8,..}. Prendre une séquence de degré et tester la faisabilité n'est pas une bonne si on essai avec. Je ne sais pas comment appliquer les modèles de Watts et... Pour un nombre de sommets fixé, il faut kn/2 arêtes, si kn est pair ca existe, sinon, si le nombre d'arêtes est supérieur ou inférieur, c'est impossible...

  8. #8
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 329
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 329
    Points : 2 562
    Points
    2 562
    Billets dans le blog
    9
    Par défaut Génération aléatoire de graphes à degré contraint
    Tu n'as rien dit de la taille de ton graphe: combien comporte-t-il de sommets ? Sa matrice d'adjacence peut-elle raisonnablement faire l'objet de manipulations telles que les échanges de valeurs entre ses éléments ?
    La somme des degrés est nécessairement paire, mais cette restriction n'est pas un obstacle, parce que les données de base du graphe sont les nombres (NS, NA) de sommets et d'arêtes.
    As-tu songé à travailler sur une liste des degrés toujours ordonnée, par exemple dans le sens croissant, et à envisager la création progressive de nouvelles arêtes ? Et par ailleurs la substitution d'une arête par une autre, avec (ou sans) sommet commun ?

    Tu pourrais ainsi te rapprocher progressivement de la liste des degrés imposée, en partant d'un graphe aléatoire connexe comportant le plus petit nombre d'arêtes (NA° = NS - 1), et le nombre imposé (N1) de sommets de degré (1).
    Une piste: on a pour tout graphe connexe acyclique: N1 = 2 + N3 + 2*N4 + 3*N5 + ... + (Dm - 1)*NDm
    et si sont présents (Nc) cycles: NA = NS - 1 + Nc

    On trouve des liens intéressants sur la construction des graphes aléatoires (parcours très rapide):
    Génération de graphes connexes aléatoires avec séquence de degrés donnée
    http://fabien.viger.free.fr/liafa/docs/report-liafa.pdf
    Graphes aléatoires
    http://perso.ens-lyon.fr/eric.thierr...ent-picard.pdf

    et aussi des algorithmes sur celui fournit par dourouc05 - là, cela n'a rien d'évident ...


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  9. #9
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 329
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 329
    Points : 2 562
    Points
    2 562
    Billets dans le blog
    9
    Par défaut Génération aléatoire de graphes à degré contraint
    La suppression d'un sommet de degré (2) suivie de la concaténation des fragments restants supprime une arête, mais conserve les degrés des autres sommets, d'où la possibilité de travailler sur un graphe réduit en procédant de la manière suivante:

    1°) Classer selon l'ordre croissant la liste des degrés des (NS) sommets initiaux; le nombre d'arêtes vérifie à ce stade:
    2*NA = N1 + 2*N2 + 3*N3 + ... + Dmax*NDmax .
    Le contenu de la liste correspondra à la somme des éléments des (NS) colonnes de la matrice d'adjacence, dans son état final.

    2°) Éliminer tous les sommets et chaînes de degré (2) en établissant un lien direct entre les centres subsistants, ce qui revient à supprimer provisoirement de la matrice les lignes et colonnes de rang (r) compris entre (N1 + 1) et (N1 + N2) - bornes incluses.
    Le nombre d'arêtes vérifie désormais: 2*N'A = N1 + 3*N3 + ... + Dmax*NDmax ,
    ce qui implique: NA - N'A = N2 en confirmation du constat initial, et N'S = NS - N2 pour le graphe réduit obtenu (G').

    3°) Passer au graphe complet correspondant (G") en reliant entre eux tous les sommets présents; la nouvelle liste des degrés associée à l'objet devient une séquence de (N'S) termes identiques, égaux à ((N'S - 1) puisque sont exclues les liaisons multiples.

    4°) Supprimer progressivement les arêtes:
    a) en commençant par les sommets de rang de plus élevé;
    b) en envisageant systématiquement les sommets associés de rang moindre, et d'une manière aléatoire;
    c) en veillant à ce que les nouvelles valeurs des degrés ne soient jamais inférieures à celle de la liste initiale, pour les deux rangs considérés;
    d) en poursuivant l'opération jusqu'à la disparition de tout écart entre les deux liste.
    Le nombre d'arêtes supprimées est N'S*(N'S - 1)/2 - N'A .

    5°) Insérer aléatoirement les (N2) sommets initialement exclus du réseau: les degrés des sommets actuellement présents demeurent inchangés.

    La connexité du graphe final n'est pas assurée. Un marquage approprié des arêtes (à l'aide de valeurs décimales(1)) pourrait remédier à cela.

    (1)) ... ou d'une paire d'indices, ou par bivaluation des arêtes créées)


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  10. #10
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 329
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 329
    Points : 2 562
    Points
    2 562
    Billets dans le blog
    9
    Par défaut Génération aléatoire de graphes à degré contraint
    Deux possibilités se présentent si l'on veut toujours parvenir à un graphe connexe, et qui partent de la liste des degrés ordonnée dans le sens croissant, et dépourvue de valeurs nulles du fait de l'exclusion des sommet isolés.
    Cette liste, de longueur (NS), commence donc par (N1) termes égaux à l'unité.

    1°) Réalisation d'un graphe connexe acyclique comportant (NA° = NS -1) arêtes et (N1) bouts de chaîne, par les étapes suivantes:
    a) tirage aléatoire des longueurs des (N1 - 1) sous-chaînes destinées à se raccorder par la suite, sous les conditions suivantes:
    # 3 <= L1 (la première présentant deux extrémités de degré égal à 1);
    # 1 <= Li pour tout indice du domaine [2 ; N1 - 1] (il n'y a plus qu'une extrémité de degré 1);
    # L1 + L2 + ... + LN1 - 1 = NS
    b) raccordement successif des tronçons en tout sommet du graphe courant, à l'exception des extrémités, ce qui conserve le nombre (N1) de sommets de degré (1); il faudra cependant vérifier qu'aucun terme de la liste croissante des degrés ne dépasse celui de même rang de la liste initiale.

    2°) À partir de ce graphe initial (G°), dont on est assuré qu'il est acyclique et connexe, et auquel il manque en principe (NA - NA°) arêtes, deux options sont envisageables:
    a) créer des liens supplémentaires (donc à chaque fois des cycles) selon une procédure apparentée à celle décrite au précédent message;
    b) passer au graphe complet, puis comme auparavant supprimer des liens - mais avec désormais l'obligation de préserver les arêtes du graphe connexe initial (G°); d'où l'attribution de 2 valeurs différentes aux éléments non-nuls de la matrice d'adjacence; par exemple:
    # aij = 7 pour les liens du graphe connexe, à préserver impérativement,
    # aij = 9 pour les autres, susceptibles de disparaître ensuite.
    Cette complication aura l'intérêt de permettre une meilleure représentation visuelle du graphe, en conservant des informations sur sa structure interne.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

Discussions similaires

  1. Réponses: 0
    Dernier message: 14/05/2016, 12h36
  2. Génération aléatoire de graphe
    Par ptit_fumiste dans le forum Langage
    Réponses: 4
    Dernier message: 29/12/2010, 00h51
  3. génération aléatoire
    Par acewb00 dans le forum MFC
    Réponses: 1
    Dernier message: 02/12/2005, 10h46
  4. Génération d'un graphe
    Par Tarrke dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 10/10/2005, 10h32
  5. génération aléatoire de couleur claire
    Par jiraiya dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 25/02/2004, 20h52

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo