So stellen Sie ein Diagramm mit mehreren zulässigen Kanten zwischen Knoten und Kanten dar, die selektiv verschwinden können

Ich versuche herauszufinden, welche Art von Datenstruktur zur Modellierung einer hypothetischen, idealisierten Netzwerknutzung verwendet werden soll.

In meinem Szenario versuchen mehrere einander feindliche Benutzer, Computernetzwerke zu bilden, in denen alle potenziellen Verbindungen bekannt sind. Die Computer, die ein Benutzer zum Verbinden benötigt, sind möglicherweise nicht mit denen identisch, die ein anderer Benutzer zum Verbinden benötigt. Benutzer 1 muss möglicherweise die Computer A, B und D verbinden, während Benutzer 2 möglicherweise die Computer B, C und E verbinden muss.

^{Mit Hilfe von NCTM Graph Creator erzeugtes Bild}

Ich denke, der Kern davon wird ein ungerichteter zyklischer Graph sein, wobei Knoten Computer und Kanten Ethernet-Kabel darstellen. Aufgrund der Art des Szenarios gibt es jedoch einige ungewöhnliche Merkmale, die Adjazenzlisten und Adjazenzmatrizen ausschließen (zumindest ohne nicht triviale Änderungen):

1. Kanten können eingeschränkt genutzt werden; Das heißt, wenn ein Benutzer eine bestimmte Netzwerkverbindung erwirbt, darf kein anderer Benutzer diese Verbindung verwenden
   • In diesem Beispiel kann der grüne Benutzer möglicherweise keine Verbindung zu Computer A herstellen, aber der rote Benutzer hat B mit E verbunden, obwohl keine direkte Verbindung zwischen ihnen besteht
2. In einigen Fällen wird ein bestimmtes Knotenpaar durch mehr als eine Kante verbunden
   • In diesem Beispiel gibt es zwei unabhängige Kabel, die von D nach E verlaufen, sodass sowohl die grünen als auch die blauen Benutzer diese Maschinen direkt anschließen konnten. Rot kann eine solche Verbindung jedoch nicht mehr herstellen
3. Wenn zwei Computer über mehr als ein Kabel verbunden sind, darf jeder Benutzer nicht mehr als eines dieser Kabel besitzen

Ich muss mehrere Operationen an diesem Diagramm ausführen, z.

• Bestimmen, ob ein bestimmtes Computerpaar für einen bestimmten Benutzer verbunden ist
• Identifizieren des optimalen Pfads für einen bestimmten Benutzer zum Verbinden von Zielcomputern
• Identifizieren der Computerverbindung mit der höchsten Latenz für einen bestimmten Benutzer (dh längster Pfad ohne Verzweigung)

Mein erster Gedanke war, einfach eine Sammlung aller Kanten zu erstellen, aber das ist für die Suche schrecklich. Das Beste, was ich mir jetzt vorstellen kann, ist, eine Adjazenzliste so zu ändern, dass jedes Element in der Liste nicht nur die Kantenlänge, sondern auch die Kosten und den aktuellen Eigentümer enthält. Ist das ein vernünftiger Ansatz? Unter der Annahme, dass der Speicherplatz kein Problem darstellt, wäre es sinnvoll, mehrere Kopien des Diagramms (eine für jeden Benutzer) anstelle eines einzelnen Diagramms zu erstellen?

Unter der Annahme, dass der Speicherplatz kein Problem darstellt, wäre es sinnvoll, mehrere Kopien des Diagramms (eine für jeden Benutzer) anstelle eines einzelnen Diagramms zu erstellen?

Es scheint mir, dass Sie das verwenden sollten, was wir als "geschichtete Diagramme" bezeichnen könnten, dh einen Kombinator für Diagramme hinzufügen, z @.

• Wenn A und B Graphen sind, ist A @ B auch ein Graph (dh kann den Algorithmen Ihrer Graphbibliothek zugeführt werden).
• Die Menge der Eckpunkte in A @ B ist die Vereinigung der Eckpunkte in A und B.
• Die Kantenmenge in A @ B ist die Vereinigung der Kanten in A und B.
• Die Struktur A @ B besitzt keinen Scheitelpunkt oder keine Kante, sondern verwendet A und B als Datencontainer.

Mit solchen geschichteten Graphen können Sie K als die verfügbaren verfügbaren Informationen und R, G, B als jede private Information definieren, so dass jeder Spieler tatsächlich R @ K, G @ K, B @ K sieht.

Um dies tatsächlich zu implementieren, suchen Sie möglicherweise nach einer Diagrammbibliothek, die Algorithmen generisch implementiert, dh, dass der Algorithmus mit dem längsten Pfad usw. durch die tatsächliche Darstellung Ihres Diagramms parametrisiert wird. Also, wenn Ihre Bibliothek sagt

ConcreteGraphAlgorithms = GenericAlgorithms(ConcreteGraphImplementation)

Sie können es leicht durch ersetzen

LayeredGraphAlgorithms = GenericAlgorithms(LayeredGraphs(ConcreteGraphImplementation))

wo Sie das liefern LayeredGraphsund den Rest aus der Bibliothek ausleihen.

Was Sie brauchen, wird als "zugeschriebener Graph" bezeichnet. In einem zugeordneten Diagramm werden Informationen (Attribute) an die Bögen angehängt. Ein gewogenes Diagramm, eines der am einfachsten zugeordneten Diagramme.

Um ein zugeordnetes Diagramm darzustellen, können Sie eine Adjazenzliste verwenden, indem Sie zusätzliche Spalten oder Adjazenzmatrizen hinzufügen, indem Sie in jeder Zelle weitere Informationen hinzufügen. Die meisten Algorithmen für nicht zugeordnete Diagramme funktionieren, wenn Sie die Bögen basierend auf den Attributen filtern. Viele Algorithmen wurden für zugeordnete Graphen entwickelt, daher werde ich sie hier nicht beschreiben.