RéSo
Résumé
RéSo proposes a decomposition of each (strongly) connected component of a graph. Its use is justified for researching center (s) / periphery (ies). It proceeds by classifying in successive layers of "fragile points" the vertices of each component. When no more fragile points appear, it classifies together the so-called "order 1" points of articulation that make the link between the different peripheries and the more central part, i.e. the vertices that guarantee continuity with the vertices in the margin. Then Reso repeats the search for peripheries ... This work continues until there are no more vertices in the component or until no vertice can be classified in this way. In the latter case, it classifies the points of articulation other than order 1 so as to highlight fracture lines between larger groups of vertices. Then the algorithm starts again for each new (strongly) connected component. It stops either when there are no more vertices, or when there are more points of articulation to classify (in this case, we say that the (or) part (s) remaining (s) is (are) non-decomposable). At any stage of the process, if the ranking of certain vertices causes the (strong) connectivity to be lost within the remaining vertices, RéSo continues its execution on each (strongly) connected component.
RéSo propose une décomposition de chaque composante (fortement) connexe d’un graphe. Son utilisation se justifie dans le cadre d’une recherche de type centre(s)/périphérie(s). Il procède en classant en couches successives de « points fragiles » les sommets de chaque composante. Lorsqu’il n’apparaît plus de points fragiles, il classe ensemble les points d’articulation dits « d’ordre 1 » qui font le lien entre les différentes périphéries et la partie plus centrale c’est-à-dire les sommets qui garantissent la continuité pour les sommets en marge. Puis Réso réitère la recherche de périphéries… Ce travail se poursuit jusqu’à ce qu’il n’y ait plus de sommets dans la composante ou bien jusqu’à ce qu’aucun sommet ne puisse plus être classée de cette façon. Dans ce dernier cas, il classe les points d’articulation autre que d’ordre 1 de manière à mettre en évidence des lignes de fracture entre groupes plus importants de sommets. Puis l’algorithme reprend à son début pour chaque nouvelle composante (fortement) connexe. Il s’arrête soit lorsqu’il n’y a plus de sommets, soit lorsqu’il n’y a plus de points d’articulation à classer (dans ce cas, on dit que la (ou les) partie(s) restante(s) est (sont) non décomposable(s)). A n’importe quelle étape du processus, si le classement de certains sommets fait perdre la (forte) connexité au sein des sommets restants, RéSo continue son exécution sur chaque composante (fortement) connexe.
Loading...