[Network X] 教學入門

轉載自 這裡 
前言 : 
NetworkX is a Python language software package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks. It provides features as below (下載 Packages) : 

* Python language data structures for graphs, digraphs, and multigraphs.
* Nodes can be "anything" (e.g. text, images, XML records)
* Edges can hold arbitrary data (e.g. weights, time-series)
* Generators for classic graphs, random graphs, and synthetic networks
* Standard graph algorithms
* Network structure and analysis measures
* Basic graph drawing
* Open source BSD license
* Well tested: more than 1500 unit tests
* Additional benefits from Python: fast prototyping, easy to teach, multi-platform

建立 graph : 
底下代碼建立一個空 graph (沒有 node, edge) : 

>>> import networkx as nx
>>> G=nx.Graph()

By definition, a Graph is a collection of nodes (vertices) along with identified pairs of nodes (called edges, links, etc). In NetworkX, nodes can be any hashable object e.g. a text string, an image, an XML object, another Graph, a customized node object, etc. (Note: Python’s None object should not be used as a node as it determines whether optional function arguments have been assigned in many functions.) 

Nodes : 
The graph G can be grown in several ways. NetworkX includes many graph generator functions and facilities to read and write graphs in many formats. To get started though we’ll look at simple manipulations. You can add one node at a time : 

>>> G.add_node(1)

add a list of nodes : 

>>> G.add_nodes_from([2, 3])

or add any nbunch of nodes. An nbunch is any iterable container of nodes that is not itself a node in the graph. (e.g. a list, set, graph, file, etc..) 

>>> H = nx.path_graph(10)
>>> G.add_nodes_from(H)

Note that G now contains the nodes of H as nodes of G. In contrast, you could use the graph H as a node in G : 

>>> G.add_node(H)

The graph G now contains H as a node. This flexibility is very powerful as it allows graphs of graphs, graphs of files, graphs of functions and much more. It is worth thinking about how to structure your application so that the nodes are useful entities. Of course you can always use a unique identifier in G and have a separate dictionary keyed by identifier to the node information if you prefer. (Note: You should not change the node object if the hash depends on its contents.) 

Edges : 
Graph 可以如下一次添加一個 edge : 

>>> import networkx as nx
>>> G = nx.Graph()
>>> G.add_edge(1, 2)
>>> e=(2, 3)
>>> G.add_edge(*e) # unpack edge tuple*
>>> G.edge
{1: {2: {}}, 2: {1: {}, 3: {}}, 3: {2: {}}}

或是如下一次添加多個 edges : 

>>> G.add_edges_from([(4, 5), (4, 2)])
>>> G.edge[4]
{2: {}, 5: {}} # edge 4 與 node 2, 5 相接

另外你也可以透過 ebunch 的方式添加 edges. 在使用 tuple 表示 edge 時, 可以在 tuple 第三個位置上擺放該 edge 的屬性, 如 (2,3,{‘weight’:3.1415}). 底下為使用 ebunch 添加 edges : 

>>> H = nx.path_graph(5)
>>> G.add_edges_from(H.edges())

如果你要移除 edges/nodes, 可以使用方法 : Graph.remove_node(), Graph.remove_nodes_from(), Graph.remove_edge() and Graph.remove_edges_from(), e.g 

>>> G.add_node("spam")
>>> G.remove_node("spam")

如果你要移除所有的 node/edge, 則可以 : 

>>> G.clear()

如果你添加重複的 node/edge 不會出現 Exception, 你可以透過方法知道目前 Graph 共有幾個 edge/node : 

>>> G.add_edges_from([(1, 2), (1, 3)])
>>> G.add_node(1)
>>> G.add_edge(1, 2)
>>> G.add_node("spam")
>>> G.add_nodes_from("spam") # adds 4 nodes: 's', 'p', 'a', 'm'
>>> G.number_of_nodes()
8
>>> G.number_of_edges()
2

底下是 Graph 部分提供方法的使用 : 

>>> G.nodes()
['a', 1, 2, 3, 'spam', 'm', 'p', 's']
>>> G.edges()
[(1, 2), (1, 3)]
>>> G.neighbors(1)
[2, 3]

底下是一些移除 node/edge 的使用示範 : 

>>> G.remove_nodes_from("spam")
>>> G.nodes()
[1, 2, 3, 'spam']
>>> G.remove_edge(1, 3)
>>> G.edges()
[(1, 2)]

Accessing edges : 
你可以將 Graph 當作 list 去 access 裡面的 nodes, edges (但千萬別修改返回的內容, 會造成 Graph inconsistent) : 

>>> G[1] # Access node-1
{2: {}}
>>> G[1][2] # Access edge(1, 2)
{}

你可以使用 dict 的方法去為 node/edge 添加屬性 : 

>>> G.add_edge(1, 3)
>>> G[1][3]['color'] = 'blue'
>>> G[1]
{2: {}, 3: {'color': 'blue'}} #在 edge(1,3) 有屬性 color='blue'

除了使用上面方法去操作 node/edge, 你也可以透過方法 adjacency_iter() 來拜訪某個 Graph 的所有 node : 
 

Adding attributes to graphs, nodes, and edges : 
你可以在 Graph 中的 edge/node 甚至是 Graph 本身添加屬性, 而屬性可以是任何物件. 屬性則以 dict 的形式存放在. 

- Graph attributes 
底下為新增的 Graph 添加/修改屬性 : 

