我正在解决一个关于有向无环图的问题。
但我无法在一些有向无环图上测试我的代码。测试图应该很大,并且(显然)是非循环的。
我尝试了很多代码来生成无环有向图。但我每次都失败了。
是否有一些现有的方法可以生成我可以使用的无环有向图?
最佳答案
我编写了一个 C 程序来执行此操作。关键是对节点进行“排序”,仅从排名较低的节点向排名较高的节点绘制边。
我编写的程序打印在 the DOT language .
这是代码本身,注释解释了它的含义:
#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;
}
这是从测试运行生成的图表:
关于c++ - 生成随机 DAG,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12790337/