How can I create random DAG graphs, where nodes has only single direction, in Python

Question

I want to generate random DAGs, where all node connections be only single direction.

I have tried following solution How can I create random single source random acyclic directed graphs with negative edge weights in python, which is able to generate random DAGs but node connections can be two way.

Answer 1

What you want is a directed graph without cycles.

My favorite Python package for directed graphs is networkx.

Here is a example of random directed DAG generation:

import networkx as nx
import matplotlib.pyplot as plt
import random

def generate_random_dag(num_nodes, num_edges):
    G = nx.DiGraph()
    while G.number_of_edges() < num_edges:
        G.add_edge(*random.sample(range(num_nodes), 2))
        if not nx.is_directed_acyclic_graph(G):
            G.remove_edges_from(list(nx.find_cycle(G, orientation='original')))
    return G

G = generate_random_dag(10, 15)

nx.draw(G, with_labels=True)
plt.show() 

Note the use of the class DiGraph (Di for directed), instead of Graph or other options.

Giving you this output:

Following-up here with the question from comments: in essence, can we enforce a specific node (like #0) to be the initial node?

Here is the modified code to do that (for node 0 in this example but number can easily be changed to any other node):

def generate_random_dag(num_nodes, num_edges):
    G = nx.DiGraph()
    while G.number_of_edges() < num_edges:
        start_node, end_node = random.sample(range(num_nodes), 2)
        # ensure that node 0 is always a source (initial node)
        if end_node == 0:  
            start_node, end_node = end_node, start_node
        G.add_edge(start_node, end_node)
        if not nx.is_directed_acyclic_graph(G):
            G.remove_edge(start_node, end_node)
    return G

G = generate_random_dag(10, 15)
nx.draw(G, with_labels=True)
plt.show()

which gives you the following output graph (note that node 0 does not have any incoming edges, as expected):

Following-up with the second question from the comments: can we enforce a specific node (like #0) to be the initial node AND make sure that the graph has a unique source node?

Here is the modified code to do that:

def generate_random_dag(num_nodes, num_edges):
    G = nx.DiGraph()
    
    for node in range(1, num_nodes):
        G.add_edge(0, node)

    while G.number_of_edges() < num_edges:
        start_node, end_node = random.sample(range(num_nodes), 2)
        # only node 0 as source, no other sources
        if end_node == 0 or start_node == 0:  
            continue
        G.add_edge(start_node, end_node)
        if not nx.is_directed_acyclic_graph(G):
            G.remove_edge(start_node, end_node)
    return G

G = generate_random_dag(10, 15)
nx.draw(G, with_labels=True)
plt.show()

And the resulting graph output: