Zmiana układu wykresu po drobnych modyfikacjach przy jednoczesnym zachowaniu cech oryginalnego układu

Question

Czy istnieje prosty sposób na wykonanie następujących czynności w programie Mathematica 8?

1. Skonstruuj wykres i wyświetl go za pomocą układu wykresu.
2. Zmodyfikuj delikatnie wykres (np. Dodaj lub usuń krawędź lub wierzchołek).
3. Ponownie oblicz układ, zaczynając od oryginalnego układu, w taki sposób, aby "kształt" obiektu był mniej lub bardziej zachowany. Na przykład. ponownie uruchom algorytm układu sprężynowo-elektrycznego, zaczynając od współrzędnych poprzedniego układu.

Jeśli wykres nie zmienił się między dwoma wyświetlaczami, układ nie powinien się zmienić (lub tylko minimalnie). Używanie wyświetlacza nowego Graph lub GraphPlot jest dopuszczalne.

EDYCJA: W istocie potrzebuję podobnych układów dla podobnych wykresów. Zawsze uzyskuję podobne wykresy, modyfikując istniejący, który mógł już zostać opracowany, ale jakiekolwiek ogólne rozwiązanie jest dopuszczalne.

EDYCJA 2: Oto przykład tego, gdzie takie rzeczy są przydatne. Przejdź do http://ccl.northwestern.edu/netlogo/models/GiantComponent i kliknij "Uruchom w przeglądarce" (wymaga Java). Kliknij Setup, a następnie kliknij Go. Możesz zobaczyć ewolucję wykresu. Jeśli zrobimy to w Mathematica, każdy z kolejnych wykresów będzie wyglądał zupełnie inaczej i trudno będzie zauważyć, że jest to ten sam wykres, który ewoluuje. W wielu aplikacjach bardzo przydatne jest wizualizowanie małych zmian na wykresie jako takich. Ale jeśli zrobi się wiele kolejnych zmian, to ponowne obliczenie układu jest koniecznością, po prostu zanikanie lub podkreślanie krawędzi nie jest wystarczające. Ponownie, jest to tylko przykład: nie próbuję używać Mathematica do animowania wykresu lub wizualizacji pojawienia się gigantycznego komponentu.

Answer 1

Możesz chcieć sprawdzić, czy opcja GraphLayout pomaga w wykreślaniu problemu.

