开发者

nx.adjacency_matrix计算邻接矩阵与真实结果不一致的解决

开发者 https://www.devze.com 2022-12-17 09:16 出处:网络 作者: 小猪上吊ing
目录问题描述原来的代码实际运行输出理论结果调试过程解决方案修改后的代码修改代码后的运行结果函数说明总结问题描述
目录
  • 问题描述
    • 原来的代码
    • 实际运行输出
    • 理论结果
  • 调试过程
    • 解决方案
      • 修改后的代码
      • 修改代码后的运行结果
      • 函数说明
    • 总结

      问题描述

      我自己根据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,js 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中的节点抽取出来BpuchlxKB按顺序排好,用操作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]]

      函数说明

      android

      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(itertoolwww.devze.coms.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,android 4, 5]
      

      总结

      以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。

      0

      精彩评论

      暂无评论...
      验证码 换一张
      取 消

      关注公众号