biconnectedComponents
Description
L'action biconnectedComponents identifie les composantes biconnexes et les points d'articulation dans un graphe non orienté. Une composante biconnexe est un sous-graphe tel que n'importe quel sommet peut être retiré sans déconnecter le reste. Les points d'articulation sont ces sommets critiques dont le retrait augmente le nombre de composantes connectées. En gros, c'est l'outil idéal pour trouver les maillons faibles qui, s'ils cassent, font s'effondrer toute la structure (un peu comme le fil rouge dans un film d'action).
Paramètres Clés
| Nom du paramètre | Description |
|---|---|
| deterministic | Indique si l'algorithme doit produire des résultats identiques à chaque exécution sur la même configuration. |
| direction | Définit si le graphe est orienté ou non. Notez que les composantes biconnexes s'appliquent généralement aux graphes non orientés (UNDIRECTED). |
| links | Définit la table CAS contenant les liens du graphe (from, to). |
| out | Table de sortie contenant le résumé des composantes biconnexes trouvées. |
| outNodes | Table de sortie listant les points d'articulation détectés dans le graphe. |
| outLinks | Table de sortie assignant chaque lien à un identifiant de composante biconnexe. |
| outBCTreeLinks | Spécifie la table de sortie pour les liens de l'arbre bloc-coupure (block-cut tree). |
Préparation des données
Création d'un graphe simple pour l'analyse de biconnexité
On crée un ensemble de liens représentant un graphe où certains nœuds (comme 'C' ou 'E') agissent comme des ponts entre des structures cycliques.
| 1 | DATA mycas.LinkSetIn; |
| 2 | INPUT from $ to $ @@; |
| 3 | DATALINES; |
| 4 | A B A C B C C D C E D E E F E G F G |
| 5 | ; |
| 6 | RUN; |
Exemples d'utilisation
Calcul de base des composantes biconnexes
Exécution de l'action avec les paramètres par défaut pour obtenir un résumé.
| 1 | PROC CAS; |
| 2 | optNetwork.biconnectedComponents / |
| 3 | links = {name = "LinkSetIn"} |
| 4 | out = {name = "BiconnSummary", replace = true}; |
| 5 | RUN; |
Résultat Attendu :
Analyse complète avec identification des points d'articulation
On demande explicitement la création des tables de sortie pour voir quels nœuds sont des points d'articulation et quels liens appartiennent à quelle composante.
| 1 | PROC CAS; |
| 2 | optNetwork.biconnectedComponents / |
| 3 | links = {name = "LinkSetIn"} |
| 4 | outNodes = {name = "NodeOut", replace = true} |
| 5 | outLinks = {name = "LinkOut", replace = true} |
| 6 | out = {name = "BiconnSummary", replace = true}; |
| 7 | /* Affichage des points d'articulation */ |
| 8 | TABLE.fetch / TABLE = {name = "NodeOut", where = "artpoint = 1"}; |
| 9 | RUN; |