快捷導(dǎo)航

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

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

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

問題描述

我自己根據(jù)edgelist計(jì)算的鄰接矩陣，與調(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()可累計(jì)多條重復(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())

實(shí)際運(yùn)行輸出

[[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é)點(diǎn)id從0開始。對(duì)于邊(1,3)，矩陣的第二行第四列應(yīng)當(dāng)為權(quán)重3，可以看到實(shí)際運(yùn)行輸出結(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)

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

所以我查看了我傳進(jìn)去的圖g的節(jié)點(diǎn)默認(rèn)順序是什么樣的：

edgelist = [
        (0, 1),
        (1, 3),
        (2, 4),
        (1, 5),
        (1, 3),
        (5, 5),
        (1, 3)
    ]
"""由于nx.MultiGraph()可累計(jì)多條重復(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())

運(yùn)行結(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é)點(diǎn)列表居然不是按照從小到大的順序排列，id為3的節(jié)點(diǎn)居然是第三而不是第四位序，這就是為什么邊(1,3)的權(quán)重會(huì)寫在矩陣的第三列…因?yàn)榫仃嚨谌袑?duì)應(yīng)節(jié)點(diǎn)3！

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

因?yàn)椋杭有逻卻dd_edges的時(shí)候會(huì)自動(dòng)加新節(jié)點(diǎn)?。?！

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

解決方案

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

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

修改后的代碼

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

""" 節(jié)點(diǎn)id按照順序排?。》駝t生成的鄰接矩陣不一樣 """
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())

修改代碼后的運(yùn)行結(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中的每個(gè)(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中的元素是無序、非空、唯一的，所以對(duì)set再sorted一下，確保順序是對(duì)的 """
nodeset = sorted(nodeset)
print(nodeset)
# 輸出：
# [0, 1, 2, 3, 4, 5]