Graphing The Dag Generated by Make

Generating a directed acyclic graph from predefined elements with connection requirements

It sounds like an L-system (aka Lindenmayer system) approach would work:

  • Your collection of Legos is analogous to an alphabet of symbols
  • Your connection rules correspond to a collection of production rules that expand each symbol into some larger string of symbols
  • Your starting Lego represents the the initial "axiom" string from which to begin construction
  • The resulting geometric structures is your DAG

The simplest approach would be something like: given a Lego, randomly select a valid connection rule & add a new Lego to the DAG. From there you could add in more complexity as needed. If you need to skew the random selection to favor certain rules, you're essentially building a stochastic grammar. If the selection of a rule depends on previously generated parts of the DAG it's a type of context sensitive grammar.

Graph rewriting, algorithmically creating a new graph out of base graph, might be a more literal solution, but I personally find that L-systems easier to internalize & that researching them yields results that are not overly academic/theoretical in nature.

L-systems themselves are a category of formal grammars. It might be worth checking into some of those related ideas, but it's pretty easy (for me at least) to get side tracked by theoretical stuff at the expense of core development.

Generating a random DAG

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

Reduce the complexity of the algorithm to construct a directed graph (DAG) from an undirected graph that satisfies the given constraints

Quick Answer

Actually you can split the vertices into groups in terms of distances to "F", and then check the neighborhood between nodes from two adjacent groups to add the edges.



Idea Behind

With respect to the distances to "F", the idea comes from the facts that:

  1. If a node is with distance d, then its parent(s) must be with distance d+1.
  2. If X is with distance d+1, then the nodes with distance d must be the children of X if and only if they are neighbors of X.


My Attempt

D <- distances(g)
d <- distances(g, "F")
lst <- split(colnames(d), d)
lst <- lst[order(as.integer(names(lst)))]
res <- c()
for (k in head(seq_along(lst), -1)) {
pre <- lst[[k]]
nxt <- lst[[k + 1]]
for (p in pre) {
dp <- D[p, nxt, drop = FALSE]
if (any(dp == 1)) {
res[[length(res) + 1]] <- data.frame(
from = colnames(dp)[dp == 1],
to = p
)
}
}
}
dag <- graph_from_data_frame(do.call(rbind, res))

then

plot(dag)

gives

Sample Image

Can you make Nextflow DAG visualisation beautiful?

Use DOT format output and Graphviz

tl;dr: Use the -with-dag flag without a filename and use Graphviz to render the resulting dag.dot file.

Graphvis is a software package built specifically for visualizing these sorts of graphs. Nextflow's DAG visualization option will output a DOT format representation by default. Instead of specifying -with-dag flowchart.png use the naked flag -with-dag to emit dag.dot or specify the filename of your choice with the .dot extension. Rendering a dot file to a visualization is the subject of other questions and documentation.

Printing simplified DAG plot with snakemake

Use the flag --rulegraph instead of --dag.



Related Topics



Leave a reply



Submit