生成一个随机的有向无环图（DAG）

Question

生成一个随机的有向无环图（DAG）

c++calgorithmgraphcycle

34

我正在解决一个有向无环图的问题。

但是，我在测试一些大型有向无环图时遇到了麻烦。测试图应该是大型的，且（显然）是无环的。

我尝试了很多次编写生成无环有向图的代码。但每次都失败了。

是否存在某种现有的方法可以生成我可以使用的无环有向图？

- Utkarsh Srivastav

1

你如何使用C和C++，却不展示任何代码？ - sehe

我会选择一些大型的开源电路网表，并使用基于DFS的简单循环检测器来打破其中的循环（如果有的话）。 - bobah

我正在受苦 - 希望它不会太疼。抱歉，我开了个玩笑，但你的英语真的很好。在这里查看函数directed_acyclic_graph：http://condor.depaul.edu/rjohnson/source/graph_ge.c - Flavius

10个回答

21

答案:

从https://mathematica.stackexchange.com/questions/608/how-to-generate-random-directed-acyclic-graphs获取的回答适用：如果您有一个表示图边的邻接矩阵，则如果矩阵是下三角形，则它必然是DAG。

类似的方法是采用任意顺序排列节点，然后仅考虑从节点x到y的边，只有当x < y时才考虑这些边。这个限制条件也应该通过构造来获得DAG。如果您使用结构体表示节点，则内存比较将是一种任意排序节点的方式。

基本上，伪代码应该是这样的：

for(i = 0; i < N; i++) {
    for (j = i+1; j < N; j++) {
        maybePutAnEdgeBetween(i, j);
    }
}

在你的图中，N 表示节点数量。

伪代码表明，给定 N 个节点，潜在的 DAG 数量为

2^(n*(n-1)/2),

由于存在这样的情况

n*(n-1)/2

我们可以选择有或没有它们之间的边，这些是有序对（“从N中选择2”）。

- dyoo

1

所有的有向无环图是否都可以用顶点置换的方式表示为一个下三角邻接矩阵？ - Andrew Tomazos

2

根据http://en.wikipedia.org/wiki/Directed_acyclic_graph，您可以对节点进行拓扑排序。鉴于此，如果按照拓扑排序的顺序编写矩阵行，则由于拓扑排序，它必须是下三角形式的。 - dyoo

1

一个更好解释的证明在SO上：https://dev59.com/9EfRa4cB1Zd3GeqP707u - dyoo

1

我现在明白了，在有向无环图中必须有一个没有入边的顶点。将其中一个放在 n 矩阵的最后一行。最右侧的列必须全部为零。从图中删除该顶点，得到 n-1 个顶点的有向无环图。通过归纳法，它适用于 n-1 子矩阵。 - Andrew Tomazos

1

你不会强制实施结构以确保单个连接的DAG。你的maybePutAnEdgeBetween过程需要促进这一点。 - Domi

显示剩余2条评论

4

所以为了尝试把所有这些合理的答案结合起来：（在以下内容中，我使用V表示生成的图中的顶点数，E表示边数，并且我们假设E≤V(V-1)/2。）就个人而言，我认为最有用的答案是评论中的，Flavius指向了http://condor.depaul.edu/rjohnson/source/graph_ge.c的代码。那段代码非常简单，而且它方便地被一个注释描述了出来，我复制如下：

To generate a directed acyclic graph, we first
generate a random permutation dag[0],...,dag[v-1].
(v = number of vertices.)
This random permutation serves as a topological
sort of the graph. We then generate random edges of the
form (dag[i],dag[j]) with i < j.

实际上，该代码的作用是通过反复执行以下步骤来生成边的请求编号：

