Post History

I have a dataset of car bookings like this:

| car_id | user_id |
| ------ | ------- |
| 1      | 1       |
| 2      | 1       |
| 1      | 2       |
| 3      | 3       |
| 1      | 2       |
| 3      | 3       |

In this dataset, two separate groups/sets of cars and users don't overlap: One group consists of two vehicles (1,2) and two users (1,2) the other group has only one car (3) and one user (3). The groups are independent and have no overlap in users or vehicles. Lines in the datasets can repeat. 

Now I have a much bigger dataset with many thousands of cars and users. What is the most elegant/fastest algorithm/data structure to find those disjunct groups? 

I code in Python or Julia.

----

I read the paper and implemented the RemSP algorithm, partly because I like algorithms, and it was cool that RemSP is so much faster than the rest of the algorithms presented. However, the processing around the results of it is noticeable. Also, I am confused because RemSP is for merging sets. I try to find independent groups. That is not the same.

Here is my code - did you have something more immediate in mind when recommending RemSP?

(How is pasting code supposed to work here? This markup seems to be an ill fit for code.)

```python
def remsp(p, x, y):
    rx = x
    ry = y
    
    while p[rx] != p[ry]:
        if p[rx] < p[ry]:
            if rx == p[rx]:
                p[rx] = p[ry]
                break
            z = rx
            p[rx] = p[ry]
            rx = p[z]
        else:
            if ry == p[ry]:
                p[ry] = p[rx]
                break
            z = ry
            p[ry] = p[rx]
            ry = p[z]
    
    return p

def find(p, x):
    if x != p[x]:
        p[x] = find(p, p[x])
    return p[x]

def get_sets(p):
    sets = {}
    for x in p.keys():
        root = find(p, x)
        if root not in sets:
            sets[root] = (set(), set())
        
        if x.startswith("car"):
            sets[root][0].add(x)
        else:
            sets[root][1].add(x)
    
    return sets.values()

# Dataset of car bookings (car_id, user_id)
bookings = [
    ("car_1", "user_1"),
    ("car_2", "user_1"),
    ("car_1", "user_2"),
    ("car_3", "user_3"),
    ("car_1", "user_2"),
    ("car_3", "user_3")
]

# Initialize parent array
p = {item: item for booking in bookings for item in booking}

# Process bookings
for car_id, user_id in bookings:
    # Merge sets containing car_id and user_id
    remsp(p, car_id, user_id)
    
    # Merge sets of all cars and users connected through user_id
    for car_id2, user_id2 in bookings:
        if user_id == user_id2:
            remsp(p, car_id, car_id2)
        if car_id == car_id2:
            remsp(p, user_id, user_id2)

# Get separate sets
sets = get_sets(p)
for s in sets:
    print(s)
```

How do I find  idependent sets in a dataset

I have a dataset of car bookings like this:


> car_id, user_id
>
> 1, 1
>
> 2, 1
>
> 1, 2
>
> 3, 3
>
> 1, 2
>
> 3, 3


In this dataset, two separate groups/sets of cars and users don't overlap: One group consists of two vehicles (1,2) and two users (1,2) the other group has only one car (3) and one user (3). The groups are independent and have no overlap in users or vehicles. Lines in the datasets can repeat. 

Now I have a much bigger dataset with many thousand cars and users. What is the most elegant/fastest algorithm/data structure to find those disjunct groups? 

This is an actual problem, not a homework exercise. :-) (I code in python or julia.)