给定节点和边的数量，随机生成有向无环图(DAG)

方法1（暴力方法）
假设需要生成一个n个节点，m条边的DAG，那我们可以先生成一个的，元素均为0的矩阵，从个位置中，随机抽取m个位置等于1，这样就构造出了一个图的邻接矩阵。随后，我们再分别写两个程序，一个用来验证该图是否联通，随后用另一个程序判断该图是否是DAG（这两个程序可以见我之前的博客）。暴力方法很好理解，但是生成图的效率非常低。经过我的尝试，在的时候，生成图的效果就会低的令人发指。

方法2（拓扑排序 + 有条件生成边）
我们知道，只有DAG才存在拓扑排序。所以我们可以利用拓扑排序的逆过程生成DAG。即，先生成任意一个拓扑排序序列，再任意连接m条边（left node在拓扑排序序列中的顺序要在right node之前）。这样我们可以保证，生成的图一定是无环的。
但问题随之而来，通过这种方法生成的图很可能未联通。比如：我们生成一个6个节点，5条边的DAG，可能我们生成了一个5个节点，5条边的DAG，有一个节点和任何其他节点都不连接。为了解决这个问题，我们对前n-1条边的生成做一些限制（确定为n-1的原因是，对于n个节点，最少需要n-1条边将他们连接起来）:从第二次生成边开始，必须选择一个已经出现的节点和一个未出现过的节点。这样我们先生成了一个n个节点n-1条边的DAG，对于剩下的m - n + 1条边可以继续按照上一段的方法生成，同时要保证这条边之前没有生成过，避免出现重复的边，代码展示如下：

import numpy as np
from random import shuffle as sl  
from random import randint as rd    
 #node节点数量，edge边数量 
def random_graph(node,edge):

    n = node
    node = range(0,n)   
    node = list(node)  
    
    sl(node)  #生成拓扑排序
    m = edge
    result = [] #存储生成的边，边用tuple的形式存储
    
    appeared_node = []
    not_appeared_node = node
    #生成前n - 1条边  
    while len(result) != n - 1:
  #生成第一条边
        if len(result) == 0:
            p1 = rd(0,n - 2)
            p2 = rd(p1+1,n - 1)
            x = node[p1]
            y = node[p2]
            appeared_node.append(x)
            appeared_node.append(y)
            not_appeared_node = list(set(node).difference(set(appeared_node)))
            result.append((x,y))
  #生成后面的边
        else:
            p1 = rd(0,len(appeared_node) - 1)
            x = appeared_node[p1]#第一个点从已经出现的点中选择
            p2 = rd(0,len(not_appeared_node) - 1)
            y = not_appeared_node[p2]
            appeared_node.append(y)#第二个点从没有出现的点中选择
            not_appeared_node = list(set(node).difference(set(appeared_node)))
     #必须保证第一个点的排序在第二个点之前
            if node.index(y) < node.index(x):
                result.append((y,x))
            else:
                result.append((x,y))
   #生成后m - n + 1条边     
    while len(result) != m:
        p1 = rd(0,n - 2)
        p2 = rd(p1+1,n - 1)
        x = node[p1]
        y = node[p2]
    #如果该条边已经生成过，则重新生成
        if (x,y) in result:
            continue
        else:
            result.append((x,y))
    
    matrix = np.zeros((n,n))
    for i in range(len(result)):
        matrix[result[i][0],result[i][1]] = 1

    return matrix

测试程序1

G1 = random_graph(5,4)

test1.png

结果：

result1.png

测试程序2:为了验证程序的效率，这次我们选择生成20个节点，19条边的DAG

class Graph(object):
    def __init__(self,G):
      self.G = G
      self.color = [0] * len(G)
      self.isDAG = True
           
    def DFS(self,i):
        self.color[i] = 1
        for j in range(len(self.G)):
            if self.G[i][j] != 0:
                if self.color[j] == 1:
                    self.isDAG = False
                elif self.color[j] == -1:
                    continue
                else:
                    #print('We are visiting node' + str(j + 1))
                    self.DFS(j)
        self.color[i] = -1
    #利用深度优先搜索判断一个图是否为DAG
    def DAG(self):
        for i in range(len(self.G)):
            if self.color[i] == 0:
                self.DFS(i)

G = random_graph(20,19)
G = Graph(G)
G.DAG()

test2.png