>>> G = nx.Graph(day='Friday')
>>> G.graph
{'day': 'Friday'}
>>> G.graph['day']
'Friday'
>>> G.graph['day'] = 'Monday'
>>> G.graph
{'day': 'Monday'}

- Node attributes 
底下示範如何對 node 的屬性進行操作 : 

>>> G.add_node(1, time='5pm')
>>> G.add_nodes_from([3, 4], time='1pm')
>>> G.node[1]['room'] = 714
>>> G.nodes(data=True)
[(1, {'room': 714, 'time': '5pm'}), (3, {'time': '1pm'}), (4, {'time': '1pm'})]

Ps. 如果你手動添加 node 到 G.node, 並不會添加到 Graph, 所以請用方法 G.add_node() etc 進行 node 的添加. 

- Edge Attributes 
底下示範對 edge 的屬性進行操作 : 

>>> G.add_edge(1, 2, weight=4.7)
>>> G.add_edges_from([(3,4), (4,5)], color='red')
>>> G.add_edges_from([(1,2,{'color':'blue'}), (2,3,{'weight':8})])
>>> G[1][2]['weight']
4.7
>>> G.edge[1][2]['color']
'blue'

Directed graphs : 
透過類別 DiGraph 可以達成有方向性的 Graph 相關操作. 相關方法如 DiGraph.out_edges(), DiGraph.in_degree(), DiGraph.predecessors() 與 DiGraph.successors() 等. 底下我們來看看簡單使用操作 : 

>>> DG = nx.DiGraph()
>>> DG.add_weighted_edges_from([(1,2,0.5), (3,1,0.75)])
>>> DG.out_degree(1, weight='weight')
0.5
>>> DG.degree(1, weight='weight') # 求 node1 的分支上屬性 weight 的合
1.25
>>> DG.add_edge(1, 4, weight=0.8)
>>> DG.edges()
[(1, 2), (1, 4), (3, 1)]
>>> DG.degree(1) # node1 的分支為3. in_degree=1, out_degree=2
3
>>> DG.out_degree(1) # node1 上往外分支為 2 (1->2, 1->4)
2
>>> DG.successors(1)
[2, 4]
>>> DG.neighbors(1)
[2, 4]

另外如果你要將有向 Graph 轉為無方向的 Graph, 可以如下操作 : 

>>> DG = nx.DiGraph()
>>> DG.add_weighted_edges_from([(1,2,0.5), (3,1,0.75), (2,1,1)])
>>> DG.edges()
[(1, 2), (2, 1), (3, 1)]
>>> DG.nodes()
[1, 2, 3]
>>> H = nx.Graph(DG) # H 為無方向的 Graph
>>> H.edges()
[(1, 2), (1, 3)] # edge(2,1) 被移除了!

Multigraphs : 
如果你的 Graph 兩點間的 edge 是沒有數量限制的, 則可以考慮使用 MultiGraph 與 MultiDiGraph. 底下是現有 NetworkX 支援 Graph 的分類 : 
 

接著來看看使用範例 : 
 

Drawing graphs : 
NetworkX 提供繪圖的 APIs, 詳細使用可以參考 Drawing. 但在使用這些繪圖 APIs 前, 你必須安裝另外的 library 為 Matplotlib (Matplotlib 安裝說明請參考 這裡). 底下我們來看簡單範例 : 
首先匯入 Matplotlib 的 plot 介面 : 

>>> import matplotlib.pyplot as plt

接著透過 NetworkX 的 draw() 函式呼叫 Matplotlib 繪圖 : 
 

或者你可以另存繪圖結果為圖片檔 : 

>>> nx.draw(G)
>>> plt.savefig("path.png")

Practice in Algorithm implementation : 
透過 NetworkX 的幫助, 我們便可以很輕鬆地寫出圖形理論相關的演算法, 底下代碼為實現 DFS (Deep First Search) 節點訪問的演算法 : 
- 範例圖形 : 
 

- 範例代碼 : 

view plaincopy to clipboardprint?

1. import networkx as nx  
2.   
3. G = nx.Graph()  
4. G.add_edges_from([(1,5), (1,2), (2,3), (2,4), (3,4), (3,5), (4,5), (5,3)])  
5. stack = [1]  # Start from node1  
6. visit_list = []  
7.   
8. while len(stack) > 0:  
9.     #nonlocal visit_list  
10.     #nonlocal stack  
11.     vnode = stack.pop()  
12.     if vnode not in visit_list:  
13.         print("\t[Info] Visit {0}...".format(vnode))  
14.         visit_list.append(vnode)  
15.     nbs = G.neighbors(vnode)  
16.     for nb in nbs:  
17.         if nb not in visit_list:  
18.             print("\t[Info] Put {0} in stack...".format(nb))  
19.             stack.append(nb)  
20.     print("\tStack list={0}".format(stack))  
21.     print("\tVisit list={0}".format(visit_list))  
22.     if len(visit_list) == len(G.nodes()): break  
23.   
24. print("\t[Info] Deep First Search has {0}".format(visit_list))  

- 執行結果 : 
 

Supplement : 
* matplotlib : A python 2D plotting library 

matplotlib is a python 2D plotting library which produces publication quality figures in a variety of hardcopy formats and interactive environments across platforms. matplotlib can be used in python scripts, the python and ipython shell (ala MATLAB®* or Mathematica®†), web application servers, and six graphical user interface toolkits.

* stackoverflow : generating a PNG with matplotlib when DISPLAY is undefined