Cas centré-arêtes

Dans le chapitre 9, nous n'avons pas traité le cas centré-arêtes. Il est légitime de se demander si dans le cas centré-arêtes, on pourrait utiliser la même fonction connected(G) que dans le cas centré-sommets. Les fonctions unmark_all(G) et all_nodes_marked(G) fonctionnent pour les deux types abstraits puisqu'elles n'utilisent que des opérations communes aux deux types.

Par contre la fonction mark_from(s) du type centré-sommets ne peut pas être utilisée pour le type centré-arêtes puisque elle utilise l'opération NB_EDGES(s) qui est spécifique au type centré-sommets.

Malheureusement, dans le type centré-arêtes, une opération équivalente à mark_from(s) ne peut pas être réalisée aussi facilement qu'avec le type centré-sommets car on n'a pas accès facilement aux arêtes issues d'un sommet. Cet accès ne peut se faire qu'en parcourant pour chaque sommet l'ensemble de ses arêtes. La complexité obtenue sera $O(\vert V(G)\vert * \vert E(G)\vert)$ au lieu de $O(\vert V(G)\vert + \vert E(G)\vert)$ dans le cas centré-sommets.

Pour pouvoir parcourir l'ensemble des arêtes du graphe il faut passer le graphe en paramètre en plus du sommet. Ce qui donnera la fonction suivante :

def mark_from (s, G):
    if NODE_MARKED(s):
        return
    MARK_NODE(s)
    for i in range(NB_EDGES(G)):
        e = EDGE(G, i)
        if EDGE_END(e, 0) == s:
            mark_from(EDGE_END(e, 1), G)
        if EDGE_END(e, 1) == s:
            mark_from(EDGE_END(e, 0), G)

La fonction connexité s'écrira alors de manière similaire au cas centré-sommets mais aura une complexité $O(\vert V(G)\vert * \vert E(G)\vert)$.

def connected (G):
    unmark_all(G)
    mark_from(NODE(G, 0), G)
    return all_nodes_marked(G):