如何找到圖中給定的輸入頂點和邊度序列？

Question

vertice = input("enter the vertices: ") 
vertice = [x.strip(' ') for x in vertice.split(',')] 

edge = input("enter the edges: ") 
edge = [x.strip(' ') for x in edge.split(',')] 

print("Number of vertices: ", len(vertice)) 
print("Number of edges: ", len(edge) 

在這裏，我想找到像給出的輸入程度序列： A，B，C爲頂點 和A-B，B-C，C-A的邊緣。我如何用這種類型的輸入來做到這一點？ 尋找像[2,2,2]

Answer 1

的輸出可以使用Counter計數相關聯的每個頂點的邊緣：

>>> from collections import Counter 
>>> vertices = ['a', 'b', 'c', 'd'] 
>>> edges = ['a-b', 'a-c', 'b-c', 'd-a'] 
>>> degree = Counter(vertex for edge in edges for vertex in edge.split('-')) 
>>> [degree[vertex] for vertex in vertices] 
[3, 2, 2, 1] 

在上述Counter構造函數接受中的項目可迭代，並返回一個dict狀物體這裏獨特的項是鍵和值分別計數。

>>> items = list(vertex for edge in edges for vertex in edge.split('-')) 
>>> items 
['a', 'b', 'a', 'c', 'b', 'c', 'd', 'a'] 
>>> degree = Counter(items) 
>>> degree 
Counter({'a': 3, 'c': 2, 'b': 2, 'd': 1}) 

由於Counter的順序是隨機的，我們需要使用列表中理解到頂點迭代，以產生在同一順序的度列表。

>>> [degree[vertex] for vertex in vertices] 
[3, 2, 2, 1] 

Answer 2

您可以隨時使用networkx軟件包 - 該軟件包爲您提供了大部分（如果不是全部）您希望操作圖形的功能，假設你有一個徑向連接的4個節點的路徑，你會發現這樣的程度：

from networkx import nx 
G = nx.Graph() 
G.add_path([0,1,2,3]) 
deg=G.degree(G.nodes()).values() 
print("number of vertices: ",G.number_of_nodes()) 
print("number of edges: ",G.number_of_edges()) 
print("degree list: ",sorted(deg)) 

>>number of vertices: 4 
>>number of edges: 3 
>>degree list: [1, 1, 2, 2]