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

11

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.

Geben Sie hier die Bildbeschreibung ein

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?

Pops
quelle
Das scheint irgendwie relevant zu sein. youtube.com/watch?v=xdiL-ADRTxQ
RubberDuck
Ich sehe nicht wirklich, wie das hier helfen wird.
Pops
Also habe ich eine Weile darüber nachgedacht. In den meisten Algorithmen für Diagramme müssen Sie hauptsächlich zwei Dinge tun: Nachbarn aufzählen oder das Gewicht einer Kante ermitteln. Die von Ihnen aufgelisteten Fragen betreffen nur einen Benutzer. Für einen einzelnen Benutzer kann das Aufzählen von Nachbarn oder das Ermitteln des Gewichts einer Kante entweder in konstanter Zeit (wenn die Anzahl der Benutzer begrenzt ist) oder in Protokoll N beantwortet werden, indem einfach entweder die Adjazenzliste oder die Matrix mit einem "Besitz" gespiegelt wird. Zu diesem Zweck denke ich, dass beides einfach erweitert werden kann und auf der Grundlage traditioneller Stärken ausgewählt werden sollte, anstatt vom Benutzerteil abgelenkt zu werden.
J Trana

Antworten:

6

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.

Michael Le Barbier Grünewald
quelle
Hoppla, ignoriere meinen vorherigen Kommentar, ich habe deine Antwort ein bisschen falsch verstanden. Dies ist im Grunde das, was ich tue, obwohl ich vorhandene Grafikbibliotheken nicht ausgenutzt habe, weil ich dummerweise nicht daran gedacht habe, zu sehen, ob es welche gibt.
Pops
1

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.

Walrii
quelle
1
Sicherlich kann eine Adjazenzmatrix normalerweise nicht mehr als eine Kante zwischen jedem Knotenpaar darstellen
jk.
1
@jk, normalerweise bist du richtig. Die in der Adjazenzmatrix angehängten Informationen können jedoch die Anzahl der Bögen und separate Attribute für jeden Bogen enthalten. In den meisten Fällen würde ich jedoch eine Adjazenzliste verwenden, da dies einfacher wäre.
Walrii
1
Wenn Sie Informationen für jede Kante an die Zelle anhängen, für die Sie ohnehin eine Adjazenzliste haben, verlieren Sie den Vorteil, den eine Matrix für dichte Diagramme bietet
jk.