生成有向图的所有可能的子图，并保持顶点数
我有两个顶点列表：V 和 S。
我想从 V 和 S 生成所有可能的有向图，因此，V 的每个顶点只有一个出边并且恰好有一个入边，并且 S 中的每个顶点可以有任意数量的入边和出边。结果中的每个图形都应包含 V 和 S 中的所有顶点。结果可以包含连接图和非连接图。
首先我认为这是一个powerset 相关的问题，但 powerset 还有许多其他集合，可能只包含一个元素（我不需要这些）。
我当前的策略是：
- 从
V中找到顶点之间的所有对，添加到Pairs； - 从
S中查找顶点之间的所有对，添加到Pairs； - 找到
V和S之间的所有顶点对，添加到Pairs中； - 以这样的方式生成大小不小于
V的子集，每个子集在第一个位置恰好有一个顶点v实例，即顶点的一个实例第二个位置中的v以及任何位置中S中任何顶点s的任意数量的实例。
我不确定这是否正确，我想知道任何想法。
也许我可以从 V 和 S 创建一个完全连接的图 G，然后以某种方式从中提取子图？ （也许在 digraph:utils 的帮助下）
PS 我试图在 Erlang 中解决这个问题，因为它是我现在正在使用和积极学习的语言。但我很高兴在答案中看到 Java、Ruby 或伪代码。
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 toPairs; - find all pairs between vertices from
S, add toPairs; - find all pairs between vertices from
VandS, add toPairs; - generate subsets of Pairs of size not less than
Vin a such way, that each subset has exactly one instance of the vertexvin the first position, one instance of the vertexvin the second position and any number of instances of any vertexsfromSin 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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
嗯，这是一个非常好的问题，但是你可以在那里做一些非常好的技巧。您可以将图形表示为
0和1的方阵，其中行数和列数是顶点数。每个1表示从行中的顶点到列中的顶点的边。那么每个可能的图都是一个具有 N^2 位的大二进制数，即有 2^(N^2) 个由 N 个顶点组成的可能图。现在您可以将问题分为两部分。S生成所有可能的图 - 每个图只是一个 N^2 位数字。V行和列，并将可能性乘以组合，其中每个V行和列中正好有一个1。我需要你澄清一下。您写了...，
S中的每个顶点可以有任意数量的入边和出边 0 是否包含在任何数量中？然后我不明白结果应该包含来自V和S的所有顶点，而约束到S则不然。这是有意义的，因为每个S都作为具有零入和出边的顶点包含在每个解决方案中。否则，它不是所有 N^2 位数字，而只是每行和每列中至少有一个1的数字，然后你不能将问题分成两部分，你必须解决S和V在一起。那么首先满足V行和列（行和列中恰好有一个1），然后将每个此解决方案乘以Sx 可能会更容易当行和列中必须至少有一个1时，满足S约束的S矩阵解。您可以尝试使用各种表示形式作为少量顶点的列表列表。当您将索引计算为
R+C*N时，您可以尝试array模块，或者您可以尝试数组的数组。对于更多的顶点，使用二进制数组是可行的。您甚至可以在这里尝试digraph模块。类似的方法非常适合在 perl 中生成完整的闭包图，其中使用 vec 进行二进制操作很糟糕。但这里似乎并非如此，因为这是一个非常不同的问题。您可能会发现一些更好的优化演示，但我怀疑 Erlang 是非常有效地进行此类计算的最佳工具。无论如何，可能性的数量在这里增长得相当快 O(2^(N^2)) 所以你不必担心大矩阵的有效存储;-)编辑：
从这个角度看问题。如果您有 10 个顶点并假设它是
V并且S为空。那么有10!可能的图，即 3628800。如果是S，则大约有2^100即 1.2677e+30 个图 (4.0197如果每秒生成 1e+09 个图表，则为 e+13 年）。这意味着对于任何数量大于极少数的顶点，您都会有大量可能的图。所以这里最大的问题是，你将如何处理它们。你不能存储它们，但如果是，那么你必须非常有效地存储它们。二进制字段是存储由S组成的图形的最有效方式。您可以找到更有效的方法来处理具有V顶点的边。我将其存储为数组或列表，其中位置是边来自的顶点，值是边去的顶点。因此，您的解决方案很大程度上取决于您将如何处理结果。我认为您会以某种方式过滤掉结果，因为我无法想象您将如何处理如此大量的图表；-) 我的建议是在图表生成过程中尽早尝试过滤掉有意义的图表。这意味着您的方法应根据目的确定，以便在生成算法中涉及您的结果过滤。
关于这个问题的 Erlang 效率，如果您处理如此大量的实体（可能的图形），您必须非常仔细地管理内存和 CPU 使用情况。您可以使用 Erlang，但对于某些时间关键的部分，您应该在 NIF 中使用 C。您还应该使用更内存友好的数据结构，如二进制或 bignum，而不是列表或元组。您还可以找到一些其他语言，如 C、C++、OCaml、Haskell...更适合此类内存和计算密集型任务。
Well, it is very nice problem, but you can do some very nice tricks there. You can present graph as square matrix of
0and1where number of rows and columns is number of vertices. Each1presents 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.S- each graph is just one N^2 bit number.Vrows and columns and multiply possibilities by combinations where is exactly one1in eachVrow and column.I need one clarification from you. You wrote ... and each vertex from
Scan 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 fromVand fromSConstrain toSdoesn't have sense because eachSis 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 one1in each row and column and then you can't divide your issue to two parts and you have to solveSandVtogether. Then it may be easier satisfyVrows and columns first (exactly one1in row and column) and then multiply each this solution bySxSmatrix solutions which satisfySconstrain when you have to have at least one1in row and column.You can experiment with various representations as list of lists for small number of vertices. You can try
arraymodule when you will compute index asR+C*Nor you can try array of array. For bigger numbers of vertices using array of binaries can be doable. You can even trydigraphmodule here. Similar approach worked well for generating full closure graphs in perl where binary manipulations usingvecsucks. 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
VandSis empty. Then there is10!possible graphs i.e. 3628800. If it would beSthere is approx2^100i.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 fromS. You can find more efficient way for edges withVvertices. 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.