生成随机DAG

Question

我正在解决有向无环图上的问题.

但是我在一些有向无环图上测试我的代码时遇到了麻烦.测试图应该很大,并且(显然)是非循环的.

我尝试了很多代码来编写用于生成非循环有向图的代码.但我每次都失败了.

是否有一些现有的方法来生成我可以使用的非循环有向图？

Answer 1

我做了一个C程序来做到这一点.关键是对节点进行"排名",并且只将较低排名节点的边缘绘制到排名较高的节点.

我写的程序用DOT语言打印.

这是代码本身,其中的注释解释了它的含义:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MIN_PER_RANK 1 /* Nodes/Rank: How 'fat' the DAG should be.  */
#define MAX_PER_RANK 5
#define MIN_RANKS 3    /* Ranks: How 'tall' the DAG should be.  */
#define MAX_RANKS 5
#define PERCENT 30     /* Chance of having an Edge.  */

int main (void)
{
  int i, j, k,nodes = 0;
  srand (time (NULL));

  int ranks = MIN_RANKS
              + (rand () % (MAX_RANKS - MIN_RANKS + 1));

  printf ("digraph {\n");
  for (i = 0; i < ranks; i++)
    {
      /* New nodes of 'higher' rank than all nodes generated till now.  */
      int new_nodes = MIN_PER_RANK
                      + (rand () % (MAX_PER_RANK - MIN_PER_RANK + 1));

      /* Edges from old nodes ('nodes') to new ones ('new_nodes').  */
      for (j = 0; j < nodes; j++)
        for (k = 0; k < new_nodes; k++)
          if ( (rand () % 100) < PERCENT)
            printf ("  %d -> %d;\n", j, k + nodes); /* An Edge.  */

      nodes += new_nodes; /* Accumulate into old node set.  */
    }
  printf ("}\n");
  return 0;
}

以下是测试运行生成的图表:

Answer 2

https://mathematica.stackexchange.com/questions/608/how-to-generate-random-directed-acyclic-graphs的答案适用:如果你有一个图的边缘的邻接矩阵表示,那么矩阵是低三角形,必要时它是DAG.

类似的方法是对节点进行任意排序,然后仅在x <y时考虑从节点x到y的边.这种约束也应该通过构造得到你的DAGness.如果您使用结构来表示节点,则内存比较将是订购节点的一种任意方式.

基本上,伪代码将是这样的:

for(i = 0; i < N; i++) {
    for (j = i+1; j < N; j++) {
        maybePutAnEdgeBetween(i, j);
    }
}

其中N是图表中的节点数.

伪代码表明给定N个节点的潜在DAG数量是

2^(n*(n-1)/2),

既然有

n*(n-1)/2

有序对("N选择2"),我们可以选择是否具有它们之间的边缘.