2

我有两个顶点列表：V和S.

我想从等生成所有可能的有向图V，S每个顶点V只有一个出边和一个入边，每个顶点S可以有任意数量的入边和出边。结果中的每个图都应包含来自V和 的所有顶点S。结果可以包含连通图和不连通图。

首先我认为这是一个与 powerset 相关的问题，但是 powerset 有许多其他的集合可能只包含一个元素（我不需要那些）。

我目前的策略是：

  • 找到顶点之间的所有对V，添加到Pairs；
  • 找到顶点之间的所有对S，添加到Pairs；
  • V从和中找到所有顶点之间的对S，添加到Pairs;
  • 生成大小不小于V这样的对子集，每个子​​集在第一个位置恰好有一个顶点v实例，在第二个位置有一个顶点实例，以及来自任何位置v的任意数量的任何顶点实例.sS

我不确定这是否正确，我想知道任何想法。

也许我可以从中创建一个完全连接的图G，V然后S以某种方式从中提取子图？（也许在 digraph:utils 的帮助下）

PS 我正在尝试在 Erlang 中解决这个问题，因为它是我现在正在使用并积极学习的语言。但我很高兴在答案中看到 Java、Ruby 或伪代码。

4

1 回答 1

2

嗯，这是一个非常好的问题，但是你可以在那里做一些非常好的技巧。您可以将图形呈现为方阵0，1其中行数和列数是顶点数。每个都1表示从行中的顶点到列中的顶点的边缘。那么每个可能的图都是一个具有 N^2 位的大二进制数，即有 2^(N^2) 个由 N 个顶点组成的可能图。现在您可以将您的问题分为两部分。

  1. 从中生成所有可能的图S- 每个图只是一个 N^2 位数。
  2. 然后对于每个此图，您按行和列扩展矩阵，并通过组合乘以每行和列V中恰好是一个的可能性。1V

我需要你澄清一件事。你写了......并且每个顶点S都可以有任意数量的入边和出边0 是否包含在任意数量中？然后我不明白结果应该包含来自V和来自SConstrain to 的所有顶点S没有意义，因为每个S顶点都包含在每个解决方案中，作为具有零进出边的顶点。否则，它不是所有 N^2 位数字，而是只有那些1在每行和每列中至少有一个的数字，然后你不能将你的问题分成两部分，你必须一起S解决V。那么首先满足V行和列可能会更容易（确切地说是一个1在行和列中），然后将每个此解决方案乘以SxS矩阵解决方案，S当您必须1在行和列中至少有一个时满足约束。

您可以尝试使用各种表示作为少量顶点的列表列表。您可以array在计算索引时尝试模块，R+C*N或者您可以尝试数组数组。对于更大数量的顶点，使用二进制数组是可行的。你甚至可以digraph在这里尝试模块。类似的方法很适合在 perl 中生成完整的闭包图，其中使用二进制操作很vec糟糕。但这里似乎不是这样，因为这是一个非常不同的问题。您可能会发现一些更好的优化演示文稿，但我怀疑 Erlang 是否是非常有效地进行此类计算的最佳工具。无论如何，这里的可能性数量增长得非常快 O(2^(N^2)) 所以你不必担心大矩阵的有效存储;-)

编辑：

从这个角度看问题。V如果您有 10 个顶点并假设它S是空的。然后有10!可能的图表，即 3628800。如果有的话S，大约有2^1001.2677e+30 个图表（如果每秒生成 1e+09 个图表，则为 4.0197e+13 年）。这意味着对于任何数量大于极少数的顶点，您都有大量可能的图。所以这里最大的问题是，你将如何处理它们。您不能存储它们，但如果是，那么您必须非常有效地存储它们。二进制字段是存储由S. V您可以为带顶点的边找到更有效的方法。我会将其存储为数组或列表，其中位置是边缘所在的顶点，值是边缘所在的顶点。

因此，您的解决方案在很大程度上取决于您将如何处理结果。我认为你会以某种方式过滤掉结果，因为我无法想象你会用这么多的图表做什么;-) 我的建议是在图表生成过程中尽早过滤掉有意义的图表。这意味着您的方法应根据目的确定，以使您的结果过滤参与生成算法。

关于这个问题的 Erlang 效率，如果你处理如此大量的实体（可能的图表），你必须非常小心地管理你的内存和 CPU 使用率。您可以使用 Erlang，但对于某些时间关键部分，您应该在 NIF 中使用 C。您还应该使用对内存更友好的数据结构作为二进制文件或 bignums，而不是列表或元组。您还可以找到其他一些语言，如 C、C++、OCaml、Haskell ......更适合这种内存和计算密集型任务。

于 2011-11-04T22:50:08.097 回答