Перекомпоновка графика после небольшой модификации с сохранением особенностей оригинального макета

Question

Есть ли простой способ сделать следующее в Mathematica 8?

1. Построить график и отобразить его с использованием некоторого макета графика.
2. Слегка изменить график (например, добавитьили удалите ребро или вершину).
3. Пересчитайте макет, начиная с исходного макета, таким образом, чтобы «форма» объекта была более или менее сохранена.Например, перезапустите алгоритм пружинно-электрического макета, начиная с координат предыдущего макета.

Если график не изменился между двумя дисплеями, макет также не должен изменяться (или только минимально).).Использование отображения новых Graph или GraphPlot допустимо.

РЕДАКТИРОВАТЬ: По сути, мне нужны похожие макеты для похожих графиков.Я всегда получаю похожие графики, изменяя существующий график, который, возможно, уже выложен, но приемлемо любое общее решение.

РЕДАКТИРОВАТЬ 2: Вот пример того, где подобные вещиПолезно.Перейдите на http://ccl.northwestern.edu/netlogo/models/GiantComponent и нажмите «Запустить в браузере» (требуется Java).Нажмите «Настройка», затем нажмите «Перейти».Вы можете увидеть график эволюции.Если мы сделаем это в Mathematica, то каждый из последовательных графов будет выглядеть совершенно по-разному, и будет трудно понять, что это тот же самый граф, который развивается.В некоторых приложениях весьма полезно иметь возможность визуализировать небольшие изменения на графике как таковые.Но если сделано много последовательных изменений, то пересчет макета является обязательным, простого затухания или выделения краев недостаточно.Опять же, это всего лишь пример: я не пытаюсь использовать Mathematica для анимации графа или для визуализации появления гигантского компонента.

Answer 1

Вот два основных подхода к изменению графиков в MMA 8.0. Первый основан на HighlightGraph и, в частности, GraphHighlightStyle -> "DehighlightHide". Второй подход использует VertexCoordinates графа в будущих вариантах этого графа.

Мы будем обсуждать удаление отдельно от добавления, потому что они включают несколько другие методы.

[P.S. Я внес несколько изменений в свой ответ, чтобы сделать его более понятным.]

Первые некоторые данные:

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}

Вот начальный график:

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

«Удаление» края графа без изменения общего вида графика.

Давайте начнем удалять ребро (4,11), расположенное в центре графика. remainingEdgesAndVertices содержит все вершины и начальные ребра, кроме ребра (4,11).

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

Давайте «удалим» (то есть спрячем) край (4,11):

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

Если бы мы фактически удалили ребро (4, 11), график радикально изменил бы его внешний вид.

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

«Добавление» края графа без изменения общего вида графика.

Добавление ребра графа немного сложнее. Есть два способа, которые приходят на ум. Используемый здесь метод работает в обратном направлении. Вы включаете новый край сначала в скрытом виде, а затем раскрываете его позже. Исходный граф со скрытым ребром «для добавления» будет иметь компоновку, аналогичную схеме графа с «новым» ребром. Причина в следующем: на самом деле они представляют собой один и тот же график: однако они показывают разное количество ребер.

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"]

Теперь покажите график с добавленным «новым краем».

Это очень сильно отличается от рисунка 1. Но, похоже, это естественное продолжение рисунка 4.

Добавление новых вершин и ребер на лету

Существует еще один способ добавления ребер (и вершин) при сохранении общего вида. Это было вдохновлено чем-то, что Сьорд написал в своем ответе.

Давайте зарезервируем точку {0,0} для будущей вершины 99. Мы просто добавим эту точку к VertexCoordinates из g2:

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

Теперь посмотрим, как это выглядит. g3 - это просто g2 с дополнительной вершиной (999) и ребром (4,99).

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

Эта процедура позволяет нам добавлять новые ребра и вершины по мере продвижения вперед. Но для того, чтобы новые вершины были расположены в подходящем положении, потребуются некоторые пробные и ошибочные действия.

Добавить только другое ребро (без новой вершины) гораздо проще: просто добавьте новое ребро и используйте VertexCoordinates из предыдущего графа.

Вы должны иметь возможность удалять ребра из графика, используя тот же подход (используя тот же VertexCoordinates).

Answer 2

Как вы знаете, в MMA существует несколько графических форматов.У нас есть формат пакета Combinatorica, формат GraphPlot и формат M8 Graph.

GraphPlot
Координаты GraphPlot узлов можно найти следующим образом.

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

Этим графиком можно манипулировать вручную.В нем все еще можно найти как старые, так и новые координаты:

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}}

Вы можете нарисовать график сноваиспользуя измененные координаты:

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

или нарисуйте новый график

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

, который по умолчанию выглядит следующим образом:

по старым координатам:

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, как GraphPlot, но вы можете получить доступ к его координатам вершин.

GraphData["AGraph"]

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

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

Это хорошочтобы иметь эти старые координаты, потому что если мы воссоздаем этот граф, используя его матрицу смежности, его расположение немного отличается.Это можно восстановить, используя старые координаты.

Answer 3

Это в лучшем случае частичный ответ.Кроме того, я работаю с Mma 7.

Если я изменю график так, чтобы он теперь содержал «бесхозную» вершину (без соединительных ребер), но я все еще хочу показать вершину на новом графе, этосделать это путем преобразования в adjacency matrix (как первоначально указывал Карл Волл)

Например:

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

Определение нового графа gr2 следующим образом:

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

Новый график, показывающий вершину 1, может быть сгенерирован следующим образом, например:

Needs["GraphUtilities`"];

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

, дающий

Answer 4

Возможно, вы захотите проверить, помогает ли опция GraphLayout с вашим графиком в проблеме.

Я проверил все комбинации возможных значений ComponentLayout и PackingLayout спримерный график (graph0 и graph1, который равен graph0 с одним удаленным ребром, в следующем коде).Некоторые комбинации определенно выглядят более полезными для вашей цели (меньше меняет компоновку графика при удалении ребра. Я считаю,

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

сохраняет макет наилучшим образом.

Код для отображения всех комбинаций

1017 *