Fate

利用networkx实现图的可视化(实现三种基础的图算法)

发表于 |

Markdown

前言：很久没更新博客了,想找点东西做做,找到一个不错的python数据分析包——networkx,这里就来用它实现最短路的可视化.

安装

  • 没有安装matplotlib的同学,先去安装对应的版本,我很早之前安装的,也忘记当时是怎么装的了(好像直接利用pip太大了?).

  • 然后安装networkx,运行命令pip install networkx,如果timeout多试几次或者直接去官网下载.

简单介绍

  • 网上有个很好的学习资源,如果想详细了解这个类可以去这里学习.我这里只做简单介绍.

  • 基本的添加点和边的方法

    1
    2
    3
    4
    5
    6
    7
    G = nx.DiGraph() #生成有向图
    G = nx.Graph() #生成无向图
    G.add_node(idx) #添加单个节点
    G.add_edge(u,v) #添加单条无权值得边
    G.add_edges_from([(u1,v1),(u2,v2),(u3,v3)]) #添加一个无权的边的集合
    G.remove_edge(u,v) #从图中移除边
    G.remove_node(idx) #从图中移除点

  • 四种基本的网络模型以及一种自定义网络模型,分别调用如下样式可以深层对应图形.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    #规则图
    pos = nx.spectral_layout(G)
    #ER随机图
    pos = nx.shell_layout(G)
    #WS小世界网络
    pos = nx.circular_layout(G)
    #BA无标度网络
    pos = nx.spring_layout(G)
    #自定义网络模型:可以规定node的坐标,点太多不适用,最适合二分图
    G.add_node(idx1,pos=(x1,y1))
    G.add_node(idx2,pos=(x2,y2))
    G.add_node(idx3,pos=(x3,y3))
    pos=nx.get_node_attributes(G,'pos')

  • 显示点和边

    1
    2
    3
    4
    5
    6
    7
    8
    9
    # 显示点:参数分别代表当前图对象,采用的网络模型,节点的大小,节点的颜色
    nx.draw_networkx_nodes(G,pos,node_size=200, node_color='orange')
    # 显示边:前两个参数同点,edgelist代表当前图中的特定边的集合,arrow代表是否显示边的方向,width代表边的宽度,edge_color代表边的颜色,alpha代表边的透明度(默认为1不透明),以及样式(dashed代表虚线,默认为实线)
    nx.draw_networkx_edges(G,pos,edgelist=e_origin, arrows=True,width=1, edge_color='g',alpha=1,style='dashed')
    #为图上的节点添加编号标签
    nx.draw_networkx_labels(G,pos,font_size=10,font_family=font)
    #为图里的边添加标签信息(前提是边有标签)
    nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)

  • 先介绍到这里,因为代码只需要这么多,因为networkx是支持matplotlib的,最后调用plt.show()就能显示图片了.

需要实现的三种算法

利用spfa算法构造最短路

  • networkx非常强大,提供最短路算法,但是为了满足需要,我还是自己实现了spfa算法.spfa算法我不详细叙述了,就是利用链式前向星求最短路的算法.这里的话我只说下我的基本思路.
  • 在spfa算法中用一个pre数组存当前节点的前一个节点的编号,以及用一个边编号数组存当前的两个节点中哪一条边被用了(考虑重边问题),节点的d值变了就更新这两个数组的数据;
  • 找完最短路后,然后通过反向寻找路径将用到的边存到一个集合,将之前的边删除掉.然后生成新的边(着两条边本质上是一样的),这样就可以将边分为两个集合(最短路中的边和原图中的边),然后就可以轻易的画出图形了.
    Markdown

    利用prim算法构造最小生成树

  • 这里我就用了邻接矩阵实现的prim算法,prim算法不做介绍.同样是用一个pre数组记录最小生成树中的边,这里的边可以在每次更新的权值的时候就找到.
  • 这个算法不复杂,大家可以扩展一下生成次小生成树.
    Markdown

利用匈牙利算法实现二分图的最大匹配

  • 二分图的最大匹配算法实质上也就是寻找增广路的过程,这其中有个linker数组,初始值为-1,当对每个点做完增广后,遍历linker数组,如果linker数组不为-1,则证明这个linker[v]和v形成了匹配.这条边最大匹配中的边.
  • 这个算法可以用链式前向星或者邻接矩阵实现.我这里用的链式前向星.
    Markdown

利用networkx生成图片

  • 这里的话所有的边都是在一个图里面的,怎么区分出来呢?我们发现边里面可以传一个**attr的关键字参数,所以我们可以为两种边设置不同的关键字weight来区分(当然设置别的属性也可以)
  • 我在这里封装了一个模板,按照要求设置好边的label和weight后生成图片.
  • show函数包含四个参数,G代表networkx生成的图对象,pos代表图的网络模型(默认ER随机图),title表示生成的图图里面所附带的title信息,photo_name代表保存的时候图的名称.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    #coding:utf-8
    import networkx as nx
    import matplotlib.pyplot as plt
    #此段代码解决 1.matplotlib中文显示问题 2 '-'显示为方块问题
    from pylab import *
    mpl.rcParams['font.sans-serif'] = ['SimHei']
    mpl.rcParams['axes.unicode_minus'] = False
    def show(G,pos,title=None,photo_name='picture'):
        e_1 =[(u,v) for (u,v,d) in G.edges(data=True) if d['weight'] ==1] # 普通边
        e_2 =[(u,v) for (u,v,d) in G.edges(data=True) if d['weight'] ==0] # 利用的边
        # Draw nodes
        nx.draw_networkx_nodes(G,pos,node_size=300, node_color='orange')
        # Draw Edges
        nx.draw_networkx_edges(G,pos,edgelist=e_1,width=1, alpha = 1,edge_color='g',style='dashed')
        nx.draw_networkx_edges(G,pos,edgelist=e_2, width=3,alpha=0.6,edge_color='b')
        edge_labels =dict([((u, v), d['label']) for u, v, d in G.edges(data=True)])
        nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
        nx.draw_networkx_labels(G,pos,font_size=10)
        plt.title(title)
        plt.axis('off')
        plt.savefig(photo_name)
        plt.show()

本文地址：https://yoghurt-lee.github.io/2017/03/30/graph-visible/
转载请注明出处，谢谢！

热评文章