L'action minCut calcule la coupe minimale d'un graphe. Une coupe minimale est une partition des sommets d'un graphe en deux ensembles disjoints, S (contenant la source) et T (contenant le puits), qui minimise la somme des poids des arêtes allant de S à T. Cette action est fondamentale en théorie des graphes et en optimisation de réseaux pour identifier les goulots d'étranglement ou les vulnérabilités dans un réseau.
| Paramètre | Description |
|---|---|
| deterministic | Lorsque défini sur True, garantit que chaque exécution (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 liens du graphe. |
| linksVar | Spécifie les noms des variables de données pour la table des liens. |
| 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. |
| maxCuts | Spécifie le nombre maximal de coupes que l'algorithme doit retourner. |
| maxWeight | Spécifie le poids maximal des coupes à retourner par l'algorithme. |
| multiLinks | Lorsque défini sur True, inclut les liens multiples 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 maximal de threads à utiliser pour le traitement multithread. |
| outCutSets | Spécifie la table de données de sortie pour contenir les ensembles de coupe minimale. |
| outGraphList | Spécifie la table de données de sortie pour contenir des 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 liens du graphe ainsi que les résultats des algorithmes. |
| 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 des algorithmes. |
| outPartitions | Spécifie la table de données de sortie pour contenir les partitions de la coupe minimale. |
| 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 liens réflexifs (boucles) lors de la lecture d'un graphe d'entrée. |
| sink | Spécifie le nœud de destination (puits) de la coupe minimale. |
| source | Spécifie le nœud de départ (source) de la coupe minimale. |
| 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 un format standardisé. |
Ce code crée une table CAS nommée 'mycas.LinkSetIn' qui représente un réseau simple avec 6 nœuds et des arêtes pondérées. Les poids peuvent être interprétés comme la capacité maximale de flux entre les nœuds.
| 1 | DATA mycas.LinkSetIn; |
| 2 | INFILE DATALINES delimiter=','; |
| 3 | INPUT from $ to $ weight; |
| 4 | DATALINES; |
| 5 | A,B,2 |
| 6 | A,C,7 |
| 7 | A,D,4 |
| 8 | B,C,3 |
| 9 | B,E,1 |
| 10 | C,E,2 |
| 11 | C,D,2 |
| 12 | D,F,6 |
| 13 | E,F,3 |
| 14 | ; |
Cet exemple calcule la coupe minimale entre le nœud 'A' (source) et le nœud 'F' (puits) dans le graphe non orienté. La coupe minimale identifie l'ensemble d'arêtes de capacité totale minimale qui, si elles étaient supprimées, déconnecteraient 'F' de 'A'.
| 1 | PROC CAS; |
| 2 | ACTION optNetwork.minCut / |
| 3 | direction = "UNDIRECTED" |
| 4 | links = {name = "LinkSetIn"} |
| 5 | SOURCE = "A" |
| 6 | sink = "F" |
| 7 | outCutSets = {name="MinCut" replace=true} |
| 8 | outPartitions = {name="Partitions" replace=true}; |
| 9 | RUN; |
| 10 | ACTION TABLE.fetch / TABLE = "MinCut"; |
| 11 | RUN; |
| 12 | ACTION TABLE.fetch / TABLE = "Partitions"; |
| 13 | RUN; |
| 14 | QUIT; |
Cet exemple illustre comment trouver jusqu'à 2 coupes minimales ('maxCuts'=2) dont le poids total est inférieur ou égal à 7 ('maxWeight'=7.0) dans un graphe orienté. Cela permet d'identifier plusieurs ensembles de goulots d'étranglement potentiels.
| 1 | PROC CAS; |
| 2 | ACTION optNetwork.minCut / |
| 3 | direction = "DIRECTED" |
| 4 | links = {name = "LinkSetIn"} |
| 5 | SOURCE = "A" |
| 6 | sink = "F" |
| 7 | maxCuts = 2 |
| 8 | maxWeight = 7.0 |
| 9 | outCutSets = {name="MinCutMulti" replace=true} |
| 10 | outPartitions = {name="PartitionsMulti" replace=true}; |
| 11 | RUN; |
| 12 | PRINT cas.results.SolutionSummary; |
| 13 | ACTION TABLE.fetch / TABLE = "MinCutMulti"; |
| 14 | RUN; |
| 15 | ACTION TABLE.fetch / TABLE = "PartitionsMulti"; |
| 16 | RUN; |
| 17 | QUIT; |