快捷導(dǎo)航

nx.adjacency_matrix計算鄰接矩陣與真實結(jié)果不一致的解決

更新時間：2022年12月16日 09:20:46 作者：小豬上吊ing

這篇文章主要介紹了nx.adjacency_matrix計算鄰接矩陣與真實結(jié)果不一致的解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

問題描述

我自己根據(jù)edgelist計算的鄰接矩陣，與調(diào)用networkx.adjacency_matrix(g)返回的結(jié)果不一樣，經(jīng)過調(diào)試發(fā)現(xiàn)了問題原因以及解決辦法，記錄如下。

原來的代碼

edgelist = [
        (0, 1),
        (1, 3),
        (2, 4),
        (1, 5),
        (1, 3),
        (5, 5),
        (1, 3)
    ]
"""由于nx.MultiGraph()可累計多條重復(fù)邊作為權(quán)重，所以(1,3)出現(xiàn)3次權(quán)重是3"""
g = nx.MultiGraph()  # 無向多邊圖
g.add_edges_from(edgelist)
adj = sp.lil_matrix(nx.adjacency_matrix(g))
print(adj.todense())

實際運行輸出

[[0 1 0 0 0 0]
[1 0 3 0 0 1]
[0 3 0 0 0 0]
[0 0 0 0 1 0]
[0 0 0 1 0 0]
[0 1 0 0 0 1]]

理論結(jié)果

[[0 1 0 0 0 0]
[1 0 0 3 0 1]
[0 0 0 0 1 0]
[0 3 0 0 0 0]
[0 0 1 0 0 0]
[0 1 0 0 0 1]]

節(jié)點id從0開始。對于邊(1,3)，矩陣的第二行第四列應(yīng)當(dāng)為權(quán)重3，可以看到實際運行輸出結(jié)果中，3卻出現(xiàn)在了第二行第三列！

調(diào)試過程

查看了networkx.adjacency_matrix()的源代碼，其中有一條說明如下：

def adjacency_matrix(G, nodelist=None, weight='weight'):
    """Return adjacency matrix of G.

    Parameters
    ----------
    G : graph
       A NetworkX graph

    nodelist : list, optional
       The rows and columns are ordered according to the nodes in nodelist.
       If nodelist is None, then the ordering is produced by G.nodes().

    weight : string or None, optional (default='weight')
       The edge data key used to provide each value in the matrix.
       If None, then each edge has weight 1.
    				...
    				...
    """
    return nx.to_scipy_sparse_matrix(G, nodelist=nodelist, weight=weight)

第二個參數(shù)的說明需要格外注意！對于nodelist這個參數(shù)，說明是這樣的：鄰接矩陣的行和列的排序按照nodelist中節(jié)點順序來！如果不傳這個參數(shù)，默認是按照傳進來的圖G調(diào)用G.nodes()時返回的節(jié)點的順序！

所以我查看了我傳進去的圖g的節(jié)點默認順序是什么樣的：

edgelist = [
        (0, 1),
        (1, 3),
        (2, 4),
        (1, 5),
        (1, 3),
        (5, 5),
        (1, 3)
    ]
"""由于nx.MultiGraph()可累計多條重復(fù)邊作為權(quán)重，所以(1,3)出現(xiàn)3次權(quán)重是3"""
g = nx.MultiGraph()  # 無向多邊圖
g.add_edges_from(edgelist)
print(g.nodes())
adj = sp.lil_matrix(nx.adjacency_matrix(g))
print(adj.todense())

運行結(jié)果居然：

[0, 1, 3, 2, 4, 5]
[[0 1 0 0 0 0]
[1 0 3 0 0 1]
[0 3 0 0 0 0]
[0 0 0 0 1 0]
[0 0 0 1 0 0]
[0 1 0 0 0 1]]

圖g的節(jié)點列表居然不是按照從小到大的順序排列，id為3的節(jié)點居然是第三而不是第四位序，這就是為什么邊(1,3)的權(quán)重會寫在矩陣的第三列…因為矩陣第三列對應(yīng)節(jié)點3！

那…為什么圖g的節(jié)點列表不是排好序的，為什么是[0, 1, 3, 2, 4, 5]這個順序？

因為：加新邊sdd_edges的時候會自動加新節(jié)點?。?！

邊(0,1)加進去的時候，節(jié)點列表是[0,1]；加邊(1, 3)的時候，節(jié)點列表[0,1,3]；…。所以節(jié)點默認列表的順序，跟你加新邊時候哪個節(jié)點先出現(xiàn)有關(guān)系。

解決方案

那么在添加新邊之前，先把節(jié)點按id從小到大順序排好同意添加，就可以了。

具體就是：在g.add_edges_from(edgelist)操作之前，先把edgelist中的節(jié)點抽取出來按順序排好，用操作g.add_nodes_from()把節(jié)點統(tǒng)一添加進圖g中。修改后的代碼如下：

修改后的代碼

edgelist = [
        (0, 1),
        (1, 3),
        (2, 4),
        (1, 5),
        (1, 3),
        (5, 5),
        (1, 3)
    ]
"""由于nx.MultiGraph()可累計多條重復(fù)邊作為權(quán)重，所以(1,3)出現(xiàn)3次權(quán)重是3"""
g = nx.MultiGraph()  # 無向多邊圖

""" 節(jié)點id按照順序排??！否則生成的鄰接矩陣不一樣 """
nodeset = sorted(set(itertools.chain(*edgelist)))
g.add_nodes_from(nodeset)

g.add_edges_from(edgelist)
print(g.nodes())
adj = sp.lil_matrix(nx.adjacency_matrix(g))
print(adj.todense())

修改代碼后的運行結(jié)果

[0, 1, 2, 3, 4, 5]
[[0 1 0 0 0 0]
[1 0 0 3 0 1]
[0 0 0 0 1 0]
[0 3 0 0 0 0]
[0 0 1 0 0 0]
[0 1 0 0 0 1]]

函數(shù)說明

nodeset = sorted(set(itertools.chain(*edgelist)))這行的功能，是把edgelist中的元素展開，去重，按順序排序。分開演示就是：

edgelist = [
        (0, 1),
        (1, 3),
        (2, 4),
        (1, 5),
        (1, 3),
        (5, 5),
        (1, 3)
    ]
""" 把edgelist中的每個(a,b)元素打平成a,b """
nodes = list(itertools.chain(*edgelist))
print(nodes)
# 輸出：
# [0, 1, 1, 3, 2, 4, 1, 5, 1, 3, 5, 5, 1, 3]

""" 利用set元素唯一的性質(zhì)，將重復(fù)元素去重 a,a => a """
nodeset = set(nodes)
print(nodeset)
# 輸出：
# {0, 1, 2, 3, 4, 5}

""" set中的元素是無序、非空、唯一的，所以對set再sorted一下，確保順序是對的 """
nodeset = sorted(nodeset)
print(nodeset)
# 輸出：
# [0, 1, 2, 3, 4, 5]