Categories
Development MongoDB

Disjoint sets in Mongodb

Hi have a MongoDB collection matchedpairs with a data structure as follows:

each document defines a pairwise connection with each other, i.e 1 is in union with 2 and 2 is in union with 10 etc. There are a large number of relationships defined.

{
    x:1,
    y:2
},
{
    x:2,
    y:10
},
{
    x:9,
    y:10
},
{
    x:8,
    y:4
}

I would like to query the documents and retrieve the unique disjoint sets for the pairs, i.e. return a result like this

{
    set:[1,2,9,10]
},
{
    set:[8,4]
}

I am familiar with the aggregation framework, but cannot see how to create the correct accumulator in the $group stage to create the disjoint sets. The attempt below simply gives just one grouping of similar pairs. As I see it I would have to create a whole string of $group stages (depending upon my set of data) to get the result I am looking for. Any clever ideas here?

db.matchedpairs.aggregate([
    {
        '$group': {
            '_id': '$y', 
            'like': {
                '$addToSet': '$x'
            }, 
            'from': {
                '$addToSet': '$y'
            }
        }
    }, {
        '$project': {
            '_id': 0, 
            'set': {
                '$setUnion': [
                    '$like', '$from'
                ]
            }
        }
    }
]

gives:

{
 set:[4,8]
},
{
 set:[10,2,9]
},
{
 set:[1,2]
}

Leave an answer

Your email address will not be published. Required fields are marked *