1.在范围[0，V）内生成两个数字； 2.如果它们相等，则拒绝它们； 3.如果第一个数字较大，则交换它们； 4.如果已经生成过这些数字，则拒绝它们。

这种解决方案的问题在于，随着E接近最大边数V(V-1)/2，算法变得越来越慢，因为它必须拒绝越来越多的边。更好的解决方案是创建包含所有V(V-1)/2个可能边的向量；随机打乱它；并选择打乱后列表中的前（请求的边）条边。蓄水池抽样算法使我们可以在O(E)的空间中完成此操作，因为我们可以从k的值推断出第k条边的端点。因此，我们实际上不必创建源向量。但是，它仍然需要O(V^2)的时间。

或者，你可以进行Fisher-Yates洗牌（或者Knuth洗牌，如果你喜欢），在E次迭代后停止。在维基百科中呈现的FY shuffle版本中，这将产生尾随条目，但该算法也可以向后工作：

// At the end of this snippet, a consists of a random sample of the
// integers in the half-open range [0, V(V-1)/2). (They still need to be
// converted to pairs of endpoints).
vector<int> a;
int N = V * (V - 1) / 2;
for (int i = 0; i < N; ++i) a.push_back(i);
for (int i = 0; i < E; ++i) {
  int j = i + rand(N - i);
  swap(a[i], a[j]);
a.resize(E);

这只需要 O(E) 时间，但需要 O(N²) 的空间。实际上，通过一些技巧，可以将其优化为 O(E) 空间，但是 SO 代码片段太小，无法包含结果，因此我提供一个简单的 O(E) 空间和 O(E log E) 时间的方法。我假设至少有一个名为 DAG 的类：

class DAG {
  // Construct an empty DAG with v vertices
  explicit DAG(int v);

  // Add the directed edge i->j, where 0 <= i, j < v
  void add(int i, int j);
};

现在开始：

// Return a randomly-constructed DAG with V vertices and and E edges.
// It's required that 0 < E < V(V-1)/2.
template<typename PRNG>
DAG RandomDAG(int V, int E, PRNG& prng) {
  using dist = std::uniform_int_distribution<int>;
  // Make a random sample of size E
  std::vector<int> sample;
  sample.reserve(E);
  int N = V * (V - 1) / 2;
  dist d(0, N - E);  // uniform_int_distribution is closed range
  // Random vector of integers in [0, N-E]
  for (int i = 0; i < E; ++i) sample.push_back(dist(prng));
  // Sort them, and make them unique
  std::sort(sample.begin(), sample.end());
  for (int i = 1; i < E; ++i) sample[i] += i;
  // Now it's a unique sorted list of integers in [0, N-E+E-1]
  // Randomly shuffle the endpoints, so the topological sort
  // is different, too.
  std::vector<int> endpoints;
  endpoints.reserve(V);
  for (i = 0; i < V; ++i) endpoints.push_back(i);
  std::shuffle(endpoints.begin(), endpoints.end(), prng);
  // Finally, create the dag
  DAG rv;
  for (auto& v : sample) {
    int tail = int(0.5 + sqrt((v + 1) * 2));
    int head = v - tail * (tail - 1) / 2;
    rv.add(head, tail);
  }
  return rv;
}

- rici

3

你可以生成一个随机的有向图，然后进行深度优先搜索以查找循环。当你找到一个循环时，通过删除一条边来打破它。

我认为这是最坏情况下的O(VE)。每个DFS需要O(V)，而每个DFS至少删除一条边（所以最大E）。

如果你通过均匀随机选择所有V^2可能的边来生成有向图，并按随机顺序进行DFS并删除随机边 - 这将为你提供对所有可能DAG的均匀分布（或者至少接近均匀分布）。

- Andrew Tomazos

2

生成一个可能不连通的随机有向无环图

以下是一个简单的算法，用于生成一个可能不连通的随机有向无环图。

const randomDAG = (x, n) => {
    const length = n * (n - 1) / 2;

    const dag = new Array(length);

    for (let i = 0; i < length; i++) {
        dag[i] = Math.random() < x ? 1 : 0;
    }

    return dag;
};

const dagIndex = (n, i, j) => n * i + j - (i + 1) * (i + 2) / 2;

const dagToDot = (n, dag) => {
    let dot = "digraph {\n";

    for (let i = 0; i < n; i++) {
        dot += `    ${i};\n`;

        for (let j = i + 1; j < n; j++) {
            const k = dagIndex(n, i, j);
            if (dag[k]) dot += `    ${i} -> ${j};\n`;
        }
    }

    return dot + "}";
};

const randomDot = (x, n) => dagToDot(n, randomDAG(x, n));

new Viz().renderSVGElement(randomDot(0.3, 10)).then(svg => {
    document.body.appendChild(svg);
});

<script src="https://cdnjs.cloudflare.com/ajax/libs/viz.js/2.1.2/viz.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/viz.js/2.1.2/full.render.js"></script>

如果您运行此代码片段几次，可能会看到一个不连通的DAG。

那么，这个代码是如何工作的呢？

有向无环图（DAG）只是一个拓扑排序的无向图。一个有n个顶点的无向图最多可以有n * (n - 1) / 2条边，不计重复边或从一个顶点到自身的边。现在，你只能从一个更低的顶点到一个更高的顶点有一条边。因此，所有边的方向都是预定的。

这意味着您可以使用一个n * (n - 1) / 2的边权值的一维数组来表示整个DAG。边权值为0表示该边不存在。因此，我们只需创建一个随机的0或1的数组，这就是我们的随机DAG。

在由n个顶点构成的DAG中，从顶点i到顶点j的一条边，其中i < j，其边权值在索引k处为k = n * i + j - (i + 1) * (i + 2) / 2。请保留HTML标签。

生成一个连通的有向无环图

一旦你生成了一个随机的有向无环图，你可以使用以下函数来检查它是否连通。

const isConnected = (n, dag) => {
    const reached = new Array(n).fill(false);

    reached[0] = true;

    const queue = [0];

    while (queue.length > 0) {
        const x = queue.shift();

        for (let i = 0; i < n; i++) {
            if (i === n || reached[i]) continue;
            const j = i < x ? dagIndex(n, i, x) : dagIndex(n, x, i);
            if (dag[j] === 0) continue;
            reached[i] = true;
            queue.push(i);
        }
    }

    return reached.every(x => x); // return true if every vertex was reached
};

如果没有连接，那么它的补集将始终连接。

const complement = dag => dag.map(x => x ? 0 : 1);

const randomConnectedDAG = (x, n) => {
    const dag = randomDAG(x, n);
    return isConnected(n, dag) ? dag : complement(dag);
};

请注意，如果我们创建了一个随机DAG，其中30%的边缘，则其补充将具有70%的边缘。因此，x的唯一安全值为50％。但是，如果您关心连通性而不是边缘的百分比，则这不应该成为交易破坏者。

最后，将所有内容放在一起。

const randomDAG = (x, n) => {
    const length = n * (n - 1) / 2;

    const dag = new Array(length);

    for (let i = 0; i < length; i++) {
        dag[i] = Math.random() < x ? 1 : 0;
    }

    return dag;
};

const dagIndex = (n, i, j) => n * i + j - (i + 1) * (i + 2) / 2;

const isConnected = (n, dag) => {
    const reached = new Array(n).fill(false);

    reached[0] = true;

    const queue = [0];

    while (queue.length > 0) {
        const x = queue.shift();

        for (let i = 0; i < n; i++) {
            if (i === n || reached[i]) continue;
            const j = i < x ? dagIndex(n, i, x) : dagIndex(n, x, i);
            if (dag[j] === 0) continue;
            reached[i] = true;
            queue.push(i);
        }
    }

    return reached.every(x => x); // return true if every vertex was reached
};

const complement = dag => dag.map(x => x ? 0 : 1);

const randomConnectedDAG = (x, n) => {
    const dag = randomDAG(x, n);
    return isConnected(n, dag) ? dag : complement(dag);
};

const dagToDot = (n, dag) => {
    let dot = "digraph {\n";

    for (let i = 0; i < n; i++) {
        dot += `    ${i};\n`;

        for (let j = i + 1; j < n; j++) {
            const k = dagIndex(n, i, j);
            if (dag[k]) dot += `    ${i} -> ${j};\n`;
        }
    }

    return dot + "}";
};

const randomConnectedDot = (x, n) => dagToDot(n, randomConnectedDAG(x, n));

new Viz().renderSVGElement(randomConnectedDot(0.3, 10)).then(svg => {
    document.body.appendChild(svg);
});

<script src="https://cdnjs.cloudflare.com/ajax/libs/viz.js/2.1.2/viz.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/viz.js/2.1.2/full.render.js"></script>

如果您运行此代码片段多次，可能会看到一个比其他DAG具有更多边的DAG。

生成一定比例的边连接的DAG

如果你关心连通性和一定比例的边，那么可以使用以下算法。

从一个完全连通的图开始。
随机删除边。
在删除一条边后，检查图是否仍然连通。
如果不再连通，则添加该边。

需要注意的是，这种算法不如之前的方法高效。

const randomDAG = (x, n) => {
    const length = n * (n - 1) / 2;

    const dag = new Array(length).fill(1);

    for (let i = 0; i < length; i++) {
        if (Math.random() < x) continue;
        dag[i] = 0;
        if (!isConnected(n, dag)) dag[i] = 1;
    }

    return dag;
};

const dagIndex = (n, i, j) => n * i + j - (i + 1) * (i + 2) / 2;

const isConnected = (n, dag) => {
    const reached = new Array(n).fill(false);

    reached[0] = true;

    const queue = [0];

    while (queue.length > 0) {
        const x = queue.shift();

        for (let i = 0; i < n; i++) {
            if (i === n || reached[i]) continue;
            const j = i < x ? dagIndex(n, i, x) : dagIndex(n, x, i);
            if (dag[j] === 0) continue;
            reached[i] = true;
            queue.push(i);
        }
    }

    return reached.every(x => x); // return true if every vertex was reached
};

const dagToDot = (n, dag) => {
    let dot = "digraph {\n";

    for (let i = 0; i < n; i++) {
        dot += `    ${i};\n`;

        for (let j = i + 1; j < n; j++) {
            const k = dagIndex(n, i, j);
            if (dag[k]) dot += `    ${i} -> ${j};\n`;
        }
    }

    return dot + "}";
};

const randomDot = (x, n) => dagToDot(n, randomDAG(x, n));

new Viz().renderSVGElement(randomDot(0.3, 10)).then(svg => {
    document.body.appendChild(svg);
});

<script src="https://cdnjs.cloudflare.com/ajax/libs/viz.js/2.1.2/viz.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/viz.js/2.1.2/full.render.js"></script>

希望这有所帮助。

- Aadit M Shah

2

一个非常简单的方法是：

通过迭代下三角矩阵的索引（如上面的链接所建议的：https://mathematica.stackexchange.com/questions/608/how-to-generate-random-directed-acyclic-graphs），随机分配边。
这将给你一个可能有多个组件的DAG。你可以使用不相交集数据结构来得到这些组件，然后通过在组件之间创建边来合并它们。

不相交集在这里描述：https://en.wikipedia.org/wiki/Disjoint-set_data_structure。

- Michael Lewis

2

编辑：我最初是在处理一个名为具有序列灵活性的灵活作业车间调度问题时发现了这篇文章，其中作业（操作处理顺序）由有向无环图定义。我的想法是使用算法生成多个随机有向图（作业），并创建调度问题实例来测试我的算法。本文末尾的代码是我用来生成实例的基本版本。实例生成器可以在此处找到。

我将其翻译为Python，并集成了一些功能，以创建随机DAG的传递集。这样，所生成的图形具有相同可达性的边缘最少。

可以通过将输出粘贴到Model Code（右侧）中，在http://dagitty.net/dags.html上可视化传递图形。

算法的Python版本

import random

class Graph:
    nodes = []
    edges = []
    removed_edges = []

    def remove_edge(self, x, y):
        e = (x,y)
        try:
            self.edges.remove(e)
            # print("Removed edge %s" % str(e))
            self.removed_edges.append(e)
        except:
            return

    def Nodes(self):
        return self.nodes

    # Sample data
    def __init__(self):
        self.nodes = []
        self.edges = []


def get_random_dag():
    MIN_PER_RANK = 1    # Nodes/Rank: How 'fat' the DAG should be
    MAX_PER_RANK = 2
    MIN_RANKS = 6   # Ranks: How 'tall' the DAG should be
    MAX_RANKS = 10
    PERCENT = 0.3  # Chance of having an Edge
    nodes = 0

    ranks = random.randint(MIN_RANKS, MAX_RANKS)

    adjacency = []
    for i in range(ranks):
        # New nodes of 'higher' rank than all nodes generated till now
        new_nodes = random.randint(MIN_PER_RANK, MAX_PER_RANK)

        # Edges from old nodes ('nodes') to new ones ('new_nodes')
        for j in range(nodes):
            for k in range(new_nodes):
                if random.random() < PERCENT:
                    adjacency.append((j, k+nodes))

        nodes += new_nodes

    # Compute transitive graph
    G = Graph()
    # Append nodes
    for i in range(nodes):
        G.nodes.append(i)
    # Append adjacencies
    for i in range(len(adjacency)):
        G.edges.append(adjacency[i])

    N = G.Nodes()
    for x in N:
        for y in N:
            for z in N: 
                if (x, y) != (y, z) and (x, y) != (x, z):
                    if (x, y) in G.edges and (y, z) in G.edges:
                        G.remove_edge(x, z)

    # Print graph
    for i in range(nodes):
        print(i)
    print()
    for value in G.edges:
        print(str(value[0]) + ' ' + str(value[1]))

get_random_dag()

下面的图片展示了由上述Python代码生成的带有许多冗余边的随机DAG。

我修改了代码，生成了相同可达性但边数最少的图，这也被称为传递闭包缩减。最初的回答已经得到改进。

def get_random_dag():
    MIN_PER_RANK = 1    # Nodes/Rank: How 'fat' the DAG should be
    MAX_PER_RANK = 3
    MIN_RANKS = 15   # Ranks: How 'tall' the DAG should be
    MAX_RANKS = 20
    PERCENT = 0.3  # Chance of having an Edge
    nodes = 0
    node_counter = 0

    ranks = random.randint(MIN_RANKS, MAX_RANKS)

    adjacency = []
    rank_list = []
    for i in range(ranks):
        # New nodes of 'higher' rank than all nodes generated till now
        new_nodes = random.randint(MIN_PER_RANK, MAX_PER_RANK)

        list = []
        for j in range(new_nodes):
            list.append(node_counter)
            node_counter += 1
        rank_list.append(list)

        print(rank_list)

        # Edges from old nodes ('nodes') to new ones ('new_nodes')
        if i > 0:
            for j in rank_list[i - 1]:
                for k in range(new_nodes):
                    if random.random() < PERCENT:
                        adjacency.append((j, k+nodes))

        nodes += new_nodes

    for i in range(nodes):
        print(i)
    print()
    for edge in adjacency:
        print(str(edge[0]) + ' ' + str(edge[1]))
    print()
    print()

结果：

- WillEnsaba

非常有用！谢谢！第一个代码块和第二个代码块有什么区别？ - Connor

第一段代码是Python的“翻译”，第二段是可传递缩减。我编辑了帖子以避免进一步混淆。如果现在清楚了，请告诉我。 - WillEnsaba

1

我最近尝试重新实现了被接受的答案，发现它是不确定的。如果您不强制执行min_per_rank参数，则可能会得到一个没有节点的图形。

为了防止这种情况，我将for循环包装在一个函数中，然后检查每个rank之后是否满足min_per_rank。以下是JavaScript的实现：

https://github.com/karissa/random-dag

以下是一些伪代码，可以替换已接受答案的主循环。

int pushed = 0

int addRank (void) 
{
  for (j = 0; j < nodes; j++)
    for (k = 0; k < new_nodes; k++)
      if ( (rand () % 100) < PERCENT)
        printf ("  %d -> %d;\n", j, k + nodes); /* An Edge.  */

  if (pushed < min_per_rank) return addRank()
  else pushed = 0

  return 0
}

- karissa

1

创建一个图，其中有 n 个节点，并且对于每一对节点 n1 和 n2，如果 n1 != n2 且 n2 % n1 == 0，则它们之间有一条边。

- Dietmar Kühl

“如果n1 != n2且n2 % n1 == 0，则每对节点n1和n2之间都有一条边”，这将以确定性方式生成一个图形。 - ArjunShankar

是的，确实如此。问题是关于生成DAG（有向无环图）的，而这是创建DAG的方法。并没有关于随机性的声明。此外，确定性图形在测试方面具有明显的优势：它们是确定性的！ - Dietmar Kühl

自从我开始关注这个问题以来，它的标题就一直有“随机”这个词。现在我看到这是编辑的结果。至于使用本质上是彼此子图的图形来测试代码的优点：我不认为我同意。我宁愿生成几千个伪随机图形并将它们存储起来，以便更好地找到错误/回归。无论如何，我不会争论这一点。这仍然是一个相当有效的答案。 - ArjunShankar

0

为了测试算法，我基于节点层生成了随机图。这是Python脚本（同时打印邻接列表）。你可以改变节点连接概率百分比或添加层数以获得略微不同或“更高”的图形：

# Weighted DAG generator by forward layers
import argparse
import random

parser = argparse.ArgumentParser("dag_gen2")
parser.add_argument(
    "--layers",
    help="DAG forward layers. Default=5",
    type=int,
    default=5,
)
args = parser.parse_args()
layers = [[] for _ in range(args.layers)]
edges = {}
node_index = -1


print(f"Creating {len(layers)} layers graph")

# Random horizontal connections -low probability-
def random_horizontal(layer):
    for node1 in layer:
        # Avoid cycles
        for node2 in filter(
            lambda n2: node1 != n2 and node1 not in map(lambda el: el[0], edges[n2]),
            layer,
        ):
            if random.randint(0, 100) < 10:
                w = random.randint(1, 10)
                edges[node1].append((node2, w))


# Connect two layers
def connect(layer1, layer2):
    random_horizontal(layer1)
    for node1 in layer1:
        for node2 in layer2:
            if random.randint(0, 100) < 30:
                w = random.randint(1, 10)
                edges[node1].append((node2, w))


# Start nodes 1 to 3
start_nodes = random.randint(1, 3)
start_layer = []

for sn in range(start_nodes + 1):
    node_index += 1
    start_layer.append(node_index)

# Gen nodes
for layer in layers:
    nodes = random.randint(2, 5)
    for n in range(nodes):
        node_index += 1
        layer.append(node_index)

# Connect all
layers.insert(0, start_layer)
for layer in layers:
    for node in layer:
        edges[node] = []
for i, layer in enumerate(layers[:-1]):
    connect(layer, layers[i + 1])

# Print in DOT language
print("digraph {")
for node_key in [node_key for node_key in edges.keys() if len(edges[node_key]) > 0]:
    for node_dst, weight in edges[node_key]:
        print(f" {node_key} -> {node_dst} [label={weight}];")
print("}")
print("---- Adjacency list ----")
print(edges)

- Matteo Tosato

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ArjunShankar · Accepted Answer

我编写了一个C程序来实现这个功能。关键是要“排名”节点，并且仅从较低排名的节点绘制到较高排名的节点。

我编写的程序以DOT语言格式打印。

以下是代码本身，其中包含解释其含义的注释：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MIN_PER_RANK 1 /* Nodes/Rank: How 'fat' the DAG should be.  */
#define MAX_PER_RANK 5
#define MIN_RANKS 3    /* Ranks: How 'tall' the DAG should be.  */
#define MAX_RANKS 5
#define PERCENT 30     /* Chance of having an Edge.  */

int main (void)
{
  int i, j, k,nodes = 0;
  srand (time (NULL));

  int ranks = MIN_RANKS
              + (rand () % (MAX_RANKS - MIN_RANKS + 1));

  printf ("digraph {\n");
  for (i = 0; i < ranks; i++)
    {
      /* New nodes of 'higher' rank than all nodes generated till now.  */
      int new_nodes = MIN_PER_RANK
                      + (rand () % (MAX_PER_RANK - MIN_PER_RANK + 1));

      /* Edges from old nodes ('nodes') to new ones ('new_nodes').  */
      for (j = 0; j < nodes; j++)
        for (k = 0; k < new_nodes; k++)
          if ( (rand () % 100) < PERCENT)
            printf ("  %d -> %d;\n", j, k + nodes); /* An Edge.  */

      nodes += new_nodes; /* Accumulate into old node set.  */
    }
  printf ("}\n");
  return 0;
}

这是从测试运行中生成的图表：

A randomly generated DAG