erhalten die Kanten innerhalb einer Liste von Knoten

Question

Wie bekomme ich alle Kanten, deren beide Knoten innerhalb einer bestimmten Liste von Knoten sind. G.edges([list_of_nodes]) gibt alle Knoten zurück, bei denen sich mindestens ein Knoten jeder Kante in der list_of_nodes befindet. Ich möchte das nicht. Wie kann ich es bekommen?

Answer 1

Sie können alle bereits gefundenen Kanten durchlaufen und testen, ob beide Knoten in der Liste der Knoten enthalten sind. Dies ist jedoch nicht optimal, wenn die Liste der Knoten groß ist. Die Überprüfung, ob eine Liste ein Element enthält, erfordert ein Durchlaufen der Liste, so dass im Durchschnitt jede Kante 2*len(list)/2 Prüfungen [len(list)/2 für jeden Knoten] benötigt. Unter der Annahme, dass die Anzahl der Kanten proportional zu len(list) ist, hat dies eine quadratische Zeit.

edges = [(u,v) for u,v in G.edges(list_of_nodes) if u in list_of_nodes and v in list_of_nodes] 

Eine effizientere Methode wäre testen, ob die Knoten in einem Satz anstelle einer Liste enthalten sind. Sets ermöglichen sehr schnell zu prüfen, ob sie ein Element enthalten. Es ist fast O(1) pro Test. So läuft das Ganze in linearer Zeit.

set_of_nodes = set(list_of_nodes) 
edges = [(u,v) for u,v in G.edges(set_of_nodes) if u in set_of_nodes and v in set_of_nodes]