Anzahl der verbundenen Kanten zu einem Knoten und Knoten mit maximal verbundenen Kanten finden

Question

Wie finde ich in einem Diagramm die Anzahl der verbundenen (direkt gebundenen) Kanten zu einem Knoten?
Und dann wäre es trivial, aber wenn es irgendeine direkte Methode gibt, um die eindeutigen Knoten mit den maximalen Kanten zu finden, die mit ihnen verbunden werden, wäre es nett.
Ich benutze Python 2.7 und Networkx.

Bis jetzt bin ich wie dies zu tun:

sG   = list(nx.connected_component_subgraphs(G)) # sG is a sub_graph of main graph G 
nb_sG   = len(sub_graphs) 
max_con_node = list() 
for m in xrange(nb_sG): 
    sG_nodes  = [(node, len(sG[m].edges(node)), sG[m].edges(node)) for node in sG[m].nodes()] 
    connexions = [i[1] for i in sG_nodes] 
    idx   = [i for i,x in enumerate(connexions) if x==max(connexions)] 
    max_con_node.append((max(connexions), [sG_nodes[i][0] for i in idx])) 

Dank.

Answer 1

Es sieht so aus, als ob Sie eine Adjazenzliste verwenden, um Ihr Diagramm darzustellen. Um die Anzahl der Kanten zu finden, die mit einem Knoten verbunden sind, können Sie die Größe Ihrer Adjazenzliste für diesen Knoten finden.

Um den Knoten mit den meisten verbundenen Kanten zu finden, können Sie alle Knoten durchlaufen und den Knoten mit den meisten verbundenen Kanten finden. Wenn Sie diese Operation häufig wiederholen müssen, können Sie einen Zeiger auf den Knoten mit den meisten Kanten halten und ihn einfach überprüfen und möglicherweise durch einen neuen Knoten ersetzen, wenn Sie zusätzliche Kanten verbinden oder einen neuen Knoten hinzufügen.

Überprüfen Sie die Wikipedia-Seite für weitere Informationen: https://en.wikipedia.org/wiki/Adjacency_list

Answer 2

Ich glaube, Sie fragen nach, wie, wie viele Kanten ein Knoten. Dies ist als Grad eines Knotens bekannt.

G.degree(node) gibt Ihnen den Grad des Knotens und G.degree() ist ein Diktat, dessen Schlüssel die Knoten sind und deren Werte die entsprechenden Grad sind.

Also ist ein einfacher Einzeiler, der (Knoten, Grad) für den Knoten mit maximalem Grad zurückgibt. Hier

ein Beispiel:

G = nx.Graph() 
G.add_edges_from([[1,2],[1,3],[2,4],[2,5]]) 
G.degree() 
> {1: 2, 2: 3, 3: 1, 4: 1, 5: 1} 
max(G.degree().items(), key = lambda x: x[1]) 
> (2,3)