Julia/Graphs.jl: Erstellen von Graphen mit graph() und Argumenten

Question

Ich versuche Subgraph von Graphen in Julia mit Graphs.jl Modul zu bekommen. Ich habe Graph und ich speichern seine Scheitelpunkte und Kanten zu Liste und dann bewegt sich mein Algorithmus durch diese Liste und entfernt Knoten und Kanten, die nicht Teil des neuen Untergraphen sind. Zu diesem Teil funktioniert alles richtig, nachdem ganzen Algorithmus alles, was sub_vertices ist Array bleibt Typ: Graphs.ExVertex [] und Array sub_edgesTyp: Graphs.ExEdge {Graphs.ExVertex} [].

Am Ende der ganzen Funktion I wanto Subgraphen zu schaffen, so verwende ich:

sub_g = graph(sub_vertices, sub_edges, is_directed=false) 

aber ich bekomme Bounds() Fehler. Irgendeine Idee? Alles, was ich weiß, ist das Problem an Kanten.

ich versuchte zu laufen:

sub_g = graph(sub_vertices, Graphs.ExEdge{Graphs.ExVertex}[], is_directed=false) 

Und es läuft ok. Es erstellt ein Diagramm mit Scheitelpunkten, die durch das Array sub_vertices gegeben werden. Problem tritt auf, wenn Kanten mit sub_edges hinzugefügt werden.

Zusätzliche Informationen: Scheitelpunkte und Kanten sind exakte Kopien des ursprünglichen Diagramms. Das heißt, Attribute wie Index, Label, ... sind dieselben wie im Originalgraphen. Ich dachte, dass Indizes von Vertices Problem sein können, aber es ist nicht, weil wenn ich renne,

sub_g = graph(sub_vertices, Graphs.ExEdge{Graphs.ExVertex}[], is_directed=false) 

es läuft OK. Und nach dem Drucken der Scheitelpunkte haben sie Indizes 1,3,5, aber es scheint in Ordnung zu sein. Also ich weiß nicht, warum Kanten Grenzen gibt.

Answer 1

Es ist wahrscheinlich keine gute Idee, den Graphenkonstruktor zu verwenden, um einen Subgraphen zu erhalten. Ich bin nicht vertraut mit Graphs.jl, aber ich habe mit Graphen in Julia gearbeitet.

Der Konstruktor weist wahrscheinlich sub_vertices neue Indizes zu. Wenn also sub_vertices[5,6,9] ist, wird das neue Diagramm zum Beispiel weiterhin [1,2,3] verwenden. Wenn Ihre Kantenliste [5 => 6, 6 => 9, 9 => 5] ist, werden Sie feststellen, dass keine der Kanten gültig ist, da der Untergraph nur Scheitelpunkte [1,2,3] hat .

Ich würde vorschlagen, dass Sie ein dediziertes Subgraphen Methode verwenden, um zu erreichen, was Sie versuchen, in zwei Stufen zu tun,:

1. zunächst eine Subgraphen berechnet die sub_edges mit Sie isoliert haben .
2. Als nächstes berechnen Sie einen Untergraphen mit dem sub_vertices.

Graft.jl hat eine Methode, die Sie beide auf einmal tun können:

julia> using Graft 

    julia> g = completegraph(10) 
     Graph(10 vertices, 90 edges, Symbol[] vertex properties, Symbol[] edge properties) 

    julia> sg = subgraph(g, [5,6,9], [5=>6, 6=>9, 9=>5]) 
     Graph(3 vertices, 3 edges, Symbol[] vertex properties, Symbol[] edge properties) 

    julia> vertices(sg) 
     1:3 

    julia> edges(sg) 
     3-element Graft.EdgeIter: 
      1=>2 
      2=>3 
      3=>1 

Oder wenn Sie die Eckpunkte wollen ihre Original-Etiketten

julia> g = completegraph(10) 
     Graph(10 vertices, 90 edges, Symbol[] vertex properties, Symbol[] edge properties) 

    julia> setlabel!(g, collect(1:10)) # Label the vertices 

    julia> sg = subgraph(g, [5,6,9], [5=>6, 6=>9, 9=>5]) 
     Graph(3 vertices, 3 edges, Symbol[] vertex properties, Symbol[] edge properties) 

    julia> encode(sg) 
     3-element Array{Int64,1}: 
      5 
      6 
      9 

    julia> encode(sg, edges(sg)) 
     3-element Array{Pair{Int64,Int64},1}: 
      5=>6 
      6=>9 
      9=>5