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:
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:
- If a node is with distance
d
, then its parent(s) must be with distanced+1
. - If
X
is with distanced+1
, then the nodes with distanced
must be the children ofX
if and only if they are neighbors ofX
.
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
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
"Must Be Connected to a Terminal Error" with Screen -X Command on a Linux Container
Uses for This Bash Filename Extraction Technique
Git: Can't Push (Strange Config Issue)
Shared Volume in Docker Through Vagrant
Starting Ddd with Remote Gdbserver
Apache Cgi in User Directory "End of Script Output Before Headers"
Executing Exe or Bat File on Remote Windows Machine from *Nix
How to Find The Memory Consumption of a Particular Process in Linux for Every 5 Seconds
How to Take Advantage of The Vdso Object with Your Own Programming Language
Sudo Apt-Get Update Fail on Ubuntu 17.04
Kvm Shadow Page Table Handling in X86 Platform
How to Execute Shell Builtin from Scala
Getting Following Error After The Command Sudo Apt-Get Update on Ubuntu 16.04
How to Add an Icon to The Bash Prompt
Expect, Interact and Then Again Expect
Different CPU Cache Size Reported by /Sys/Device/ and Dmidecode
Receiving Multicast on a Server with Multiple Interfaces (Linux)