Comptage de tous les nœuds connectés dans le graphique

Question

J'ai une liste> 10k de paires de nombres (non ordonnés). Je voudrais les classer dans des ensembles de paires connectées directement ou indirectement. Je pense que cela correspond à un graphique non orienté. J'utilise python, et j'ai essayé quelque chose comme this pour représenter cette structure.

Afin de connaître tous les numéros connectés à i, je peux examiner s'il y a un chemin i-j pour tous j dans la liste, sauf i. Cependant, avec cette implémentation, le temps de calcul devient trop long pour la taille de la liste que j'ai affaire. Y a-t-il un moyen plus efficace de le faire? (Ou existe-t-il des bibliothèques python déjà établies?)

Answer 1

Il semble que vous soyez intéressé par le calcul des composants connectés d'un graphique. Je suggère de regarder dans le paquet networkx et son tools for computing components.

Par exemple, supposons que nos données est une liste de paires de nombres, chaque paire représentant une arête dans le graphe:

pairs = [ 
    (1, 2), 
    (2, 4), 
    (3, 5), 
    (2, 5), 
    (7, 9), 
    (9, 10), 
    (8, 7) 
] 

Dans le graphique représenté par ces bords, il y a un chemin entre une paire quelconque de nœuds dans l'ensemble {1, 2, 3, 4, 5}, et il existe également un chemin entre n'importe quelle paire de nœuds dans {6, 7, 8, 9, 10}. Mais il n'y a pas de chemin, disons, de 5 à 7. C'est-à-dire qu'il y a deux composants connectés dans le graphique.

Pour découvrir ces composants, nous avons d'abord importer networkx et créer un graphique:

>>> import networkx as nx 
>>> graph = nx.from_edgelist(pairs) 

Le calcul des composants est aussi simple que

>>> list(nx.connected_components(graph)) 
>>> [{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}] 

nx.connected_components est un générateur, et donc ici nous avons converti la résultat dans une liste afin d'afficher tous les composants connectés.

Nous pouvons également trouver le composant connecté contenant un noeud donné:

>>> nx.node_connected_component(graph, 3) 
{1, 2, 3, 4, 5} 

Nous pouvons aussi compter rapidement le nombre de composants connectés:

>>> nx.number_connected_components(graph) 
2