Community Spring Cleaning week is here! Join your fellow Maveryx in digging through your old posts and marking comments on them as solved. Learn more here!
Free Trial

Forum

Trouvez des réponses, posez des questions, et partagez votre expertise d’Alteryx.
TIPS de la semaine

Chaque semaine, découvrez de nouvelles astuces et bonnes pratiques pour devenir un expert !

Voir l'index
RÉSOLU

Minimum-distance Spanning Tree

Gottfried
Météore

Hello,

I am looking for a way to run a minimum-distance spanning tree algorithm in Alteryx. I would start with an input table listing all edges with 3 columns: [vertex 1], [vertex 2], [strength] (or distance or cost...). The goal would be to obtain the output table with the same format corresponding to the pruned optimal spanning tree (minimizing or maximizing the strength). I would then send it to the "Network Analysis Tool" to obtain a pretty force-graph.

 

A typical algorithm for that is "Prim's Algorithm" (https://en.wikipedia.org/wiki/Prim%27s_algorithm).

  • Does anyone see a way to perform this nicely directly within Alteryx?
  • Would you agree to support the idea that this could be a great in-built option for an improved Network Analysis Tool?

Best regards,

Gottfried

14 RÉPONSES 14
StephV
Alteryx Alumni (Retired)

Bonjour @Gottfried

 

merci pour ta question ! Je suis sûre qu’elle aidera aussi d’autres utilisateurs. Comme ce forum est en langue française, je t'invite à écrire de préférence en français.

 

Si tu préfères l’anglais, aucun problème, tu peux poster ta question sur le forum anglais.

 

Je suis sure que @StephaneP@Jean-Balteryx@Ladarthure@carlosteixeira, @annedione ou @mathieuf pourront t'aider ! Ceux sont des experts 😊🏆😀

Steph Vitale-Havreng
StephaneP
Alteryx
Alteryx

Bonsoir @Gottfried ,

 

Voici une solution avec une macro itérative.

J'ai reproduis avec les outils Alteryx le processus expliqué sur la page Wikipedia que tu avais mis en lien.

Je ne sais pas si c'est la plus élégante mais elle me semble fonctionner sur quelques exemples que j'ai testé.

StephaneP_0-1604701411025.png

J'espère que cela t'aidera.

 

Cette macro minimise le cout total.Il faut inverser dans la macro si tu souhaites l'inverse, voir mettre une option sur la macro pour inverser à la voléeen fonction de ta sélection.

 

J'ai aussi placé le workflow de base qui m'a servi à créer la macro. Il est intéressant pour comprendre itération par itération ce qu'il réalise en fonction des cas particuliers.

Jai placé les données associées aux différentes étapes pour comprendre rapidement le principe.

StephaneP_0-1604703443089.png

 

 

Enjoy !

 

Stéphane Portier
Sales Engineer
Alteryx
Gottfried
Météore

Bonjour @StephaneP ,

 

En préambule, je veux dire que je suis positivement impressionné par votre macro (et la rapidité avec laquelle vous l'avez conçue). Elle me servira aussi de rampe de lancement pour apprendre à manipuler les macros itératives. Et oui, elle fonctionne ! J'apprécie tout particulièrement le tour de force d'avoir tout fait en pur Alteryx. Un grand bravo !

 

Entre temps, il se trouve que je me suis lâchement essayé à utiliser le R tool et à y intégrer un algorithme trouvé sur le CRAN. Et ça marche aussi très bien. (J'ai posté ça côté anglophone... peut-être l'avez-vous vu). Bon d'accord, c'était la solution de facilité... comparé à votre macro.

 

Pour info, l'algorithme en R intégré est celui-ci (avant quelques bidouilles pour que ça fonctionne avec Alteryx) :

https://rdrr.io/cran/edmcr/src/R/mst.R

 

Si je puis me permettre et au cas où vous voulez peaufiner votre excellente macro ou la suggérer aux développeurs Alteryx, voici une idée d'amélioration : ce serait utile d'avoir directement un output supplémentaire avec la liste des champs. Pourquoi ? Eh bien parce que derrière il est sympa de pouvoir enchaîner avec le tool Network Analysis et ses graphes de force. Si les développeurs se penchent sur la fonctionnalité je pense même qu'elle devrait être intégrée directement comme une option caractérisant les graphes en sortie de Network Analysis, sous forme d'une amélioration de ce tool, en somme.

 

En tous cas, grand merci !

Chapeau bas. Je garde vos coordonnées...

 

Bon week-end

Gottfried Mathurin

https://linkedin.com/in/gottfriedmathurin

StephaneP
Alteryx
Alteryx

Hello @Gottfried ,

 

Youpi, content de savoir qu'elle fonctionne correctement.

 

Je pense que cela ne doit pas être bien long de rajouter ce que tu demandes, l'output avec la liste.

Histoire d'être sur de ce qui t'intéresse, peux tu me fournir un exemple concret basé sur 1 des 2 exemples de ma macro ?

 

Par ailleurs il y a une section dédiée aux demandes d'améliorations du produit. Elle se trouve ici : Product ideas 

Tu peux valider si ta demande n'a pas déjà été faite par quelqu'un et ainsi ajouter des votes, ou en créer une en espérant motiver les troupes. 🙂

 

Personnellement je n'ai pas encore compris l'intéret de mixer cela avec le Network Analysis. As tu un article ou un exemple concret à partager pour que je m'inprègne du sujet ?

 

Merci

Stéphane Portier
Sales Engineer
Alteryx
Gottfried
Météore

Bonjour Stéphane,

CI-joint, je te renvoie ton workflow avec l'ajout du network tool. Tu verras (en consultant les browse tools en config) qu'il permet d'obtenir directement les diagrammes (en plus sous forme de force graph, très sympa à manipuler). Les minimum spanning trees ont toutes sortes d'application (il suffit de taper ces mots clés dans Google pour s'en convaincre). Leur côté "spanning" est notamment intéressant car ils forment réellement des arbres, donc des structures sans boucle. Je les utilise personnellement dans pour analyser des données catégorielles en première approximation d'un réseau bayésien ou simplement pour repérer les principales dépendances entre variables avant d'engager d'autres étapes d'analyse statistique ou prédictive. C'est l'approche de Chow-Liu... (Wikipedia).

 

Je me suis permis de renommer ta macro avec "Prim's". En effet, on doit l'algorithme à un certain Robert C. Prim en 1957 (Wikipedia)... qui n'a donc rien à voir avec un prisme. Et ça me chagrine parce que j'aime vraiment beaucoup l'icône de prisme que tu as affectée à ta superbe macro !

 

Bonne journée

Gottfried

StephaneP
Alteryx
Alteryx

Hello @Gottfried ,

 

Merci pour les explications, c'est plus clair et c'est vrai que du coup les 2 algorytmes s'enchainnent naturellement effectivement.

J'ai donc modifié la macro pour rajouter en output la sortie des Vertex pour enchainer directement les 2 outils.

 

Et pour rendre à César (Prism pardon) ce qui lui appartient j'ai donc changé le nom et l'image de la macro. 🙂

De toute manière on peut changer les icones des macros.

StephaneP_1-1604938892150.png

 

Petite astuce Gottfried, lorsque tu pousses un workflow avec des dépendances (macros, fichiers sources ou output) il vaut mieux utiliser l'option "Export Worklfow" qui embarque tous les fichiers liés. Cela génère une sorte de zip, une.yxzp que tu peux ouvrir aussi dans le designer.
Dans ton dernier post la macro n'était pas intégrées par exemple et donc le workflow inexploitable.

StephaneP_2-1604939021714.png

 

Enjoy !

 

 

Stéphane Portier
Sales Engineer
Alteryx
Gottfried
Météore

Super !

Juste un petit détail au sujet de César. Je crois que c'est Prim, pas Prism. Le 's n'apparaît que pour le génitif, pour dire l'algorithme de Prim, donc Prim's algorithm en anglais. Tu dois malheureusement totalement abandonner toute référence à ce bel objet diffractant la lumière... 😁

Gottfried

StephV
Alteryx Alumni (Retired)

Merci @StephaneP d'avoir pu aider @Gottfried ! Et merci à toi @Gottfried pour ces excellents insights. Je suis sûre qu'ils bénéficieront à l'ensemble de la communauté. 

 

Excellente journée à tous !

Steph Vitale-Havreng
StephaneP
Alteryx
Alteryx

😂

J'ai un vrai problème avec le nom de cette macro !!
Mon cerveau ne vois que ce qu'il veut. Depuis le début tu as bien indiqué "Prim". 😄

 

Du moment qu'on arrive à calculer le chemin le plus court on est bon. Ouf.

Stéphane Portier
Sales Engineer
Alteryx
Étiquettes