Composants liés du graphique

Bonjour. Composants concaténés du graphe ([graphe concaténé](https://ja.wikipedia.org/wiki/concatenated graph), [structure de données de l'ensemble élémentaire](https://ja.wikipedia.org/wiki/elementary structure de données de l'ensemble) J'ai trouvé "composants connectés Python" (Stack Overflow) dans le calcul pour trouver. J'y ai couru la source presque telle quelle et l'ai comparée aux résultats de networkx pour vérification.

graph.jpg

$ ./connected_components.py
graph = {0: [1, 2, 3], 1: [2], 2: [], 3: [4, 6], 4: [], 5: [7], 6: [], 7: []}
[[0, 1, 2, 3, 4, 6], [5, 7]]
True (equal to one derived from networkx)

connected_components.py


#!/usr/bin/env python
from __future__ import print_function

def connected_components(graph):
    seen = set()
    def component(n):
        nodes = set([n])
        while nodes:
            n = nodes.pop()
            seen.add(n)
            nodes |= set(graph[n]) - seen
            yield n
    for n in graph:
        if n not in seen:
            yield component(n)

def print_gen(gen):
    print([list(x) for x in gen])

def check_connected(graph):
    import networkx as nx
    G = nx.Graph()
    G.add_nodes_from(graph.keys())
    for k, v in graph.items():
        for n in v:
            G.add_edge(k, n)
    check = sorted([set(x) for x in nx.connected_components(G)]) == sorted([set(x) for x in connected_components(graph)])
    print(check, "(equal to one derived from networkx)")

graph = {0: [1, 2, 3], 1: [2], 2: [], 3: [4, 6], 4: [], 5: [7], 6: [], 7: []}

print("graph =", graph)
print_gen(connected_components(graph))
check_connected(graph)

# graph:
#       0
#     / | \
#    1--2  3
#          | \
#          4  6
#    5--7

«Je suis désolé que le service de jugement des chèques soit un peu enfantin.

Recommended Posts

Composants liés du graphique
À propos des composants de Luigi
Afficher le graphique de tensorBoard sur Jupyter
Augmentez la taille de la police du graphique avec matplotlib
La base de la théorie des graphes avec l'animation matplotlib
Le début de cif2cell
Le sens de soi
le zen de Python
L'histoire de sys.path.append ()
La vengeance des types: la vengeance des types
Omettre les graduations du graphique après la virgule décimale dans matplotlib
Aligner la version de chromedriver_binary
Grattage du résultat de "Schedule-kun"
10. Compter le nombre de lignes
L'histoire de la construction de Zabbix 4.4
Vers la retraite de Python2
Comparez les polices de jupyter-themes
Obtenez le nombre de chiffres
Avoir le graphique d'équation de la fonction linéaire dessiné en Python
Expliquez le code de Tensorflow_in_ROS
Réutiliser les résultats du clustering
GoPiGo3 du vieil homme
Couper le graphe de calcul PyTorch
Calculez le nombre de changements
Changer le thème de Jupyter
La popularité des langages de programmation
Changer le style de matplotlib
Trouver le diamètre du graphique par recherche de priorité de largeur (mémoire Python)
Graphique de base à une ligne de HoloViews
Filtrer la sortie de tracemalloc
À propos des fonctionnalités de Python
Tracé interactif du graphique 3D
Simulation du contenu du portefeuille
Le pouvoir des pandas: Python
[Statistiques] Saisir l'image de la théorie de la limitation du pôle central avec un graphe
Affichez l'image de la caméra connectée à l'ordinateur personnel sur l'interface graphique.
[TensorFlow 2] Comment vérifier le contenu de Tensor en mode graphique
Compter la partie concaténée maximale d'un graphe aléatoire avec NetworkX
Bases de Seaborn pour les débutants ① Graphique agrégé du nombre de données (Countplot)
Les spécifications de pytz ont changé
Tester la version du module argparse
Trouvez la définition de la valeur de errno
jour de course des dockers (note)
L'histoire de Python et l'histoire de NaN
Élever la version de pyenv elle-même
Obtenez le nombre de vues de Qiita
First Python 3 ~ Le début de la répétition ~
L'histoire de la participation à AtCoder
Changer l'arrière-plan d'Ubuntu (GNOME)
J'ai étudié le mécanisme de connexion flask!
Comprendre le contenu du pipeline sklearn
Le monde des livres d'ingénierie de contrôle
Entrez dans l'obscurité de msync
Prenez le journal d'exécution du céleri
Tester l'adéquation de la distribution
Existence du point de vue de Python