生成有向图的所有可能子图，保持顶点数 [英] Generate all possible subgraphs of a directed graph keeping the number of vertices

问题描述

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

我想从 V 和 S 生成所有可能的有向图，所以每个顶点从 V 只有一个外边缘和正好一个边缘，并且 S 中的每个顶点可以有任意数量的内外边缘。结果中的每个图形都应该包含来自 V 和 S 的所有顶点。结果可以包含连接和断开的图形。

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

我目前的策略是：

• code> V ，添加到对;


• 从 S ，添加到对;


• 从 V 和 S ，添加到对;


• 以这样的方式生成大小不小于 V 的对的子集，每个子​​集只有顶点的一个实例 v 在第一个位置，第二个位置的顶点 v 的一个实例和任何顶点的任何数量的实例 s 从 S 任何位置。

I我不知道这是对的，我想知道任何想法。

也许我可以创建一个完全连接的图表 G 从 V 和 S 然后以某种方式从中提取子图？ （或许借助于图：utils）

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

解决方案

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

1. 从 S生成所有可能的图表 - 每个图只是一个N ^ 2位数。


2. 然后，对于每个此图形，您可以通过 V 行和列展开矩阵，并通过组合乘以恰好一个<$ c $每个 V 行和列中的c> 1

我需要你的一个澄清。你写了 ...并且 S 中的每个顶点都可以有任意数量的进出口 ？然后我不明白结果应该包含来自 V 和 S 的所有顶点限制到 S 没有意义，因为每个解决方案中包含每个 S 作为具有零进出边缘的顶点。否则，不是所有的N ^ 2位数字，只有那些在每行和列中至少有一个 1 ，那么你不能将你的问题分成两部分，你必须一起解决 S 和 V 。那么可能更容易满足 V 行和列（行和列中只有一个 1 ），然后将每个这个解决方案由 S x S 满足 S 限制，当您必须在行和列中至少有一个 1 。

您可以尝试各种表示形式少数顶点的列表列表。您可以尝试数组模块，当您计算索引为 R + C * N 或者您可以尝试数组数组。对于使用二进制数组的更大数量的顶点可以实现。您甚至可以在这里尝试 digraph 模块。类似的方法对于在perl中生成完全关闭图表非常有效，其中使用 vec 的二进制操作很糟糕。但这并不是因为这是非常不同的问题。您可能会发现一些更好的优化演示文稿，但我怀疑Erlang是非常有效的这种计算的最佳工具。 （2 ^（N ^ 2）），所以你不必担心大矩阵的有效存储; - ）

编辑：

从这个角度来看问题。如果您有10个顶点，并假设它是 V 和 S 是空的。那么有 10！可能的图，即3628800.如果它是 S 有大约$ code> 2 ^ 100 ie 1.2677e + 30图（4.0197e + 13年，如果您将每秒生成1e + 09图表）。这意味着任何数量的顶点大于极少数，您可能有很多可能的图形。这里最大的问题是，你会怎么做。您不能存储它们，但如果是，则必须非常有效地存储它们。二进制字段是存储由 S 制作的图形的最有效方法。您可以使用 V 顶点找到更有效的方式。我将它存储为数组或列表，其中位置是顶点的顶点，而边缘去的值是顶点。

所以你的解决方案强烈地依赖于你将做什么结果。我想你会以某种方式过滤掉结果，因为我无法想象你会用如此大量的图表做什么;-)我的建议是在图形生成过程中尽早过滤出有意义的图形。这意味着您的方法应该通过目的来确定，以便在生成算法时使用您的结果过滤。

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

I have two lists of vertices: V and S.

I would like to generate all possible directed graphs from V and S so, that each vertex from V has only one out-edge and exactly one in-edge, and each vertex from S can have any number of in- and out- edges. Each graph in the result should contain exactly all vertices from V and from S. The result can contain both connected and disconnected graphs.

