[Résolu] Génération d'un graphe respectant un visuel

[Sephi-Chan]

Bonsoir,

J'essaye de mettre au point un algorithme qui me permettrait de modéliser (sous forme de matrice, donc) le graphe qui suit. La fonction prendrait comme argument une profondeur (ici 4 niveaux de profondeur) et un coefficient C (le niveau de profondeur N possède N*C sphères).

J'ai représenté quelqes arrêtes pour certains noeuds pour que vous cerniez ce que je cherche. Notez que les cercles concentriques sont purement cosmétiques (ce seront en fait des arrêtes spéciales).



Par exemple, la sphère 2.0 a pour voisins les sphères 3.0, 3.1, 2.1, 1.0, 2.7 et 3.11.

J'espère que vous pourrez m'aider à mettre au point cet algorithme.


Sephi-Chan

[Argorate]

Salut,
La théorie des graphes est plutot complexe dans son enssemble, mais si y a bien une chose qu'on sait bien faire (merci Dijkstra) c'est trouver une liste de successeurs dans un graphe et quelque soit le graphe.

Il te suffit d'appliquer une decente en largeur en te contentant de t'arreter a la couche 1 (puisque tu ne veux que les successeurs direct => "voisin").

L'algorithme d'une descente est pas très difficile. (jai programmer en php la descente en profondeur cet année, ça prend 30 lignes environ et il n'y a pas grande différence avec celle en largeur)

Si tu as besoin d'aide n'hésite pas, mais pour l'instant je te laisse avec l'algo de wiki:
http://fr.wikipedia.org/wiki/Algorithme_...en_largeur

Bon courage

[Sephi-Chan]

En fait, mon problème n'est pas défini pour y appliquer la théorie des graphes. En effet, je n'ai défini aucun lien entre les noeuds, ça n'est que du visuel. Le terme de graphe utilisé dans le titre est mal choisi.

Pour avoir fait un peu de théorie des graphes l'an dernier (on a bouffé des algorithmes de plus court chemin, de plus large couverture, etc.), le problème serait plus simple si j'avais un graphe correctement défini (et qui colle à la représentation graphique que je présente).

La question devient alors : Quel algorithme permettrait la génération d'un tel graphe (pas visuellement, donc, mais en terme de structure de données) ?
On donnerait à cet algorithme un niveau de profondeur : 0 pour une seule sphère, 1 pour 4 sphères, puis n pour n*4 sphères.

Je modifie le sujet initial en conséquences.


Sephi-Chan

[Freygolow]

Les voisins de X.Y quand (X%Y = 0) sont:
- X+1.Y et X-1.Y (exception pour min(X) et max(X))
- X.(Y+1)%NBY et X.(Y-1+NBY)%NBY
- X+1.Y+1
- X+1.(Y-1+NBY+4)%(NBY+4) <== Faux

NBY étant le nombre de noeuds formant un cercle. A priori, quand tu rajoutes un "grand" cercle, tu y rajoutes 4 noeuds supplémentaires (Un de plus pour chaque quart).

Donc pour X%Y != 0
dans le premier quart le voisin de 2.1 est 3.1+1
dans le deuxieme quart le voisin de 2.3 est 3.3+2
dans le troisieme quart le voisin de 2.5 est 3.5+3
dans le quatrieme quart le voisin de 2.7 est 3.7+4
Et inversement
dans le premier quart le voisin de 2.1 est 3.1+1-1
dans le deuxieme quart le voisin de 2.3 est 3.3+2-1
dans le troisieme quart le voisin de 2.5 est 3.5+3-1
dans le quatrieme quart le voisin de 2.7 est 3.7+4-1

Voici un début de raisonnement si ça peu faire avancer les choses. C'est vrai que le problème n'est pas simple.

[Sephi-Chan]

Les voisins de X.Y quand (X%Y = 0) sont:
- X+1.Y et X-1.Y (exception pour min(X) et max(X))
- X.(Y+1)%NBY et X.(Y-1+NBY)%NBY
- X+1.Y+1
- X+1.(Y-1+NBY+4)%(NBY+4) <== Faux

NBY étant le nombre de noeuds formant un cercle. A priori, quand tu rajoutes un "grand" cercle, tu y rajoutes 4 noeuds supplémentaires (Un de plus pour chaque quart).

Donc pour X%Y != 0
dans le premier quart le voisin de 2.1 est 3.1+1
dans le deuxieme quart le voisin de 2.3 est 3.3+2
dans le troisieme quart le voisin de 2.5 est 3.5+3
dans le quatrieme quart le voisin de 2.7 est 3.7+4
Et inversement
dans le premier quart le voisin de 2.1 est 3.1+1-1
dans le deuxieme quart le voisin de 2.3 est 3.3+2-1
dans le troisieme quart le voisin de 2.5 est 3.5+3-1
dans le quatrieme quart le voisin de 2.7 est 3.7+4-1

Voici un début de raisonnement si ça peu faire avancer les choses. C'est vrai que le problème n'est pas simple.

J'étais également parti sur ce genre de raisonnement mais je pense me tourner vers la théorie des graphes, ça me permettra de me reposer sur des théorèmes existants et fiables, car je ne suis pas quelqu'un de très bon en logique/maths.


Sephi-Chan

[jo_link_noir]

En séparant les cercle en 4 avec un trait sur l'axe x et y. On peut retrouver les coordonnée des nœuds de cette manière

• partie droite-haut :
  • +1x ; +1y
    
  • -1x ; -1y
    
  • +1x
    
  • -1x
    
  
  
• partie droite-bas :
  • +1x ; +1y
    
  • -1x ; -1y
    
  • +1x ; +2y
    
  • -1x ; -2y
    
  
  
• partie gauche-bas :
  • +1x ; +3y
    
  • -1x ; -3y
    
  • +1x ; +2y
    
  • -1x ; -2y
    
  
  
• partie gauche-haut :
  • +1x ; +3y
    
  • -1x ; -3y
    
  • +1x ; +4y
    
  • -1x ; -4y
    

Attention pour le dernier, on peut "dépasser" la valeur (N*C). par exemple 1.4 n'existe pas, il devient 1.0.


Exception également sur les nœuds positionner sur l' axe x ou y.

• axe x haut :
  • +1x
    
  • -1x
    
  • +1x ; +1y
    
  • +1x ; +NCy
    
  
  
• axe y droit :
  • +1x
    
  • -1x ; -1y
    
  • +1x ; +2y
    
  • +1x ; +1y
    
  
  
• axe x bas :
  • +1x ; +2y
    
  • -1x ; -2y
    
  • +1x ; +4y
    
  • -1x ; +2y
    
  
  
• axe y gauche :
  • +1x ; +4y
    
  • +1x ; +2y
    
  • +1x ; +3y
    
  • -1x ; +-3y
    

Les 2 nœuds restants sont sur le même cercle donc +1y et -1y.


Manque plus qu'à trouvé la position du nœud :

Code :

si x = 0 et y = 0
...
sinon si x = y
    axe x droit
sinon si y = 0
    axe y haut
sinon si 2x = y
    axe y bas
sinon si 3x = y
    axe x gauche
sinon si y < x
    coté haut-droit
sinon si y < 2N
    coté bas-droit
sinon si y < 3N
    coté bas-gauche
sinon
    coté haut-droit

Un truc comme ça .

[Roworll]

Mis à part pour le centre, ça ressemble assez à une structure hexagonale.
Chaque cercle dans le graphe semble avoir 6 voisins.
Il n'y aurait pas une solution à fouiller de ce coté ?

[NicoMSEvent]

Bien vu Roworll...

pour trouver les voisins, si tes coordonnées sont (x,y)

il y a un voisin vers le centre, deux voisins sur la même "boucle" de la spirale, et trois voisins vers l'extérieur.

donc
(x-1,y-1), (x-1,y), (x+1,y), (x-1,y+1), (x,y+1), (x-1,y+1)

les exceptions sont : la boule du centre(cas tout a fait spécial), et les boules en début et fin de boucle (x -> modulo du nombre de boule sur ta boucle?)

[Sephi-Chan]

Mais pour générer un graphe de cette forme, je ne vois pas comment faire.

A partir du nombre d'anneaux de la structures, je suis capable de dire combien il y aura de sphères (ici, 1*4 + 2*4 + 3*4 + 1 = 25) dans la structures.

A partir de là, je peux générer une matrice de 25*25 éléments. Mais ensuite, pour "remplir" les bonnes cases (mettre des 0 quand il n'y a pas de relations, des 1 quand il y a une)... Je bloque.


Sephi-Chan

[NicoMSEvent]

crée une chaine linéaire, et chaque élément contient un couple de valeur (x,y), d'une telle manière que tu puisse faire une recherche rapide sur x et y. Ensuite, crée les liens (donc ton graphe) sur base des voisins

il y a un voisin vers le centre, deux voisins sur la même "boucle" de la spirale, et trois voisins vers l'extérieur.

donc
(x-1,y-1), (x-1,y), (x+1,y), (x-1,y+1), (x,y+1), (x-1,y+1)

fais gaffe aux "exceptions" (début et fin de chaque anneau)

je ne crois pas que ça soit spécialement difficile, juste un peu dur a appréhender si tu n'as une bonne vision en 2D du problème (transformation d'une chaine en graphe)

Edit : j'ai p-e mal compris ton besoin... je pense que tu cherches a mettre ce graphe en mémoire, et avoir accès facilement d'un noeud a un autre (ou déterminer facilement les voisins). Mais p-e qu'il suffit juste d'un petit morceau d'algorithme, et pas d'un graphe complet )
par exemple, juste sur base de l'algo pour un schéma ou tu passerait en paramètre (3,4), comme pour ton exemple (3 niveaux,4 sphères),
basé sur les voisins (x-1,y-1), (x-1,y), (x+1,y), (x-1,y+1), (x,y+1), (x-1,y+1) (on ignore les négatifs pour x, de meme ce qui dépasse, et pour y on utilise un modulo)
ta sphère (2,1) à comme voisin -> (1,0),(1,1),(3,1),(1,2),(2,2),(3,2).

en gros, chaque noeud possède 1->N lien (pour ta chaine, tu utiliserait juste 1 lien pour le noeud de début et de fin, et pour les autres, 2 liens : précédent et suivant)

Si tu as un algorithme(ou du pseudo-code), je veux bien y jeter un oeil

Edit2 : erf,je viens de voir que ta spirale de base n'est pas une chaine, mais déjà un graphe... :p