生成随机 DAG

2021-12-24 00:00:00 algorithm graph c c++ cycle

我正在解决一个关于有向无环图的问题.

I am solving a problem on directed acyclic graph.

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

But I am having trouble testing my code on some directed acyclic graphs. The test graphs should be large, and (obviously) acyclic.

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

I tried a lot to write code for generating acyclic directed graphs. But I failed every time.

是否有一些现有的方法可以生成我可以使用的无环有向图?

Is there some existing method to generate acyclic directed graphs I could use?

推荐答案

我编写了一个执行此操作的 C 程序.关键是对节点进行排名"，并且只从排名较低的节点到排名较高的节点绘制边.

I cooked up a C program that does this. The key is to 'rank' the nodes, and only draw edges from lower ranked nodes to higher ranked ones.

我用DOT语言编写的程序.

这是代码本身，注释解释了它的含义:

Here is the code itself, with comments explaining what it means:

#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 {
");
  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;
", j, k + nodes); /* An Edge.  */

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

这是从测试运行中生成的图表:

And here is the graph generated from a test run:

相关文章