L'action `minSpanTree` calcule l'arbre couvrant de poids minimum pour un graphe donné. Un arbre couvrant d'un graphe non orienté, connexe et pondéré est un sous-graphe qui connecte tous les nœuds ensemble, sans aucun cycle et avec le poids total minimum possible des arêtes. Pour un graphe orienté, il s'agit d'une arborescence couvrante. Cette action est fondamentale dans les problèmes de conception de réseau pour minimiser les coûts de connexion.
| Paramètre | Description |
|---|---|
| deterministic | Lorsque défini sur True, garantit que chaque invocation (avec la même configuration machine et les mêmes paramètres) produit le même résultat final. |
| direction | Spécifie si le graphe d'entrée doit être considéré comme orienté ou non orienté. |
| display | Spécifie une liste de tables de résultats à envoyer au client pour affichage. |
| distributed | Lorsque défini sur True, utilise un graphe distribué. |
| graph | Spécifie le graphe en mémoire à utiliser. |
| indexOffset | Spécifie le décalage d'index pour les identifiants dans les journaux et les tables de résultats. |
| links | Spécifie la table de données d'entrée qui contient les informations sur les arêtes du graphe. |
| linksVar | Spécifie les noms des variables de données pour la table des arêtes. |
| logFreqTime | Contrôle la fréquence (en secondes) d'affichage des journaux d'itération pour certains algorithmes. |
| logLevel | Contrôle la quantité d'informations affichées dans le journal SAS. |
| multiLinks | Lorsque défini sur True, inclut les multi-arêtes lors de la lecture d'un graphe d'entrée. |
| nodes | Spécifie la table de données d'entrée qui contient les informations sur les nœuds du graphe. |
| nodesVar | Spécifie les noms des variables de données pour la table des nœuds. |
| nThreads | Spécifie le nombre maximum de threads à utiliser pour le traitement multithread. |
| out | Spécifie la table de données de sortie pour contenir la solution du problème de l'arbre couvrant de poids minimum. |
| outGraphList | Spécifie la table de données de sortie pour contenir les informations récapitulatives sur les graphes en mémoire. |
| outLinks | Spécifie la table de données de sortie pour contenir les informations sur les arêtes du graphe ainsi que les résultats. |
| outNodes | Spécifie la table de données de sortie pour contenir les informations sur les nœuds du graphe ainsi que les résultats. |
| outputTables | Liste les noms des tables de résultats à sauvegarder en tant que tables CAS sur le serveur. |
| selfLinks | Lorsque défini sur True, inclut les boucles (arêtes reliant un nœud à lui-même) lors de la lecture d'un graphe d'entrée. |
| source | Spécifie le nœud source pour le problème de l'arbre couvrant de poids minimum dirigé. |
| standardizedLabels | Lorsque défini sur True, spécifie que les données du graphe d'entrée sont dans un format standardisé. |
| standardizedLabelsOut | Lorsque défini sur True, demande que les données du graphe de sortie incluent le format standardisé. |
Ce bloc de code crée une table CAS nommée 'mycas.LinkSetIn' qui représente les arêtes d'un graphe avec leurs poids. Cette table sera utilisée dans les exemples pour calculer l'arbre couvrant minimum.
| 1 | DATA mycas.LinkSetIn; |
| 2 | INFILE DATALINES delimiter=','; |
| 3 | INPUT from $ to $ weight; |
| 4 | DATALINES; |
| 5 | A,B,1 |
| 6 | A,C,4 |
| 7 | B,C,2 |
| 8 | B,D,5 |
| 9 | C,D,8 |
| 10 | C,E,3 |
| 11 | D,E,7 |
| 12 | D,F,6 |
| 13 | E,F,9 |
| 14 | ; |
| 15 | RUN; |
Cet exemple calcule l'arbre couvrant de poids minimum pour le graphe non orienté défini dans 'mycas.LinkSetIn'. Les résultats, c'est-à-dire les arêtes formant l'arbre, sont stockés dans la table 'mycas.MST_out'.
| 1 | PROC CAS; |
| 2 | optNetwork.minSpanTree / |
| 3 | links={name='LinkSetIn'} |
| 4 | out={name='MST_out', replace=true}; |
| 5 | RUN; |
Cet exemple calcule l'arborescence couvrante de poids minimum pour un graphe orienté, en spécifiant le nœud 'A' comme source. Le graphe est défini par les mêmes données, mais l'option 'direction' est explicitement définie sur 'DIRECTED'. Cela est utile pour trouver le chemin le moins coûteux pour diffuser une information depuis une source vers tous les autres nœuds.
| 1 | PROC CAS; |
| 2 | optNetwork.minSpanTree / |
| 3 | direction='DIRECTED' |
| 4 | SOURCE='A' |
| 5 | links={name='LinkSetIn'} |
| 6 | out={name='MST_out_directed', replace=true}; |
| 7 | RUN; |