Groupement d'unions dans les graphes bipartis?

8

J'essaie de trouver une bonne (et rapide) solution au problème suivant:

J'ai deux modèles avec lesquels je travaille, appelons-les joueurs et équipes. Un joueur peut appartenir à plusieurs équipes et une équipe peut avoir plusieurs joueurs). Je travaille sur la création d'un élément d'interface utilisateur sur un formulaire qui permet à un utilisateur de sélectionner plusieurs équipes (cases à cocher). Comme l'utilisateur sélectionne (ou désélectionne) des équipes, je voudrais afficher les équipes regroupées par les joueurs.

Donc, pour des exemples:

  1. Si les équipes sélectionnées n'ont pas de joueurs qui se croisent, chaque équipe aurait sa propre section.

  2. Si l'utilisateur sélectionne deux équipes et qu'il a les mêmes joueurs, il y aurait une section contenant les noms des deux équipes et de tous les joueurs.

  3. Si TEAM_A a des joueurs [1, 2, 4, 5] et TEAM_B a des joueurs [1, 3, 5, 6]. Il y aurait les sections suivantes: SECTION_X = [TEAM_A, TEAM_B, 1, 5], SECTION_Y = [TEAM_A, 2, 3], SECTION _Z = [TEAM_B, 3, 5]

J'espère que c'est clair. Essentiellement, je veux trouver les équipes que les joueurs ont en commun et regrouper par là. Je pensais qu'il y avait peut-être un moyen de le faire en naviguant sur un graphique bipartite? Je ne sais pas exactement comment et je pense peut-être trop. J'espérais le faire en créant un certain type de structure de données sur le serveur et en l'utilisant sur le client. J'aimerais entendre vos suggestions et j'apprécie toute aide que vous pouvez apporter!

graphs Ian
la source
Êtes-vous sûr de ne pas pouvoir coder cette logique en utilisant une relation plusieurs-à-plusieurs entre vos modèles. Espérons que lorsque vous commencerez à écrire votre code côté serveur, votre framework préféré vous permettra de déclarer des modèles avec certains champs. Par conséquent, vous pourrez indiquer que le modèle Teamdoit avoir un champ appelé playersqui nécessite une relation plusieurs-à-plusieurs avec votre autre modèle Player. Cela vous permet de récupérer les joueurs de chaque équipe et les équipes associées à chaque joueur.
Robert Smith
Avez-vous choisi une technologie particulière? Cela pourrait être fait avec Neo4J et Cypher.
sheldonkreger

Réponses:

2

Avez-vous entendu parler du graphique d'intersection ? Vous pouvez essayer de dessiner des joueurs comme des points, des connexions (coéquipiers) comme des bords et des équipes comme des taches colorées transparentes sur le dessus.

Quant à votre question initiale, je ne comprends pas votre objectif. Je pense que votre formulation n'est pas bien définie / incomplète. Supposons que vous ayez les équipes A [1,2] B [2,3] et C [1,3]. Que voulez-vous afficher? Voulez-vous répertorier les parties du diagramme de Venn? Je pense que pour plus de 3 sets cela peut devenir plus lourd que le graphe bipartite lui-même = simple listage des compositions des équipes.

Valentas
la source
1

Stockez les bords (relations) dans votre serveur:

(TeamID, playerID)

Lorsque vous souhaitez trouver des éléments communs, il suffit de filtrer toutes les arêtes où:

TeamID="TeamA" or TeamID="TeamB"

(Vous pouvez utiliser des index pour accélérer, etc.)

Regroupez ensuite par playerID et vérifiez le nombre d'éléments dans chaque groupe. Les groupes avec deux éléments appartiennent aux deux équipes et sont partagés.

Juan Leni
la source