python - 基于图形的元组合并？

Question

我在相关匹配的元组中有配对值(技术上仍在 CSV 文件中)。配对值都不一定是唯一的。

tupleAB = (A####, B###), (A###, B###), (A###, B###)...
tupleBC = (B####, C###), (B###, C###), (B###, C###)...
tupleAC = (A####, C###), (A###, C###), (A###, C###)...

我理想的输出是具有唯一 ID 和“强化”匹配项列表的字典。我尝试在基于图形的上下文中思考它。

例如，如果:

tupleAB[x] = (A0001, B0012)
tupleBC[y] = (B0012, C0230)
tupleAC[z] = (A0001, C0230)

这会产生:

output = {uniquekey0001, [A0001, B0012, C0230]}

理想情况下，这也可以扩展到三个以上的元组(例如，添加“D”匹配会导致额外的三个元组 - AD、BD 和 CD - 以及四个项目长的列表; 等等)。

关于扩展到更多元组，我对拥有不一定完全连接的“图”持开放态度，即每个节点都连接到每个其他节点。我的直觉是我可以很容易地根据列表长度进行过滤。我愿意接受任何建议。

我想，只要喝几杯咖啡，我就能想出一个蛮力解决方案，但我想我会问问社区是否有人知道更优雅的解决方案。感谢您的任何反馈。

编辑 1 以澄清:在图形上下文中，我发现了一种我认为可行的方法 - 循环检测 (http://en.wikipedia.org/wiki/Cycle_detection_(graph_theory)#Cycle_detection)。如果这为任何人敲响了警钟，我想我正在尝试识别由元组中的成对值构造的图中的循环。

编辑 2:好的，这是计划:1)获取csv文件并构建incidence matrix用于图形分析2) 执行depth first search在关联矩阵的每个节点上(并通过在原始节点上结束来完成一个循环)3) 尝试最大化独特的“字母”(A、B、C 等——在我的例子中，字母代表物种)4) 这些最大物种深度优先搜索是字典中的列表

Answer 1

我认为您想要的是弗洛伊德算法的 Warshall 变体:http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

这将在 O(n^3) 时间内找到图中所有可达的对。