我正在解决有向无环图上的问题。
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语言中。
The program I wrote prints in the DOT language.
此处是代码本身,并带有注释,解释其含义:
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 {\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; }这是从测试运行生成的图形:
And here is the graph generated from a test run:
更多推荐
生成随机DAG
发布评论