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

11

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.

entrez la description de l'image ici

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?

Pops
la source
Cela semble en quelque sorte pertinent. youtube.com/watch?v=xdiL-ADRTxQ
RubberDuck
Je ne vois pas vraiment comment cela va aider ici.
Pops
Alors j'y ai réfléchi un moment. Dans la plupart des algorithmes pour les graphiques, vous avez principalement deux choses à faire: énumérer les voisins ou trouver le poids d'une arête. Les questions que vous avez répertoriées impliquent toutes un seul utilisateur. Pour un seul utilisateur, il est possible de répondre à l'énumération des voisins ou à la recherche du poids d'un bord soit en temps constant (si le nombre d'utilisateurs est limité) soit dans le journal N en reflétant simplement la liste d'adjacence ou la matrice avec une "propriété". À cette fin, je pense que l'un ou l'autre peut être étendu facilement et devrait être choisi en fonction des forces traditionnelles, plutôt que d'être distrait par la partie utilisateur.
J Trana

Réponses:

6

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.

Michael Le Barbier Grünewald
la source
Oups, méprisez mon commentaire précédent, j'ai mal lu votre réponse un peu. C'est essentiellement ce que je fais, même si je n'ai pas réussi à tirer parti des bibliothèques de graphes existantes, car je ne pensais pas bêtement de voir s'il en existait.
Pops
1

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.

walrii
la source
1
une matrice d'adjacence ne peut sûrement pas représenter plus d'un bord entre chaque paire de nœuds
jk.
1
@jk, normalement vous avez raison. Mais les informations attachées dans la matrice d'adjacence pourraient avoir le nombre d'arcs et des attributs séparés pour chaque arc. Mais dans la plupart des cas, j'utiliserais une liste de contiguïté car ce serait plus simple.
walrii
1
si vous attachez des informations pour chaque bord à la cellule, vous avez de toute façon une liste adjacente, vous perdez l'avantage qu'une matrice vous offre pour les graphiques denses
jk.