日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

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

作者：小豬上吊ing ? 更新時間： 2023-01-15 編程語言

問題描述

我自己根據edgelist計算的鄰接矩陣，與調用networkx.adjacency_matrix(g)返回的結果不一樣，經過調試發現了問題原因以及解決辦法，記錄如下。

原來的代碼

edgelist = [
        (0, 1),
        (1, 3),
        (2, 4),
        (1, 5),
        (1, 3),
        (5, 5),
        (1, 3)
    ]
"""由于nx.MultiGraph()可累計多條重復邊作為權重，所以(1,3)出現3次權重是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]]

理論結果

[[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]]

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

調試過程

查看了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)

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

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

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

運行結果居然：

[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的節點列表居然不是按照從小到大的順序排列，id為3的節點居然是第三而不是第四位序，這就是為什么邊(1,3)的權重會寫在矩陣的第三列…因為矩陣第三列對應節點3！

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

因為：加新邊sdd_edges的時候會自動加新節點！！！

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

解決方案

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

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

修改后的代碼

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

""" 節點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())

修改代碼后的運行結果

[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]]

函數說明

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元素唯一的性質，將重復元素去重 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]

總結

原文鏈接：https://blog.csdn.net/yingluo54/article/details/113325108

欄目分類
最近更新