检查每一位是否在某个周期
Checking every bit is on some cycle
我正在编写一个模型，其中：
节点表示为长度为 10 的位向量，每个位向量代表一些分子，边可以将源中存在的任何分子带到目标节点。
例如
S_Node : 0b0100000011 // Molecule 0 , 1 , 8 present on node
One_Edge : 0b0000000010 // Molecule 1 is going out on edge
我必须强制执行 边缘上的每个传出分子在某个周期 返回源节点的条件。分子必须在循环中返回意味着在循环路径期间，它必须出现在它所采用的每个节点和每个边缘上。
* 允许平行边。
分子 1 采用路径 S_Node -> Node_1 -> Node_2 ... -> S_Node。所以分子 1 从边上的 S_Node 开始，经过 Node_1 ... 并循环回到 S_Node。因此，该分子满足条件。
同样，我必须检查每条边上的每个分子。
我正在以简单的可能方式检查每个节点有哪些可能的边出去，然后为每个边检查可能存在的位并强制每个节点在某个周期返回。
for (i = 0; i < N; i++) { // for each Node
for (j = 0; j < E; j++) { // for each Edge going out frm node i
// Lets say we have some way of finding E
if(edgeWeight & (1 << j)) { //All outgoing bits
// Enforcing that each will come back
// On some Cycle
很容易看出，我必须遍历所有节点，然后遍历所有边缘，然后对于这些边缘上的每个位，必须编写代码来执行相同的操作。强制执行本身必须迭代至少 no.Of 个节点 #N.
有什么更好的方法可以有效地做到这一点？还有其他方法可以检查图论中的相同内容吗？谢谢
节点的表示与问题无关。你有一个有向图。您希望验证对于每个节点和边缘，都存在一个包含该边缘的循环。并且您希望合理有效地处理它（而不是从所有边缘对所有可能的循环进行蛮力搜索）。
这是一个观察。假设您在图表 G 中找到一个循环。考虑图 G'，它与您的原始图相同，只是循环已折叠为单个节点。 G 问题的答案与 G' 问题的答案相同，因为 G 中的任何循环都会导致 G' 中的循环（可能 self-intersecting一个可以变成2个循环），G'中的任何一个循环都会导致G中的一个循环（如果你击中了折叠节点，然后沿着它的循环直到找到出口点继续）。
所以现在的问题是从蛮力发现循环到折叠循环，直到你有一个可以轻松回答问题的小图。所以对于每个节点，对于每条边，你开始一条路径。您的路径会继续，直到您发现一个循环。任何循环。 （不一定要回到原来的节点！）折叠那个循环，继续旅行，直到你不得不回溯（在这种情况下你的条件不满足）或者你设法循环回到你的原始节点，折叠那个循环，然后移动到另一边。
如果你实现这个，你将有一个多项式算法，但不是你能做的最好的。问题是创建循环折叠的新图是一项昂贵的操作。但是有一个技巧可以提供帮助。与其每次找到循环时都折叠图表，不如尝试偷懒。为该循环创建一个新的 "fake node"，并将该循环中的每个节点标记为进入那个假节点。每次你看到一条通往节点的边时，通过这些映射进行递归搜索，找到你找到的最折叠的节点，并将你在该搜索中看到的所有内容标记为直接映射到那里。
如果你很好地实现了惰性位，你的整体算法应该结束 O(E) 其中 E 是图中的边数。考虑到无论您做什么都必须访问每条边，您实际上无法做得更好。
你似乎有一个每个分子（每个位）的有向图简单地做你的技巧来检查每个分子的任何non-cycles。
你可以采用 btillys 的方式来检查循环，另一种选择是查看 strongly connected components. You essentially want each subgraph (for a given molecule) to be a graph where each connected component 实际上是强连接的。前面链接的维基百科文章中提到的强连接组件有一些很好的算法。
我正在编写一个模型，其中：
节点表示为长度为 10 的位向量，每个位向量代表一些分子，边可以将源中存在的任何分子带到目标节点。
例如
S_Node : 0b0100000011 // Molecule 0 , 1 , 8 present on node
One_Edge : 0b0000000010 // Molecule 1 is going out on edge
我必须强制执行 边缘上的每个传出分子在某个周期 返回源节点的条件。分子必须在循环中返回意味着在循环路径期间，它必须出现在它所采用的每个节点和每个边缘上。 * 允许平行边。
分子 1 采用路径 S_Node -> Node_1 -> Node_2 ... -> S_Node。所以分子 1 从边上的 S_Node 开始，经过 Node_1 ... 并循环回到 S_Node。因此，该分子满足条件。 同样，我必须检查每条边上的每个分子。
我正在以简单的可能方式检查每个节点有哪些可能的边出去，然后为每个边检查可能存在的位并强制每个节点在某个周期返回。
for (i = 0; i < N; i++) { // for each Node
for (j = 0; j < E; j++) { // for each Edge going out frm node i
// Lets say we have some way of finding E
if(edgeWeight & (1 << j)) { //All outgoing bits
// Enforcing that each will come back
// On some Cycle
很容易看出，我必须遍历所有节点，然后遍历所有边缘，然后对于这些边缘上的每个位，必须编写代码来执行相同的操作。强制执行本身必须迭代至少 no.Of 个节点 #N.
有什么更好的方法可以有效地做到这一点？还有其他方法可以检查图论中的相同内容吗？谢谢
节点的表示与问题无关。你有一个有向图。您希望验证对于每个节点和边缘，都存在一个包含该边缘的循环。并且您希望合理有效地处理它（而不是从所有边缘对所有可能的循环进行蛮力搜索）。
这是一个观察。假设您在图表 G 中找到一个循环。考虑图 G'，它与您的原始图相同，只是循环已折叠为单个节点。 G 问题的答案与 G' 问题的答案相同，因为 G 中的任何循环都会导致 G' 中的循环（可能 self-intersecting一个可以变成2个循环），G'中的任何一个循环都会导致G中的一个循环（如果你击中了折叠节点，然后沿着它的循环直到找到出口点继续）。
所以现在的问题是从蛮力发现循环到折叠循环，直到你有一个可以轻松回答问题的小图。所以对于每个节点，对于每条边，你开始一条路径。您的路径会继续，直到您发现一个循环。任何循环。 （不一定要回到原来的节点！）折叠那个循环，继续旅行，直到你不得不回溯（在这种情况下你的条件不满足）或者你设法循环回到你的原始节点，折叠那个循环，然后移动到另一边。
如果你实现这个，你将有一个多项式算法，但不是你能做的最好的。问题是创建循环折叠的新图是一项昂贵的操作。但是有一个技巧可以提供帮助。与其每次找到循环时都折叠图表，不如尝试偷懒。为该循环创建一个新的 "fake node"，并将该循环中的每个节点标记为进入那个假节点。每次你看到一条通往节点的边时，通过这些映射进行递归搜索，找到你找到的最折叠的节点，并将你在该搜索中看到的所有内容标记为直接映射到那里。
如果你很好地实现了惰性位，你的整体算法应该结束 O(E) 其中 E 是图中的边数。考虑到无论您做什么都必须访问每条边，您实际上无法做得更好。
你似乎有一个每个分子（每个位）的有向图简单地做你的技巧来检查每个分子的任何non-cycles。
你可以采用 btillys 的方式来检查循环，另一种选择是查看 strongly connected components. You essentially want each subgraph (for a given molecule) to be a graph where each connected component 实际上是强连接的。前面链接的维基百科文章中提到的强连接组件有一些很好的算法。