K entferntesten Punkte vom Scheitelpunkt in Grafik edu.uci.ics.jung

Question

Ich möchte K am weitesten Punkte von einem gegebenen Scheitelpunkt in einem jung implementation of directed graph finden.

Ich nehme an, dass BFSDistanceLabeler die Arbeit macht. Es bietet jedoch keine API für die Rückgabe von K am weitesten entfernten Punkten, also muss ich es manuell tun, indem ich alle Scheitelpunkte im Graph durchquere und die Methode getDistance aufruft. Oder gibt es einen besseren Weg?

Aber es gibt eine größere Herausforderung für mich. Trotz der Tatsache, dass die Grafik gerichtet ist, möchte ich sie als ungerichtet für den Entfernungsmarker behandeln. Ist es möglich, von einem gerichteten Graphen in eine ungerichtete Version zu wechseln?

Warum muss ich Graphen als ungerichtet behandeln?

Ich analysiere ein sehr großes Netzwerk (Millionen von Vertices) in konsequenten Schritten. In jedem Schritt wird ein kleiner Teil des Netzwerks (Tausende von Knoten) in ein Diagramm geladen und analysiert. Diese Analyse erfordert einen gerichteten Graphen und liefert das Ergebnis für einen bestimmten Eckpunkt, der in der Mitte des geladenen Bereichs liegen muß.

Wenn ich von Schritt A zu Schritt B gehe, könnte ich die gesamte vorherige Grafik löschen und eine neue erstellen. Dies wäre jedoch sehr zeitaufwendig. Da ich weiß, dass mein neuer Scheitelpunkt nahe bei dem vorherigen ist, kann ein großer Teil des Graphen wiederverwendet werden.

Und deshalb muss ich K am weitesten Punkte für den neuen Hauptknoten entfernen und sie durch neue Eckpunkte aus der Umgebung dieses Eckpunkts ersetzen.

Werfen wir einen Blick auf das untere Bild mit Grafik und sagen wir, dass Scheitelpunkt 1 unser Scheitelpunkt von Interesse ist. Da der Graph gerichtet ist, ist der Eckpunkt 6 am weitesten entfernt. Wenn jedoch der Graph als ungerichtet behandelt würde, wäre die Ecke Nummer 4 am weitesten entfernt und das ist es, was ich brauche.

Answer 1

Es wird nicht ein asymptotisch schneller Weg sein, um alle am weitesten entfernten Ecken von einem gegebenen Eingangsscheitelpunkt zu finden, als die Abstände zu allen Ecken zu finden.

Sie können die am weitesten entfernten Scheitelpunkte effizienter abrufen, indem Sie getVerticesInOrderVisited() aufrufen und dann die Liste in umgekehrter Reihenfolge beginnend mit dem 'Tail' durchlaufen: Diese Liste sollte in aufsteigender Reihenfolge der Entfernung von der Wurzel (Menge) gefüllt werden Holen Sie Vertices aus der Liste, bis die Entfernung für jede beginnt abzunehmen.

(Anmerkung: dies wird nicht die Eckpunkte holen, die vollständig aus dem Wurzelknoten getrennt werden kann, die Sie betrachten können, die „am weitesten“ sein; getUnvisitedVertices() wird das tun.)

Um Ihre zweite Frage zu beantworten *: Im Wesentlichen möchten Sie die gerichteten Kanten als ungerichtet behandeln. JUNG ermöglicht es Ihnen, dies zu tun; Anstatt /getPredecessors() zu verwenden, können Sie beispielsweise getNeighbors() aufrufen.

Wie Sie herausgefunden haben, tut BFSDistanceLabeler dies nicht; es möchte die Kantenrichtung respektieren, wenn sie existiert, also verwendet es getSuccessors(). Also hier sind einige Optionen:

1. Verwendung jung.algorithms.transformation.DirectionTransformer.toUndirected().Dies ist sehr einfach, beinhaltet aber ein paar neuen (ungerichteten) zu schaffen Kanten

2. eine Unterklasse von BFSDistanceLabeler erstellen, die labelDistances() außer Kraft gesetzt und ersetzt getSuccessors() mit getNeighbors(). Das ist ziemlich einfach, wenn nicht sehr elegant.

3. erstellen GraphDecorator Unterklasse, die getSuccessors() überschreibt getNeighbors() auf seinem Delegierten Diagramm aufrufen. Erstellen Sie dann eine Instanz Ihrer Unterklasse, wobei das ursprüngliche Diagramm der Delegat ist. Dies ist die eleganteste und allgemeinste Lösung. (Und irgendwann kann es nützlich sein für uns Dienstprogramme zu schaffen, die dies für Sie tun, wenden Sie sich bitte ein Problem auf der JUNG GitHub Seite in Datei: https://github.com/jrtom/jung/issues)

Hoffnung, das hilft.

* Zukünftige Referenz teilen Sie bitte nicht zusammenhängende Fragen in separate StackOverflow-Fragen auf; es macht sie leichter zu beantworten und zu finden.