枚举所有可能的连接节点

Question

假设我有100个节点，然后为每个节点分配一个1：100的唯一ID。

如果我想要每个节点组合的列表，我相信它的长度为2^100。这是图中可能缺少任何节点的情况。

但是说我有一个表示节点之间连接的数据框：

head(conn_)
  from  to
2    1   2
3    1   4
4    2   3
5    2   5
6    4   6
7  154 100
8  102 101

因此，此df的第一行指出存在从节点11到节点10的连接>

说我想枚举有效节点的每个组合，但是只有当集合的元素之间没有断开的连接时，组合才有效。我该怎么办？

例如，如果我有节点1->2->3->4->5->6->7->8->9，其中->表示双向连接（1连接到2，2连接到1），那么两个有效子集将是{1, 2, 3} & {4, 5, 6} ，但无效的子集为{1, 3, 4, 6}。这将是无效的，因为集合中两个元素之间的连接断开。

如果一个节点连接到多个其他节点，则视为有效连接，这意味着对于上面的数据框，我可以具有有效的集合{1, 2, 4, 6}

我很难找到一种递归或for / while循环的方法。

而且，如果每个节点最多有五个双向连接，对于100个节点，是否可以枚举全部？这个问题如何发展？

编辑：

这里是输入/输出的示例：

conn_ =
  from  to
     1   2
     1   4
     2   3
     2   5
     4   6

Expected output : { {1}, {1, 2}, {1, 4}, {1, 2, 4}, {1, 2, 3}, {1, 2, 5}, {1, 4, 6}, {1, 2, 4, 6}, {1, 2, 3, 4}, {1, 2, 3, 4, 6}, {1, 2, 3, 4, 5, 6}, {2}, {2, 3}, {2, 5}, {2, 3, 5}, {3}, {4}, {4, 6} }
注意{1, 3, 5}不在输出中，因为集合中的元素之间不存在中断，但是{1, 2, 4, 6}有效，因为1连接到2，而1连接到4 

假设我有100个节点，然后为每个节点分配一个1：100的唯一ID。如果我想要每个节点组合的列表，我相信它的长度为2 ^ 100。这是如果...

Answer 1

这里是igraph的解决方案。它将迅速耗尽您的资源来建立具有高连接性的大型图表。