Erhalte den Untergraphen des kürzesten Pfades zwischen n Knoten
Ich habe ein ungewichtetes Diagramm und möchte einen Untergraphen erstellen, der nur die Knoten und Kanten enthält, die die kürzesten Pfade zwischen n bekannten Knoten enthalten. In diesem Fall sind 3 Knoten (11, 29, und 13 sind die Namen).
Frage
Wie kann ich einen Untergraphen des kürzesten Pfades zwischen n Knoten in R erhalten?
MWE
%Vor% 
Gewünschte Ausgabe
Die gewünschte Ausgabe wäre der folgende grüne Teilgraph (Oder, nah, ich gucke den Graphen oben an und wähle visuell, was der Untergraph wäre) und ignoriere / entferne die anderen Knoten und Kanten.
2 Antworten
Sie können den kürzesten Pfad zwischen n Knoten nicht finden. Da der kürzeste Pfad nur zwischen zwei Knoten definiert ist.
Ich denke, dass Sie den kürzesten Pfad von 1 node zu anderen n-1 node möchten, können Sie get_all_shortest_paths(v, to=None, mode=ALL) von igraph library verwenden.
- v - die Quelle für die berechneten Pfade
- to - ein Vertex Selector, der das Ziel für die berechnete Pfade. Dies kann eine einzelne Eckpunkt-ID sein, eine Liste von Eckpunkten IDs, ein einzelner Vertex-Name, eine Liste von Vertex-Namen. None bedeutet alle Vertices.
- Modus - die Direktionalität der Pfade. IN bedeutet zu berechnen eingehende Pfade, OUT bedeutet, ausgehende Pfade zu berechnen, ALL bedeutet, beide zu berechnen.
Gibt den kürzesten Pfad vom angegebenen Knoten zu jedem anderen erreichbaren Knoten im Diagramm in einer Liste zurück.
get_all_shortest_paths
Nun müssen Sie einen Graphen aus einer Liste der kürzesten Pfade erstellen.
-
Initialisiere ein leeres Diagramm und füge dann den gesamten Pfad aus der Liste hinzu der Pfad
Pfad im Diagramm hinzufügenODER
- mache einen Graphen für jeden gefundenen kürzesten Pfad und nehme Graphen union.
union igraph
Sie benötigen eine Matrix von kürzesten Wegen, um dann ein Unterdiagramm zu erstellen, das eine Vereinigung aller Kanten verwendet, die zu diesen Pfaden gehören.
Lassen Sie Key-Scheitelpunkte diejenigen Scheitelpunkte sein, zwischen denen Ihr gewünschter Sub-Graph erscheint. Sie sagen, Sie haben drei solche Schlüsselvertices.
Beachten Sie, dass der kürzeste Pfad zwischen i und j von ihnen unlist(shortest_paths(g, i, j, mode="all", weights=NULL)$vpath) ist. Sie sollten alle ij-Kombinationen (1-2, 1-3, 2-3 in Ihrem Fall) Ihrer Schlüssel-Vertices auflisten und dann alle Vertices auflisten, die auf den Pfaden zwischen ihnen erscheinen . Manchmal erscheinen dieselben Scheitelpunkte auf den kürzesten Wegen von mehr als einem deiner ij-Paare (Siehe Betweenness Centrality ). . Ihr gewünschter Untergraph sollte nur diese Scheitelpunkte enthalten, die Sie induced_subgraph() geben können.
Dann entsteht ein anderes interessantes Problem. Nicht alle Kanten zwischen den ausgewählten Scheitelpunkten sind Teil Ihrer kürzesten Pfade. Ich weiß nicht genau, was Sie in Ihrem Sub-Graphen wünschen, aber ich nehme an, dass Sie nur Kanten und Kanten wollen, die Teil kürzester Wege sind. Das Handbuch für induced_subgraph() sagt, dass eids bereitgestellt werden kann, um auch Untergraphen an Kanten zu filtern, aber ich habe das nicht zum Laufen gebracht. Kommentare dazu sind willkommen, wenn jemand es knackt. Um einen Untergraphen mit nur Kanten und Scheitelpunkten tatsächlich auf dem kürzesten Weg zu erstellen, müssen einige überzählige Kanten gelöscht werden.
Im Folgenden sehen Sie ein Beispiel, bei dem einige Schlüsselvertikale zufällig ausgewählt werden, das Problem mit den überzähligen Kanten von Untergraphen visualisiert wird und ein richtiger Untergraphen nur für kurze Pfade erstellt wird:
