生成随机图

Question

我需要产生随机的单源/单汇流网络，的不同维度，以便我可以测量一些算法的性能，如福特-富尔克森和迪尼奇。

Kruskal算法是生成这样的图的一种方法吗？

Answer 1

要创建通用流网络，只需创建一个adjancency矩阵即可。

adju =从节点u到节点v的容量

所以，你只需要随机地创建这个矩阵。

例如，如果n是你想要的顶点数(你也可以随机)：

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()

Answer 2

希马德里斯的回答部分是正确的。我必须添加一些约束，以确保单源/单接收器得到满足。

对于单个源，只有一列必须是邻接矩阵的全部0，而对于单个接收器则必须是一行。

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

您可以使用以下代码进行可视化：

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)})