optNetwork

minCut

##set_optnetwork

Description

L'action `minCut` calcule la coupe minimale (minimum cutEnsemble minimal d'arcs dont la suppression sépare un réseau en deux sous-groupes déconnectés, minimisant la capacité totale de passage entre une source et une destination.) d'un graphe. En d'autres termes, elle cherche le moyen le moins coûteux de séparer votre graphe en deux, comme si vous cherchiez le meilleur endroit pour couper un pont sans trop vous fatiguer. ✂️ Elle prend en charge les graphes orientés et non orientés et peut calculer soit la coupe minimale globale, soit la coupe minimale entre un nœud source et un nœud cible (sinkDans un réseau, un sink (puits) est un nœud de destination finale qui absorbe le flux. Il possède une demande nette positive et aucun arc de sortie dans les modèles de flux optimisés.) .

Syntaxe Officielle
proc cas;
optNetwork.minCut /
direction="UNDIRECTED"
links={name="nom_table_liens"}
nodes={name="nom_table_noeuds"}
outCutSets={name="table_coupes_sortie", replace=true}
outPartitions={name="table_partitions_sortie", replace=true}
source="noeud_source"
sink="noeud_cible"
maxCuts=1;
run;
quit;

Paramètres Clés

Nom du paramètre Description
direction Spécifie si le graphe est orienté ('DIRECTED') ou non orienté ('UNDIRECTED'). Par défaut, c'est 'UNDIRECTED'.
links Table CAS en entrée contenant les informations des liens (arêtes) du graphe.
outCutSets Table de sortie listant les arêtes qui composent la (ou les) coupe(s) minimale(s).
outPartitions Table de sortie contenant l'affectation des nœuds aux partitions générées par la coupe.
source Nœud source (point de départ) pour trouver une coupe s-t spécifique.
sink Nœud cible (point d'arrivée) pour trouver une coupe s-t spécifique.
maxCuts Nombre maximum de coupes à retourner par l'algorithme. La valeur par défaut est 1.

Préparation des données

Création d'un graphe pondéré de test

Nous créons un petit réseau de 5 nœuds pour illustrer la découpe. Assurez-vous d'avoir une session CAS active (associée ici à la caslib 'mycas').

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

Exemples d'utilisation

Calcul de la coupe minimale globale

Cet exemple cherche la coupe globale la plus petite dans le graphe non orienté fourni, sans spécifier de source ou de cible.

1PROC CAS;
2 optNetwork.minCut /
3 links={name="LinkSetIn"}
4 outCutSets={name="CutSetsOut", replace=true}
5 outPartitions={name="PartitionsOut", replace=true};
6RUN;
7QUIT;
Résultat Attendu :
L'action renvoie la coupe minimale globale. La table `CutSetsOut` listera les arêtes à retirer pour partitionner le graphe avec le poids total le plus faible, et `PartitionsOut` indiquera dans quel sous-graphe se trouve chaque nœud.
Calcul de la coupe minimale s-t (Source vers Sink)

Ici, l'algorithme cherche spécifiquement la coupe minimale pour déconnecter le nœud 'A' (source) du nœud 'E' (cible). Le paramètre logLevel='AGGRESSIVE' affichera tous les détails algorithmiques dans le journal SAS pour les curieux. 🕵️‍♂️

1PROC CAS;
2 optNetwork.minCut /
3 direction="UNDIRECTED"
4 links={name="LinkSetIn"}
5 SOURCE="A"
6 sink="E"
7 outCutSets={name="CutSetsOut_ST", replace=true}
8 outPartitions={name="PartitionsOut_ST", replace=true}
9 logLevel="AGGRESSIVE";
10RUN;
11QUIT;
Résultat Attendu :
Génère les tables `CutSetsOut_ST` et `PartitionsOut_ST` qui définissent la coupe s-t optimale séparant A de E. Le journal SAS contiendra une trace détaillée des opérations algorithmiques effectuées en mémoire distribuée.
Sommaire