Search code examples
c++calgorithmgraphcycle

Generating a random DAG


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?


Solution

  • 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.

    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:

    A randomly generated DAG