optNetwork

minSpanTree

##set_optnetwork

Description

L'action minSpanTree (du jeu d'actions optNetwork ) calcule l'arbre couvrant de poids minimum (Minimum Spanning TreeSous-ensemble d'arcs reliant tous les nœuds d'un réseau sans former de cycle, tout en minimisant la somme totale des poids (coûts ou distances) de ces connexions.) d'un graphe. Dans un graphe pondéré, cette action trouve le sous-ensemble d'arêtes qui connecte tous les sommets ensemble, sans aucun cycle et avec le poids total le plus faible possible. C'est un peu comme essayer de tirer des câbles réseau entre tous les bureaux d'une entreprise en achetant le moins de câble possible !

Syntaxe Officielle
proc cas;
optNetwork.minSpanTree /
deterministic=TRUE | FALSE,
direction="DIRECTED" | "UNDIRECTED",
links={name="table-name", caslib="string"},
linksVar={from="variable-name", to="variable-name", weight="variable-name"},
nodes={name="table-name", caslib="string"},
nodesVar={node="variable-name", weight="variable-name"},
out={name="table-name", caslib="string", replace=TRUE | FALSE},
source="string",
logLevel="AGGRESSIVE" | "BASIC" | "MODERATE" | "NONE";
run;
quit;

Paramètres Clés

Nom du paramètre Description
direction Spécifie si le graphe d'entrée doit être considéré comme orienté (DIRECTED) ou non orienté (UNDIRECTED).
links Spécifie la table d'entrée contenant les informations sur les liens (arêtes) du graphe.
linksVar Spécifie les noms des variables de données pour la table des liens (origine, destination et poids de l'arête).
out Spécifie la table de sortie qui contiendra la solution du problème d'arbre couvrant de poids minimum.
source Spécifie le noeud source pour le problème de l'arbre couvrant minimum orienté (utile uniquement si direction='DIRECTED').
logLevel Contrôle la quantité d'informations affichées dans le journal SAS (log).

Préparation des données

Création des données du graphe

Nous allons générer une table de liens représentant un petit réseau avec des distances (poids) entre différents noeuds.

1DATA casuser.my_links;
2 LENGTH from $10 to $10 weight 8;
3 INPUT from $ to $ weight;
4 DATALINES;
5A B 2
6A C 3
7B C 1
8B D 1
9C D 4
10C E 5
11D E 1
12;
13RUN;

Exemples d'utilisation

Calcul de l'arbre couvrant minimum

Dans cet exemple, nous cherchons le chemin le plus court (en termes de poids total) pour relier tous les nœuds de notre graphe.

1PROC CAS;
2 optNetwork.minSpanTree /
3 links={name="my_links", caslib="casuser"}
4 linksVar={from="from", to="to", weight="weight"}
5 out={name="mst_out", caslib="casuser", replace=true};
6RUN;
7QUIT;
Résultat Attendu :
L'action retourne un résumé ProblemSummary%%https://go.documentation.sas.com/doc/en/pgmsascdc/v_069/casactnopt/cas-optnetwork-minspantree.htm#SAS.cas-optnetwork-minspantree-rslts%%. Une nouvelle table mst_out est générée en mémoire, contenant uniquement les arêtes qui forment l'arbre couvrant minimum. Pour ce graphe, les arêtes A-B, B-C, B-D et D-E seront sélectionnées, donnant un poids total minimal.
Arbre couvrant minimum orienté avec log agressif

Ici, nous configurons un graphe orienté en spécifiant un noeud source%%https://go.documentation.sas.com/doc/en/pgmsascdc/v_069/casactnopt/cas-optnetwork-minspantree.htm#SAS.cas-optnetwork-minspantree-source%%. Nous demandons également un niveau de log agressif pour voir tous les détails d'exécution de l'algorithme.

1PROC CAS;
2 optNetwork.minSpanTree /
3 direction="DIRECTED"
4 SOURCE="A"
5 links={name="my_links", caslib="casuser"}
6 linksVar={from="from", to="to", weight="weight"}
7 logLevel="AGGRESSIVE"
8 out={name="mst_directed_out", caslib="casuser", replace=true};
9RUN;
10QUIT;
Résultat Attendu :
Le journal affichera un niveau de détail élevé (AGGRESSIVE). La table mst_directed_out contiendra les arêtes de l'arborescence de poids minimum partant du nœud 'A' et rejoignant tous les autres nœuds de manière orientée.
Sommaire