how to create random single source random acyclic directed graphs with negative edge weights in python

Question

I want to do a execution time analysis of the bellman ford algorithm on a large number of graphs and in order to do that I need to generate a large number of random DAGS with the possibility of having negative edge weights.

I am using networkx in python. There are a lot of random graph generators in the networkx library but what will be the one that will return the directed graph with edge weights and the source vertex.

I am using networkx.generators.directed.gnc_graph() but that does not quite guarantee to return only a single source vertex.

Is there a way to do this with or even without networkx?

Answer 1

I noticed that the generated graphs have always exactly one sink vertex which is the first vertex. You can reverse direction of all edges to get a graph with single source vertex.

Answer 2

You can generate random DAGs using the gnp_random_graph() generator and only keeping edges that point from lower indices to higher. e.g.

In [44]: import networkx as nx

In [45]: import random

In [46]: G=nx.gnp_random_graph(10,0.5,directed=True)

In [47]: DAG = nx.DiGraph([(u,v,{'weight':random.randint(-10,10)}) for (u,v) in G.edges() if u<v])

In [48]: nx.is_directed_acyclic_graph(DAG)
Out[48]: True

These can have more than one source but you could fix that with @Christopher's suggestion of making a "super source" that points to all of the sources.

For small connectivity probability values (p=0.5 in the above) these won't likely be connected either.

Answer 3

The method suggested by @Aric will generate random DAGs but the method will not work for a large number of nodes for example: for n tending to 100000.

        G = nx.gnp_random_graph(n, 0.5, directed=True)
        DAG = nx.DiGraph([(u, v,) for (u, v) in G.edges() if u < v])
        # print(nx.is_directed_acyclic_graph(DAG)) # to check if the graph is DAG (though it will be a DAG)
        A = nx.adjacency_matrix(DAG)
        AM = A.toarray().tolist()  # 1 for outgoing edges
        while(len(AM)!=n):
            AM = create_random_dag(n)

        # to display the DAG in matplotlib uncomment these 2 line
        # nx.draw(DAG,with_labels = True)
        # plt.show()

        return AM

For a large number of nodes, you can use the property that every lower triangular matrix is a DAG. So generating random Lower Triangular matrix will generate random DAG.

        mat = [[0 for x in range(N)] for y in range(N)]
        for _ in range(N):
             for j in range(5):
                 v1 = random.randint(0,N-1)
                 v2 = random.randint(0,N-1)
                 if(v1 > v2):
                     mat[v1][v2] = 1
                 elif(v1 < v2):
                     mat[v2][v1] = 1

        for r in mat:
            print(','.join(map(str, r)))

Answer 4

For G -> DG -> DAG

DAG with k inputs and m outputs

1. Generate a graph with your favorite algorithm( G=watts_strogatz_graph(10,2,0.4) )
2. make the graph to bidirectional ( DG = G.to_directed())
3. ensure only node with low index points to high index
4. remove k lowest index nodes' input edge, and m highest index nodes' output edges ( that make DG to DAG)
5. make sure every k lowest index nodes have output edges, and every m highest index nodes have input edges.
6. check every node in this DAG, if the k<index<n-m, and it only has no input edges or output edges, randomly choose a node in k lowest index nodes to link to or choose a node in m highest index nodes to link to it, then you get a random DAG with k inputs and m outputs

Like:

 def g2dag(G: nx.Graph, k: int, m: int, seed=None) -> nx.DiGraph:
     if seed is not None:
         random.seed(seed)
     DG = G.to_directed()
     n = len(DG.nodes())
     assert n > k and n > m
     # Ensure only node with low index points to high index
     for e in list(DG.edges):
         if e[0] >= e[1]:
             DG.remove_edge(*e)
     # Remove k lowest index nodes' input edge. Randomly link a node if
     # they have not output edges.
     # And remove m highest index nodes' output edges. Randomly link a node if
     # they have not input edges.
     # ( that make DG to DAG)
     n_list = sorted(list(DG.nodes))
     for i in range(k):
         n_idx = n_list[i]
         for e in list(DG.in_edges(n_idx)):
             DG.remove_edge(*e)
         if len(DG.out_edges(n_idx)) == 0:
             DG.add_edge(n_idx, random.random_choice(n_list[k:]))
     for i in range(n-m, n):
         n_idx = n_list[i]
         for e in list(DG.out_edges(n_idx)):
             DG.remove_edge(*e)
         if len(DG.in_edges(n_idx)) == 0:
             DG.add_edge(random.random_choice(n_list[:n-m], n_idx))
     # If the k<index<n-m, and it only has no input edges or output edges,
     # randomly choose a node in k lowest index nodes to link to or
     # choose a node in m highest index nodes to link to it,
     for i in range(k, m-n):
         n_idx = n_list[i]
         if len(DG.in_edges(n_idx)) == 0:
             DG.add_edge(random.random_choice(n_list[:k], n_idx))
         if len(DG.out_edges(n_idx)) == 0:
             DG.add_edge(n_idx, random.random_choice(n_list[n-m:]))

     # then you get a random DAG with k inputs and m outputs
     return DG