Si vous avez déja eu l'occasion de travailler avec des réseaux de données ( une liste d'objet et de liens entre
ces objets ) vous avez du être confronté à la difficultée de les représenter graphiquement. Il existe plusieurs
algorithmes plus ou moins adaptés mettant en oeuvre des modèles de forces ( électrique, magnétique, gravitationnelles,.. )
A ma connaissance, ces algorithmes n'ont pas été portés en PHP.
Le code que je vous propose ici permet de représenter des réseaux de données en utilisant une implémentation
de l'algorithme de force / répulsion ( aussi appelé Spring forces ). Le rendus est effectué via la librairie
GD2. Quelques images illustrent cette articles, elles ont toutes été générées par ce script.
Le modèle d'attraction / répulsion est simple à construire, il consiste à calculer les vecteurs de forces
appliqués à chaques noeuds provenant de chaques autre noeuds.
Deux règles s'appliquent :
- Deux noeuds liés subiront une force d'attraction proportionelle à la distance qui les sépare.
- Deux noeuds appliqueront l'un par rapport à l'autre une force de répulsion inversement proportionelle à la distance qui les sépare.
|
|
 |
|
Pour calculer ces vecteurs il est nécessaire de faire quelques calculs trigonométriques.
 |
|
Les vecteurs sont caractérisés par un angle et une force. La force doit dépendre de la distance entre
les objets. Pour environ 20 objets, les valeurs suivantes permettent d'obtenir des graphs de qualité :
|
Une fois tous les vecteurs calculés pour chaques noeuds, il reste à les appliquer. Les étapes calcul /
déplacement doivent être répétées suffisamment de fois pour que l'équilibre des noeuds soit atteint. Dans
certaines configuration cela est impossible.
Je vous invite à télécharger ce script pour essayer de jouer avec les différents paramètres ( principalement
$RepulsionFactor, $RepulsionAtt, $AttractionFactor, $AttractionAtt ). Il convient des les adapter
suivant le nombre de noeuds et de liaisons.
Pour télécharger ce script,
cliquez ici.
Au début du script vous trouverez 3 méthodes pour générer des réseaux : "Every nodes connected to all nodes"
génère un réseau ou tous les noeuds sont reliés à tous les noeuds, "All nodes connected to a single same node"
génère un réseau ou tous les noeuds sont reliés à un noeud central, "All nodes with random connection to another node"
probablement le plus intéressant car les connections sont aléatoires. Le nombre de noeuds est définis par la
variable
$MaxNodes. Vous pouvez exécuter ce script en utilisant PHP-CLI :
php -q vectors.php
Le fichier
final.jpg sera alors généré dans le même répertoire.