python: Erkennen eines Zyklus in NetzwerkX

Question

Wie der Titel impliziert, versuche ich eine Funktion zu schreiben, die die Anzahl der Zyklen berechnet, die ein eingegebener Knoten ist. Ich fand eine hilfreiche video, die die Theorie hinter einem Algorithmus zum Finden von Zyklen erklärt, aber ich habe Probleme zu verstehen, wie man es mit networkX implementieren kann, anstatt mit der Datenstruktur, die die Site verwendet. Ich konnte das Weiß/Grau/etc-Set-Konzept auch nicht verstehen, um das Netzwerk zu durchlaufen und Zyklen zu finden.

Meine Funktion Parameter/Struktur:

def feedback_loop_counter(G, node): 
    c = 0 
    calculate all cycles in the network 
    for every cycle node is in, increment c by 1 
    return c 

Der Netzknoten Eingang und Ausgang zu hat, und ich bin nicht klar, wie diese in der Berechnung Zyklus spielen

Das ist mein Eingangsnetzwerk:

import networkx as nx 
import matplotlib.pyplot as plt 
G=nx.DiGraph() 
molecules = ["CD40L", "CD40", "NF-kB", "XBP1", "Pax5", "Bach2", "Irf4", "IL-4", "IL-4R", "STAT6", "AID", "Blimp1", "Bcl6", "ERK", "BCR", "STAT3", "Ag", "STAT5", "IL-21R", "IL-21", "IL-2", "IL-2R"] 
Bcl6 = [("Bcl6", "Bcl6"), ("Bcl6", "Blimp1"), ("Bcl6", "Irf4")] 
STAT5 = [("STAT5", "Bcl6")] 
IL_2R = [("IL-2R", "STAT5")] 
IL_2 = [("IL-22", "IL-2R")] 
BCR = [("BCR", "ERK")] 
Ag = [("Ag", "BCR")] 
CD40L = [("CD40L", "CD40")] 
CD40 = [("CD40", "NF-B")] 
NF_B = [("NF-B", "Irf4"), ("NF-B", "AID")] 
Irf4 = [("Irf4", "Bcl6"), ("Irf4", "Pax5"), ("Irf4", "Irf4"), ("Irf4", "Blimp1")] 
ERK = [("ERK", "Bcl6"), ("ERK", "Blimp1"), ("ERK", "Pax5")] 
STAT3 = [("STAT3", "Blimp1")] 
IL_21 = [("IL-21", "IL-21R")] 
IL_21R = [("IL-21R", "STAT3")] 
IL_4R = [("IL-4R", "STAT6")] 
STAT6 = [("STAT6", "AID"), ("STAT6", "Bcl6")] 
Bach2 = [("Bach2", "Blimp1")] 
IL_4 = [("IL-4", "IL-4R")] 
Blimp1 = [("Blimp1", "Bcl6"), ("Blimp1", "Bach2"), ("Blimp1", "Pax5"), ("Blimp1", "AID"), ("Blimp1", "Irf4")] 
Pax5 = [("Pax5", "Pax5"), ("Pax5", "AID"), ("Pax5", "Bcl6"), ("Pax5", "Bach2"), ("Pax5", "XBP1"), ("Pax5", "ERK"), ("Pax5", "Blimp1")] 
edges = Bcl6 + STAT5 + IL_2R + IL_2 + BCR + Ag + CD40L + CD40 + NF_B + Irf4 + 
ERK + STAT3 + IL_21 + IL_21R + IL_4R + STAT6 + Bach2 + IL_4 + Blimp1 + Pax5 
G.add_nodes_from(molecules) 
G.add_edges_from(edges) 
sources = ["Ag", "CD40L", "IL-2", "IL-21", "IL-4"] 
targets = ["XBP1", "AID"] 

Answer 1

Ich werde meine Antwort unter der Annahme, Sie in „einfachen Zyklen“ interessiert sind, schreiben, das heißt Zyklen, deren einziger wiederholter Knoten der erste/letzte Knoten ist.

Nehmen Sie die Knoten mit Kanten zu einem Knoten u (die "Eingangsknoten"). Verwenden Sie dann den Befehl networkx all_simple_paths, um alle einfachen Pfade von u zu jedem der Eingabeknoten zu finden. Jeder von diesen wird zu einem einfachen Zyklus.

Answer 2

Die Idee, Zyklen zu finden, ist eine Depth-first search zu tun und während Sie es tun, erinnern Sie sich, welche Knoten Sie bereits gesehen haben und den Pfad zu ihnen. Wenn Sie zufällig einen Knoten sehen, den Sie bereits gesehen haben, dann gibt es einen Zyklus, und Sie können ihn finden, indem Sie Pfade verketten.

Versuchen Sie, einige Code zu schreiben, das zu tun, und öffnen Sie eine neue Frage mit diesem Code, wenn Sie nicht weiterkommen