Generating random graphs

I need to generate random single-source/single-sink flow networks of different dimensions so that I can measure the performance of some algorithms such as the Ford-Fulkerson and Dinic.

Is the Kruskal 开发者_如何学运维algorithm a way to generate such graphs?

To create a generic flow network you just need to create an adjancency matrix.

adj[u][v] = capacity from node u to node v

So, you just have to randomly create this matrix.

For example, if n is the number of vertices that you want ( you could make that random too ):

for u in 0..n-1:
    for v in 0..u-1:
      if (rand() % 2 and u != sink and v != source or u == source):
         adj[u][v] = rand()
         adj[v][u] = 0
      else:
         adj[u][v] = 0
         adj[v][u] = rand()

Himadris answer is partly correct. I had to add some constraints to make sure that single-source/single-sink is satisfied.

For single source only one column has to be all 0 of the adjacency matrix as well as one row for single sink.

import numpy 

def random_dag(n):
    adj = np.zeros((n, n))
    sink = n-1
    source = 0
    for u in range(0, n):
        for v in range(u):
            if (u != sink and v != source or u == source):
                adj[u, v] = np.random.randint(0, 2)
                adj[v, u] = 0
            else:
                adj[u, v] = 0
                adj[v, u] = np.random.randint(0, 2)
    # Additional constraints to make sure single-source/single-sink
    # May be further randomized (but fixed my issues so far)
    for u in range(0, n):
        if sum(adj[u]) == 0:
            adj[u, -1] = 1
            adj[-1, u] = 0
        if sum(adj.T[u]) == 0:
            adj.T[u, 0] = 1
            adj.T[0, u] = 0
    return adj

You can visualize with the following code:

import networkx
import matplotlib.plot as plt

def show_graph_with_labels(adjacency_matrix, mylabels):
    rows, cols = np.where(adjacency_matrix == 1)
    edges = zip(rows.tolist(), cols.tolist())
    gr = nx.DiGraph()
    gr.add_edges_from(edges)
    nx.draw(gr, node_size=500, labels=mylabels, with_labels=True)
    plt.show()


n = 4
show_graph_with_labels(random_dag(n), {i: i for i in range(n)})