Function random_DAG

numpy_ml/utils/graphs.py:336–363

Create a 'random' unweighted directed acyclic graph by pruning all the backward connections from a random graph. Parameters ---------- n_vertices : int The number of vertices in the graph. edge_prob : float in [0, 1] The probability of forming an edge betwee

(n_vertices, edge_prob=0.5)

def random_DAG(n_vertices, edge_prob=0.5):
    """
    Create a 'random' unweighted directed acyclic graph by pruning all the
    backward connections from a random graph.

    Parameters
    ----------
    n_vertices : int
        The number of vertices in the graph.
    edge_prob : float in [0, 1]
        The probability of forming an edge between two vertices in the
        underlying random graph, before edge pruning. Default is 0.5.

    Returns
    -------
    G : :class:`Graph` instance
        The resulting DAG.
    """
    G = random_unweighted_graph(n_vertices, edge_prob, directed=True)

    # prune edges to remove backwards connections between vertices
    G = DiGraph(G.vertices, [e for e in G.edges if e.fr < e.to])

    # if we pruned away all the edges, generate a new graph
    while not len(G.edges):
        G = random_unweighted_graph(n_vertices, edge_prob, directed=True)
        G = DiGraph(G.vertices, [e for e in G.edges if e.fr < e.to])
    return G