查询以在 mongodb 个图形集合中查找连通分量？

Question

我想在 mongodb 集合中对连通分量进行分组。示例：

{ '_id': 1, 'data': '...', 'similar_id': [2,3,4] }

{ '_id': 2, 'data': '...', 'similar_id': [1] }

{ '_id': 3, 'data': '...', 'similar_id': [1,4] }

{ '_id': 4, 'data': '...', 'similar_id': [1,3] }

{ '_id': 7, 'data': '...', 'similar_id': [2,3,4] }

{ '_id': 5, 'data': '...', 'similar_id': [6] }

{ '_id': 6, 'data': '...', 'similar_id': [5] }

以上网络的示意图。

所以我想要一个可以找到连通分量的查询。

{ '_id': ..., 'groups': {[1,2,3,4], [5,6], [7]} }

结果可能不需要像上面那样，只需要以某种形式将它们分成不同的组即可。

Answer 1

它不是很漂亮，但这是我得到的，我的策略的简要描述最初是创建两组节点。一个包含“连接”的节点（即存在 x=>y 和 y=>x 边）。另一个是潜在的单节点。意味着他们有一个或零个 x=>y 或 y=>x 边。

一旦实现这一点，我们所要做的就是通过连接连接的节点来减少数组。

请注意，我完全相信这不是实现您想要的结果的“最佳”方式，因为我只是专注于完成它而没有过多考虑性能或冗余。话虽如此，我将自己定义为 Mongo 爱好者，我肯定会说我对此有点挣扎。对我来说，这通常是一个危险信号，表明我的模式或数据库解决方案是错误的（也许使用图形数据库？）。同样，这些只是我的意见，我完全有可能只是纠结于这条管道。

值得一提的是，我考虑过使用 $graphLookup 的方法，但是在完全连接或几乎完全连接的图上，这需要使用 n，其中 n=节点数，最终我决定反对它，尽管如果您有任何可以将深度限制在某个常数的先验知识，这种方法可能可行。

db.collection.aggregate([
  {
    $unwind: {
      path: "$similar_id",
      preserveNullAndEmptyArrays: true
    }
  },
  {
    $addFields: {
      similar_id: {
        $ifNull: [
          "$similar_id",
          "$_id"
        ]
      }
    }
  },
  {
    $sort: {
      _id: 1,
      similar_id: -1
    }
  },
  {
    $addFields: {
      tmpId: {
        $cond: [
          {
            $gt: [
              "$similar_id",
              "$_id"
            ]
          },
          [
            "$_id",
            "$similar_id"
          ],
          [
            "$similar_id",
            "$_id"
          ]
        ]
      }
    }
  },
  {
    $group: {
      _id: "$tmpId",
      sum: {
        $sum: 1
      }
    }
  },
  {
    $facet: {
      single: [
        {
          $match: {
            sum: 1
          }
        },
        {
          $unwind: "$_id"
        },
        {
          $group: {
            _id: null,
            potentionals: {
              $addToSet: "$_id"
            }
          }
        }
      ],
      clusters: [
        {
          $match: {
            sum: 2
          }
        },
        {
          $group: {
            _id: null,
            edges: {
              $addToSet: "$_id"
            },
            
          }
        },
        {
          $project: {
            all: {
              $reduce: {
                input: "$edges",
                initialValue: [],
                in: {
                  $setUnion: [
                    "$$this",
                    "$$value"
                  ]
                }
              }
            },
            groups: {
              $reduce: {
                input: "$edges",
                initialValue: [],
                in: {
                  $cond: [
                    {
                      $gt: [
                        {
                          $size: {
                            $filter: {
                              input: "$$value",
                              as: "subgroup",
                              cond: {
                                $gt: [
                                  {
                                    $size: {
                                      $setIntersection: [
                                        "$$subgroup",
                                        "$$this"
                                      ]
                                    }
                                  },
                                  0
                                ]
                              }
                            }
                          }
                        },
                        0
                      ]
                    },
                    {
                      $map: {
                        input: "$$value",
                        as: "subgroup",
                        in: {
                          $cond: [
                            {
                              $gt: [
                                {
                                  $size: {
                                    $setIntersection: [
                                      "$$subgroup",
                                      "$$this"
                                    ]
                                  }
                                },
                                0
                              ]
                            },
                            {
                              "$setUnion": [
                                "$$this",
                                "$$subgroup"
                              ]
                            },
                            "$$subgroup"
                          ]
                        }
                      }
                    },
                    {
                      $concatArrays: [
                        "$$value",
                        [
                          "$$this"
                        ]
                      ]
                    }
                  ]
                }
              }
            }
          }
        }
      ]
    }
  },
  {
    $unwind: {
      path: "$single",
      preserveNullAndEmptyArrays: true
    }
  },
  {
    $unwind: {
      path: "$clusters",
      preserveNullAndEmptyArrays: true
    }
  },
  {
    $project: {
      groups: {
        $concatArrays: [
          "$clusters.groups",
          {
            $map: {
              input: {
                $filter: {
                  input: "$single.potentionals",
                  as: "pot",
                  cond: {
                    $eq: [
                      {
                        $size: {
                          $setIntersection: [
                            [
                              "$$pot"
                            ],
                            "$clusters.all"
                          ]
                        }
                      },
                      0
                    ]
                  }
                }
              },
              as: "single",
              in: [
                "$$single"
              ]
            }
          }
        ]
      }
    }
  }
])

MongoPlayground

Answer 2

抱歉这么晚回复，但也许其他人会觉得这有用。

您可以尝试使用 Python 中的 NetworkX 库。

第一次展开 similar_id 得到成对的文档 {'_id':1,'similar_id':2}

import networkx as nx 

unwind={'$unwind':'$similar_id'}
pipeline=[unwind]
cursor=db.collection.aggregate(pipeline)
G=nx.Graph()
for c in cursor:
      G.add_edge(c['_id'],c['similar_id'])
    
    
all_clusters=list(nx.connected_components(G))  # a list of all connected components
len(all_clusters) # number of connected components

查询以在 mongodb 个图形集合中查找连通分量？

Query to find connected components in mongodb graph collection?

graph

mongoose

mongodb

pymongo

mongodb-query