Comment représenter un graphique avec plusieurs arêtes autorisées entre les nœuds et les arêtes qui peuvent disparaître de manière sélective

J'essaie de comprendre quel type de structure de données utiliser pour modéliser une utilisation réseau hypothétique et idéalisée.

Dans mon scénario, un certain nombre d'utilisateurs hostiles tentent tous de former des réseaux d'ordinateurs où toutes les connexions potentielles sont connues. Cependant, les ordinateurs dont un utilisateur a besoin pour se connecter peuvent ne pas être les mêmes que ceux dont un autre utilisateur a besoin pour se connecter; l'utilisateur 1 peut avoir besoin de connecter les ordinateurs A, B et D tandis que l'utilisateur 2 peut avoir besoin de connecter les ordinateurs B, C et E.

^{Image générée avec l'aide de NCTM Graph Creator}

Je pense que le noyau de cela va être un graphe cyclique non dirigé, avec des nœuds représentant des ordinateurs et des bords représentant des câbles Ethernet. Cependant, en raison de la nature du scénario, il existe quelques fonctionnalités rares qui excluent les listes d'adjacence et les matrices d'adjacence (au moins, sans modifications non triviales):

1. les bords peuvent devenir à usage restreint; c'est-à-dire que si un utilisateur acquiert une connexion réseau donnée, aucun autre utilisateur ne peut utiliser cette connexion
   • dans l'exemple, l'utilisateur vert ne peut pas se connecter à l'ordinateur A, mais l'utilisateur rouge a connecté B à E bien qu'il n'ait pas de lien direct entre eux
2. dans certains cas, une paire de nœuds donnée sera connectée par plus d'un bord
   • dans l'exemple, il y a deux câbles indépendants allant de D à E, donc les utilisateurs verts et bleus ont pu tous les deux connecter directement ces machines; cependant, le rouge ne peut plus établir une telle connexion
3. si deux ordinateurs sont connectés par plus d'un câble, chaque utilisateur ne peut posséder plus d'un de ces câbles

Je devrai effectuer plusieurs opérations sur ce graphique, telles que:

• déterminer si une paire d'ordinateurs particulière est connectée pour un utilisateur donné
• identifier le chemin optimal pour qu'un utilisateur donné se connecte aux ordinateurs cibles
• identifier la connexion informatique à latence la plus élevée pour un utilisateur donné (c'est-à-dire le chemin le plus long sans branchement)

Ma première pensée a été de créer simplement une collection de tous les bords, mais c'est terrible pour la recherche. La meilleure chose que je puisse penser maintenant est de modifier une liste de contiguïté afin que chaque élément de la liste contienne non seulement la longueur du bord mais aussi son coût et son propriétaire actuel. Est-ce une approche sensée? En supposant que l'espace n'est pas une préoccupation, serait-il raisonnable de créer plusieurs copies du graphique (une pour chaque utilisateur) plutôt qu'un seul graphique?

En supposant que l'espace n'est pas une préoccupation, serait-il raisonnable de créer plusieurs copies du graphique (une pour chaque utilisateur) plutôt qu'un seul graphique?

Il me semble que vous devriez utiliser ce que nous pourrions appeler des «graphiques en couches», c'est-à-dire ajouter un combinateur pour les graphiques, par exemple @, de sorte que:

• Si A et B sont des graphiques, A @ B est également un graphique (c'est-à-dire qu'il peut être appliqué aux algorithmes de votre bibliothèque de graphiques).
• L'ensemble des sommets dans A @ B est l'union des sommets dans A et B.
• L'ensemble des arêtes dans A @ B est l'union des arêtes dans A et B.
• La structure A @ B ne possède aucun sommet ni arête, mais utilise plutôt A et B comme conteneurs de données.

Avec de tels graphiques en couches, vous pouvez définir K comme étant les informations disponibles communes et R, G, B chaque information privée afin que chaque joueur voie réellement R @ K, G @ K, B @ K.

Pour réellement implémenter cela, vous pouvez rechercher une bibliothèque de graphes mettant en œuvre des algorithmes de manière générique, c'est-à-dire de sorte que l'algorithme de chemin le plus long, etc. soit paramétré par la représentation réelle de votre graphe. Donc, si votre bibliothèque dit

ConcreteGraphAlgorithms = GenericAlgorithms(ConcreteGraphImplementation)

vous pouvez facilement le remplacer par

LayeredGraphAlgorithms = GenericAlgorithms(LayeredGraphs(ConcreteGraphImplementation))

où vous fournissez LayeredGraphset empruntez le reste à la bibliothèque.

Ce dont vous avez besoin est appelé "graphique attribué". Dans un graphique attribué, des informations (attributs) sont attachées aux arcs. Un graphique pondéré l'un des graphiques attribués les plus simples.

Pour représenter un graphique attribué, vous pouvez utiliser une liste de contiguïté en ajoutant des colonnes ou des matrices de contiguïté supplémentaires en ajoutant plus d'informations dans chaque cellule. La plupart des algorithmes pour les graphiques non attribués fonctionneront si vous filtrez les arcs, en fonction des attributs. De nombreux algorithmes ont été développés pour les graphiques attribués, je ne les décrirai donc pas ici.