# Union grouping in bipartite graphs?

I'm trying to figure out a good (and fast) solution to the following problem:

I have two models I'm working with, let's call them players and teams. A player can be on multiple teams and a team can have multiple players). I'm working on creating a UI element on a form that allows a user to select multiple teams (checkboxes). As the user is selecting (or deselecting) teams, I'd like to display the teams grouped by the players.

So for examples:

1. If the selected teams have no players that intersect, each team would have its own section.

2. If the user selects two teams and they have the same players, there would be one section containing the names of the two teams and all the players.

3. If TEAM_A has players [1, 2, 4, 5] and TEAM_B has players [1, 3, 5, 6]. There would be the following sections: SECTION_X = [TEAM_A, TEAM_B, 1, 5], SECTION_Y = [TEAM_A, 2, 3], SECTION _Z = [TEAM_B, 3, 5]

I hope that's clear. Essentially, I want to find the teams that players have in common and group by that. I was thinking maybe there is a way to do this by navigating a bipartite graph? Not exactly sure how though and I might be overthinking it. I was hoping to do this by creating some type of data structure on the server and using it on the client. I would love to hear your suggestions and I appreciate any help you can give!

• Are you sure you can't code that logic using a many-to-many relationship between your models. Hopefully, when you start writing your server-side code, your favorite framework will allow you to declare models with some fields. Therefore, you will be able to instruct that the model Team should a have a field called players that requires a many-to-many relationship to your other model Player. This allows you to retrieve which players are in each team and which teams are associated to each player. Commented Jan 23, 2015 at 3:47
• Have you chosen any particular technology? This could be done with Neo4J and Cypher. Commented Mar 4, 2015 at 20:22

Have you heard about the intersection graph? You can try to draw players as points, connections (team mates) as edges and teams as transparent coloured blobs on top.

As for your original question, I cannot understand your goal. I think your formulation is not well defined / incomplete. Suppose you have teams A [1,2] B [2,3] and C [1,3]. What do you want to display? Do you want to list the parts of the Venn diagram? I think that for more than 3 sets this can become more cumbersome than the bipartite graph itself = simple listing of team compositions.

Store the edges (relations) in your server:

(TeamID, playerID)


When you want to find common elements just filter all edges where:

TeamID="TeamA" or TeamID="TeamB"


(You could use indexes to speed is up, etc)

Then group by playerID and check how many items are in each group. The groups with two items belong to both teams and are shared.