First I thought it was a powerset-related problem, but powerset has many other sets that may contain just one element (and I do not need those).

My current strategy is to:

• find all pairs between vertices from V, add to Pairs;
• find all pairs between vertices from S, add to Pairs;
• find all pairs between vertices from V and S, add to Pairs;
• generate subsets of Pairs of size not less than V in a such way, that each subset has exactly one instance of the vertex v in the first position, one instance of the vertex v in the second position and any number of instances of any vertex s from S in any position.

I am not sure this is right and I would like to know about any ideas.

Maybe I could create a fully-connected graph G from V and S and then somehow extract subgraphs from it? (perhaps with the help of digraph:utils)

P.S. I am trying to solve this in Erlang, because it is the language that I am using and actively learning now. But I would be glad to see Java, Ruby or pseudocode in the answer.

解决方案

Well, it is very nice problem, but you can do some very nice tricks there. You can present graph as square matrix of 0 and 1 where number of rows and columns is number of vertices. Each 1 presents edge from vertex in row to vertex in column. Then every possible graph is one big binary number with N^2 bits i.e. there is 2^(N^2) possible graphs made from N vertices. Now you can divide your issue to two parts.

1. Generate all possible graphs from S - each graph is just one N^2 bit number.
2. Then for each this graph you expand matrix by V rows and columns and multiply possibilities by combinations where is exactly one 1 in each V row and column.

I need one clarification from you. You wrote ... and each vertex from S can have any number of in- and out- edges Is 0 included in any number? Then I don't understand result should contain exactly all vertices from V and from S Constrain to S doesn't have sense because each S is included in each solution as vertex with zero in and out edges. Otherwise it's not all N^2 bit numbers but only those which have at least one 1 in each row and column and then you can't divide your issue to two parts and you have to solve S and V together. Then it may be easier satisfy V rows and columns first (exactly one 1 in row and column) and then multiply each this solution by SxS matrix solutions which satisfy S constrain when you have to have at least one 1 in row and column.

You can experiment with various representations as list of lists for small number of vertices. You can try array module when you will compute index as R+C*N or you can try array of array. For bigger numbers of vertices using array of binaries can be doable. You can even try digraph module here. Similar approach worked well for generating full closure graphs in perl where binary manipulations using vec sucks. But it doesn't seem case here because it is very different issue. You may found some better optimized presentations but I doubt Erlang is best tool for this sort of computations very efficiently. Anyway number of possibilities is growing pretty fast here O(2^(N^2)) so you don't have to worry about efficient storage of big matrices ;-)

Edit:

Look at problem from this perspective. If you have 10 vertices and assume it is V and S is empty. Then there is 10! possible graphs i.e. 3628800. If it would be S there is approx 2^100 i.e. 1.2677e+30 graphs (4.0197e+13 years if you will generate 1e+09 graphs per second). It means for any number of vertices bigger than very few you have very big number of possible graphs. So biggest question here is, what will you do with them. You can't store them but if yes so you have to store them very efficiently. Binary field is most efficient way for storing graphs made from S. You can find more efficient way for edges with V vertices. I would store it as array or list where position is vertex where edge goes from and value is vertex where edge goes to.

So your solution strongly depend what you will do with result. I think you will filter out results in some way because I can't imagine what you will do with so big number of graphs ;-) Mine advice is try filter out meaningful graphs as early as possible during graphs generation. It means your approach should be determined by purpose to enable involve your result filtering in generating algorithm.

And about Erlang efficiency for this problem, if you deal with so enormous number of entities (possible graphs) you have to manage your memory and CPU usage very carefully. You can use Erlang but for some time critical parts you should use C in NIFs. You also should use more memory friendly data structures as binaries or bignums instead of lists or tuples. You also can find some other languages as C, C++, OCaml, Haskell, ... more suitable for such memory and computation intensive task.

这篇关于生成有向图的所有可能子图，保持顶点数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！