我正在解决有向无环图的问题。
但是我在一些有向无环图上测试我的代码时遇到了麻烦。测试图应该很大，并且（显然）是非循环的。
我尝试了很多代码来生成无环有向图。但我每次都失败了。
是否有一些现有的方法可以生成我可以使用的无环有向图？
问问题
19770 次
9 回答
59
我编写了一个 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;
}
这是从测试运行生成的图表：
于 2012-10-08T23:06:08.920 回答
21
https://mathematica.stackexchange.com/questions/608/how-to-generate-random-directed-acyclic-graphs的答案适用：如果您有图形边缘的邻接矩阵表示，那么如果矩阵是下三角形，它必然是一个 DAG。
类似的方法是对节点进行任意排序，然后仅在x < y时才考虑从节点x到y的边。该约束也应该通过构造来获得您的 DAGness。如果您使用结构来表示节点，那么内存比较将是一种对节点进行排序的任意方式。
基本上，伪代码将类似于：
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”），我们可以选择它们之间是否有边。
于 2012-10-08T22:39:28.213 回答
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.
实际上，代码所做的就是通过重复执行以下操作来生成请求的边数：
- 在 [0, V) 范围内生成两个数字；
- 如果他们是平等的，就拒绝他们；
- 如果第一个更大，则交换它们；
- 如果它以前生成过它们，则拒绝它们。
这个解决方案的问题在于，当 E 接近最大边数 V(V-1)/2 时，算法变得越来越慢，因为它必须拒绝越来越多的边。更好的解决方案是制作一个包含所有 V(V-1)/2 个可能边的向量；随机洗牌；并选择洗牌列表中的第一个（请求的边）边。
储层采样算法允许我们在空间 O(E) 中执行此操作，因为我们可以从 k 的值推断出第 k 条边的端点。因此，我们实际上不必创建源向量。但是，它仍然需要 O(V 2 ) 时间。
或者，可以进行Fisher-Yates shuffle（或 Knuth shuffle，如果您愿意），在 E 次迭代后停止。在 Wikipedia 中提供的 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 2 ) 空间。实际上，这可以通过一些技巧改进到 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;
}
于 2012-10-09T03:27:15.337 回答
3
您可以生成一个随机有向图，然后对循环进行深度优先搜索。当你找到一个循环时，通过删除一条边来打破它。
我认为这是最坏的情况 O(VE)。每个 DFS 需要 O(V)，并且每个 DFS 至少删除一条边（所以最大 E）
如果您通过均匀随机选择所有 V^2 个可能的边来生成有向图，并且您以随机顺序进行 DFS 并删除随机边 - 这将为您提供所有可能的 dag 上的均匀分布（或至少接近它）。
于 2012-10-08T22:32:36.070 回答
2
一个非常简单的方法是：
通过迭代下对角矩阵的索引来随机分配边（如上面的链接所示：https ://mathematica.stackexchange.com/questions/608/how-to-generate-random-directed-acyclic-graphs ）
这将为您提供一个可能包含多个组件的 DAG。您可以使用不相交集数据结构为您提供组件，然后可以通过在组件之间创建边来合并这些组件。
此处描述了不相交集：https ://en.wikipedia.org/wiki/Disjoint-set_data_structure
于 2017-03-03T18:23:31.193 回答
2
编辑：我最初在处理名为灵活作业车间调度问题的调度问题时发现了这篇文章，其中作业（处理操作的顺序）由有向无环图定义。这个想法是使用一种算法来生成多个随机有向图（作业）并创建调度问题的实例来测试我的算法。本文末尾的代码是我用来生成实例的代码的基本版本。实例生成器可以在这里找到。
我翻译成 Python 并集成了一些功能来创建随机 DAG 的传递集。这样，生成的图具有相同可达性的最小边数。
通过将输出粘贴到模型代码（右侧）中，可以在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()
结果：
于 2019-08-02T07:32:15.100 回答
1
创建一个图，其中包含n节点和每对节点之间的边n1以及n2ifn1 != n2和n2 % n1 == 0。
于 2012-10-08T22:30:13.153 回答
1
我最近尝试重新实现接受的答案，发现它是不确定的。如果您不强制执行 min_per_rank 参数，您最终可能会得到一个包含 0 个节点的图。
为了防止这种情况，我将 for 循环包装在一个函数中，然后检查以确保在每个等级之后，它min_per_rank都得到满足。下面是 JavaScript 实现：
https://github.com/karissa/random-dag
还有一些伪 C 代码将取代已接受答案的主循环。
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
}
于 2015-11-20T20:24:32.643 回答
1
生成可能未连接的随机 DAG
这是一个用于生成可能未连接的随机 DAG 的简单算法。
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。
顶点DAG 中从顶点i到顶点的边，其中，在索引处具有边权重where 。jni < jkk = n * i + j - (i + 1) * (i + 2) / 2
生成连接的 DAG
生成随机 DAG 后，您可以使用以下函数检查它是否已连接。
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);
};
请注意，如果我们创建一个具有 30% 边的随机 DAG，那么它的补码将具有 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>希望有帮助。
于 2020-01-01T11:58:18.610 回答