I sprawdzone wszystkie możliwe kombinacje wartości ComponentLayout i PackingLayout z wykresu przykład (graph0 i graph1 który graph0 z jedną krawędzią usunięto w następujący kod). Niektóre kombinacje zdecydowanie wyglądają bardziej przydatne dla celów (zmiany układu wykres mniej, gdy krawędź jest usuwany. Uważam

"ComponentLayout" -> "CircularEmbedding" 
"ComponentLayout" -> "LayeredDrawing" 
"ComponentLayout" -> "SpiralEmbedding" 

zachować układ najlepszy.

kodu do pokazywania wszystkich kombinacji jest

In[5]:= Quit 
In[12]:= $COMPONENTLAYOUTS={(*Automatic,None,*)"CircularEmbedding","HighDimensionalEmbedding","LayeredDrawing","LinearEmbedding","RadialEmbedding","RandomEmbedding","SpiralEmbedding","SpringElectricalEmbedding","SpringEmbedding"}; 
$PACKINGLAYOUTS={"ClosestPacking","ClosestPackingCenter","Layered","LayeredLeft","LayeredTop","NestedGrid"}; 
layoutopt[c_,p_]:=GraphLayout-> {"ComponentLayout"->$COMPONENTLAYOUTS[[ c]],"PackingLayout"-> $PACKINGLAYOUTS[[p]]}; 
In[4]:= words=DictionaryLookup["*zz"]; 
In[5]:= graph0=Flatten[Map[(Thread[#\[DirectedEdge]DeleteCases[Nearest[words,#,3],#]])&,words]]; 
i=RandomInteger[{1,Length[graph0]}]; 
graph0[[i]] 
graph1=Drop[graph0,{i}]; 
Out[7]= tizz\[DirectedEdge]fizz 
In[18]:= g0[i_,j_]:=Graph[graph0,VertexLabels->"Name",ImagePadding->20,ImageSize->200,layoutopt[i,j]]; 
g1[i_,j_]:=Graph[graph1,VertexLabels->"Name",ImagePadding->20,ImageSize->200,layoutopt[i,j]] 

Column[Grid/@Table[ 
{ 
$COMPONENTLAYOUTS[[c]], 
$PACKINGLAYOUTS[[p]], 
g0[c,p], 
g1[c,p] 
}, 
{c,1,Length[$COMPONENTLAYOUTS]}, 
{p,1,Length[$PACKINGLAYOUTS]} 
]] 

Answer 2

Jak wiadomo istnieje wiele formatów wykres pływających wokół w MMA. Mamy format pakietów Combinatorica sformatować GraphPlot i sformatować M8 Graph.

GraphPlot
Możliwe jest znalezienie współrzędnych węzłów GraphPlot w następujący sposób.

GraphPlot[{1 -> 2, 2 -> 3, 3 -> 1, 3 -> 4}, DirectedEdges -> True, 
      VertexLabeling -> True] 

Wykres ten może być ręcznie manipulować.Nadal można znaleźć zarówno stare i nowe współrzędne w nim:

VertexCoordinateRules -> {{0.000196475, 0.}, {0.,0.847539}, 
          {0.916405, 0.423865}, {2.03143, 0.42382}} 

VertexCoordinateRules -> {{0.000196475, 0.}, {0., 0.847539}, 
          {1.07187,0.708887}, {1.9537, 0.00924285}} 

można narysować wykres ponownie stosując zmodyfikowaną współrzędne:

GraphPlot[{1 -> 2, 2 -> 3, 3 -> 1, 3 -> 4}, DirectedEdges -> True, 
      VertexLabeling -> True, newRules] 

lub narysować Nowy wykres

GraphPlot[{1 -> 2, 2 -> 3, 3 -> 1, 3 -> 4, 1 -> 5, 5 -> 4}, 
      DirectedEdges -> True, VertexLabeling -> True] 

że domyślnie wygląda następująco:

przy użyciu starych współrzędne:

updatedRules = VertexCoordinateRules -> 
       Append[VertexCoordinateRules /. newRules, {1, 0}]; 
GraphPlot[{1 -> 2, 2 -> 3, 3 -> 1, 3 -> 4, 1 -> 5, 5 -> 4}, 
      DirectedEdges -> True, VertexLabeling -> True, updatedRules] 

---

Graph

I nie sądzę, że można manipulować Graph jak można GraphPlot, ale można uzyskać dostęp współrzędne jego wierzchołków.

GraphData["AGraph"] 

oldCoords = AbsoluteOptions[GraphData["AGraph"], VertexCoordinates] 

(* ==> VertexCoordinates -> {{1., 2.}, {2., 3.}, {2., 1.}, {1.,1.}, 
         {1., 3.}, {2., 2.}} *) 

Dobrze jest mieć te stare współrzędne bo gdybyśmy ponownie utworzyć ten wykres używając jego macierz sąsiedztwa jego układ jest nieco inny. Można to przywrócić przy użyciu starych współrzędnych.

Answer 3

Oto dwa podstawowe podejścia do zmieniania wykresy w MMA 8.0. Pierwszy opiera się na HighlightGraph, w szczególności na GraphHighlightStyle -> "DehighlightHide". Drugie podejście wykorzystuje współrzędne VertexCooge wykresu w przyszłych wariantach tego wykresu.

Będziemy omawiać usuwanie oddzielnie od dodawania, ponieważ dotyczą one nieco innych metod.

[P.S. : Zrobiłem kilka zmian do mojej odpowiedzi w celu uczynienia go bardziej zrozumiałym]

Pierwsza część danych.

edges={1\[UndirectedEdge]8,1\[UndirectedEdge]11,1\[UndirectedEdge]18,1\[UndirectedEdge]19,1\[UndirectedEdge]21,1\[UndirectedEdge]25,1\[UndirectedEdge]26,1\[UndirectedEdge]34,1\[UndirectedEdge]37,1\[UndirectedEdge]38,4\[UndirectedEdge]11,4\[UndirectedEdge]12,4\[UndirectedEdge]26,4\[UndirectedEdge]27,4\[UndirectedEdge]47,4\[UndirectedEdge]56,4\[UndirectedEdge]57,4\[UndirectedEdge]96,4\[UndirectedEdge]117,5\[UndirectedEdge]11,5\[UndirectedEdge]18,7\[UndirectedEdge]21,7\[UndirectedEdge]25,7\[UndirectedEdge]34,7\[UndirectedEdge]55,7\[UndirectedEdge]76,8\[UndirectedEdge]11,26\[UndirectedEdge]29,26\[UndirectedEdge]49,26\[UndirectedEdge]52,26\[UndirectedEdge]111,27\[UndirectedEdge]28,27\[UndirectedEdge]51,42\[UndirectedEdge]47,49\[UndirectedEdge]97,51\[UndirectedEdge]96} 

Oto początkowy wykresu:

g = Graph[edges, VertexLabels -> "Name", ImagePadding -> 10, 
ImageSize -> 500] 

" Usuwanie "krawędzi wykresu bez zmiany ogólnego wyglądu wykresu.

Zacznijmy od usunięcia krawędzi (4,11) znajdującej się w środku wykresu. remainingEdgesAndVertices zawiera wszystkie wierzchołki i początkowe krawędzie, z wyjątkiem krawędzi (4,11).

remainingEdgesAndVertices = 
Join[VertexList[g], Complement[EdgeList[g], {4 \[UndirectedEdge] 11}]] 

Miejmy "delete" (czyli ukryć) krawędzi (4,11):

HighlightGraph[g, remainingEdgesAndVertices, VertexLabels -> "Name", 
    ImagePadding -> 10, GraphHighlightStyle -> "DehighlightHide", 
    ImageSize -> 500] 

Gdybyśmy rzeczywiście usunięte krawędź (4, 11) wykres miałby radykalnie zmienił swój wygląd.

Graph[Complement[edges, {4 \[UndirectedEdge] 11}], 
    VertexLabels -> "Name", ImagePadding -> 10, ImageSize -> 500] 

"Dodawanie" krawędź wykres bez zmiany ogólnego wyglądu wykresu.

Dodawanie krawędzi wykresu jest nieco trudniejsze. Są dwa sposoby, które przychodzą na myśl. Zastosowana tutaj metoda działa wstecz. Uwzględniasz nową krawędź jako pierwszą w ukrytej formie, a następnie odsłonisz ją później. Początkowy wykres z ukrytą krawędzią "do dodania" będzie miał układ podobny do wykresu z "nowym" brzegiem. Powód jest taki: w rzeczywistości są one tym samym wykresem: jednak pokazują one różną liczbę krawędzi.

g2 = Graph[Append[edges, 42 \[UndirectedEdge] 37], 
VertexLabels -> "Name", ImagePadding -> 10, ImageSize -> 500] 

HighlightGraph[g2, 
    Join[Complement[EdgeList[g2], {42 \[UndirectedEdge] 37}], 
    VertexList[g2]], VertexLabels -> "Name", ImagePadding -> 10, 
    GraphHighlightStyle -> "DehighlightHide"] 

teraz zobaczyć na wykresie z "nowy wymiar" dodany.

To wygląda bardzo różni się od rysunku 1. Ale to wydaje się być naturalnym przedłużeniem Rys. 4.

Dodając nowe wierzchołki i krawędzie on-the-fly

Jest inna sposób dodawania krawędzi (i wierzchołków) przy zachowaniu ogólnego wyglądu. Zainspirowało go coś, co Sjoerd napisał w swojej odpowiedzi.

Niech zastrzegają punkt {0,0} dla przyszłej wierzchołka 99. Po prostu dodać ten punkt do VertexCoordinates z G2:

vc = VertexCoordinates -> 
    Append[AbsoluteOptions[g2, VertexCoordinates][[2]], {0, 0}] 

Teraz zobaczmy jak to wygląda. g3 to po prostu g2 z dodatkowym wierzchołkiem (999) i krawędzią (4,99).

g3 = Graph[Append[EdgeList [g2], 4 \[UndirectedEdge] 999], vc, 
    VertexLabels -> "Name", ImagePadding -> 10, 
    GraphHighlightStyle -> "DehighlightHide", ImageSize -> 500] 

Procedura ta pozwala nam dodawać nowe krawędzie i wierzchołki, jak iść do przodu. Ale trzeba będzie trochę prób i błędów, aby upewnić się, że nowe wierzchołki znajdują się w odpowiedniej pozycji.

Dodawanie tylko innej krawędzi (bez nowego wierzchołka) jest znacznie łatwiejsze: wystarczy dodać nową krawędź i użyć VertexCoordinates z poprzedniego wykresu.

Powinieneś być w stanie usunąć krawędzie z wykresu przy użyciu tego samego podejścia (używając tego samego VertexCoordinates).

Answer 4

Jest to w najlepszym wypadku częściowa odpowiedź. Pracuję również z Mma 7.

Jeśli zmodyfikuję wykres tak, że teraz zawiera teraz "osierocony" wierzchołek (bez łączących się krawędzi), ale nadal chcę pokazać wierzchołek na nowym wykresie, może to być zrobione Przejście na adjacency matrix (jak pierwotnie wskazała Carl Woll)

na przykład:

gr1 = {1 -> 2, 2 -> 3, 3 -> 4, 4 -> 5, 5 -> 6, 6 -> 1}; 
gplot1 = GraphPlot[gr1, Method -> "CircularEmbedding", 
    VertexLabeling -> True] 

Określenie nowego wykresu gr2 w następujący sposób:

gr2 = {2 -> 3, 3 -> 4, 4 -> 5, 5 -> 6} 

Nowy wykres pokazujący wierzchołek 1 mogą być generowane w następujący sposób, na przykład:

Needs["GraphUtilities`"]; 

gplot2 = 
GraphPlot[SparseArray@Map[# -> 1 &, EdgeList[gr2]], 
    VertexLabeling -> True, 
    VertexCoordinateRules -> 
    Thread[VertexList[gr1] -> 
    First@Cases[gp1, GraphicsComplex[points_, __] :> points, 
     Infinity]]] 

dając