确定在连接节点的堆图 - 这是怎么叫？ [英] Identifying graphs in heap of connected nodes -- how is this called?

问题描述

我有三列的X，Y，Z。我需要它以这样的方式，与X或Y或Z的相同值的所有记录被分配给同一组分成组SQL表。我需要确保有相同的值X或Y或Z的记录不会被多个组划分。

I have a SQL table with three columns X, Y, Z. I need to split it in groups in such a way that all records with same value of X or Y or Z are assigned to the same group. I need to make sure that the records with same value X or Y or Z are never split across multiple groups.

如果你想记录为节点和X，Y，Z的边缘值，这个问题是一样的发现，其中每个图中的节点会直接或间接地通过X，Y或Z-连接所有图形边缘，但各图会没有共同的边缘与其他图（否则将是相同的图形的一部分）。

If you think of records as nodes and values of X, Y, Z as edges, this problem is the same as finding all graphs where the nodes in each graph will be connected directly or indirectly via X, Y, or Z-edge, but each graph will have no edges in common with other graphs (otherwise it would be part of the same graph).

几年前，我就知道这是什么叫，甚至想起了算法，但现在它脱离了我。请告诉我这个问题怎么叫这样我就可以谷歌的解决方案。如果你现在是一个很好的算法 - 请点我吧。如果你有一个SQL实现 - 我会娶你：）

A few years ago I knew what this was called and even remembered the algorithm but now it escapes me. Please tell me how this problem is called so I can Google for solution. If you now a good algorithm -- please point me to it. If you have a SQL implementation -- I will marry you :)

例如：

    X                   Y               Z            BUCKET
---------     ----------------      ---------      -----------
   1                   34              56              1
   54                  43              45              2
   1                   12              22              1
   2                   34              11              1

最后一行是在桶1中，因为Y = 34的值，它是相同的第一行，这是在挖斗1的

The last row is in bucket 1 because of the value of Y=34 which is the same as of the first row, which is in bucket 1.

推荐答案

这看起来不像一个曲线图，更像是一个的单纯复。 但是，如果我们把这个复杂的作为其骨架图（数字被视为顶点和一个表中的行意味着所有三个顶点通过边相连），那么我们可以只使用任何算法来寻找的连接组件此图。我不知道是否还有就是，虽然这样做在SQL一个可行的办法，也许会比较谨慎地使用的图形数据库不知。

It looks not like a graph, more like a simplicial complex. But if we treat this complex as its skeletal graph (the numbers are treated as vertices and a row in a table means that all that three vertices are connected by an edge), then we may just use any algorithm to find connected components of this graph. I'm not sure whether there is a feasible way to do this in SQL though, perhaps it would be more prudent to use a graph database somehow.

不过，对于这个特定的问题有可能是一些简单的解决方案，可以实现由SQL的方式，我没有去找。

However, for this specific problem there may be some easy solution attainable by means of SQL which I didn't look for.

这篇关于确定在连接节点的堆图 - 这是怎么叫？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！