当前位置 博文首页 > Sawakita1122的博客：Python生成依赖性应用的DAG(有向无环图)拓
因为研究方向设计到依赖性的应用，做实验需要用到一些随机的DAG(有向无环图)拓扑来作为应用的表示，找了找网上没有符合的代码，于是决定自己写个小脚本来生成大量随机的DAG拓扑。
我实验中要用到的依赖性应用拓扑类似于下面这种模式：
观察到，DAG包括一个入口节点和一个出口节点，其余的节点都是具有依赖关系的中继节点
图中入口节点的入度和出口节点的出度都为0，其余任意节点都至少有一条入边和一条出边。
根据有向无环图的性质，每一个有向无环图中的所有节点能形成有限个拓扑序，拓扑序中的节点只能向后序的节点出边（即一条依赖边中的父节点在拓扑序中的顺序一定位于子节点前面）。那么给定一个拓扑序，只要通过按顺序遍历，以一定概率随机向后加边的形式，就能生成一个DAG。
根据我所需要应用的场景，拓扑图比较“窄”，因此我将除入口和出口之外中间节点的入度和出度都限制在2以内(也可以根据自己对形状的需求来调整参数)。
因为对遍历中的每对节点对，脚本都以一定概率加边或不加边，因此会出现没有出边或没有入边的中间节点。对没有入边的节点，添加一条入口节点到它的边，同理对没有出边的节点，添加一条它到出口节点的边。
在实际运行过程中发现，如果入口到出口节点有直连的边，形成的拓扑图会比较绕，因此脚本不会生成直连入口到出口的边。
最终代码如下：
import random
n = 8#节点数量
def prob_value(p):#一个按概率连边的函数
q = int(10*p)
l = [1]*q+[0]*(10-q)
item = random.sample(l,1)[0]
return item
into_degree = [0]*n#节点入度列表
out_degree = [0]*n#节点出度列表
edges = []#存储边的列表
#拓扑序就按[1,n]的顺序，依次遍历加边
for i in range(n-1):
for j in range(i+1,n):
if i==0 and j==n-1:#不直连入口和出口
continue
prob = prob_value(0.4)#连边的概率取0.4
if prob:
if out_degree[i]<2 and into_degree[j]<2:#限制节点的入度和出度不大于2
edges.append((i,j))#连边
into_degree[j]+=1
out_degree[i]+=1
for node,id in enumerate(into_degree):#给所有没有入边的节点添加入口节点作父亲
if node!=0:
if id ==0:
edges.append((0,node))
out_degree[0]+=1
into_degree[node]+=1
for node,od in enumerate(out_degree):#给所有没有出边的节点添加出口节点作儿子
if node!=n-1:
if od ==0:
edges.append((node,n-1))
out_degree[node]+=1
into_degree[n-1]+=1
print(edges)
print(into_degree,out_degree)
程序输出：
在给定参数下，最终形成的拓扑大概是这样的：
基本符合我实验中的需求。
