Почему Graphviz больше не минимизирует длину ребер при введении подграфов - PullRequest
3 голосов
/ 06 марта 2012

У меня есть этот график Graphviz:

digraph
{
   rankdir="LR";
   overlap = true;
   Node[shape=record, height="0.4", width="0.4"];
   Edge[dir=none];

   A B C D E F G H I 

   A -> B -> C
   D -> E -> F
   G -> H -> I

   Edge[constraint=false]

   A -> D -> G

   subgraph clusterX
   {
      A
      B
   }

   subgraph clusterY
   {
      E
      H
      F
      I
   }
}

, который производит этот вывод:

Graphviz output

Я бы ожидал длину ребра между A иD нужно свести к минимуму, чтобы узлы были расположены следующим образом:

A B C
D E F
G H I

, а не

D E F
G H I
A B C

Это работает, как ожидается, если я удалю определения подграфа.

Почему Graphviz размещает ABC внизу, когда вводятся подграфы?

1 Ответ

6 голосов
/ 07 марта 2012

Это на самом деле не означает минимизации длины ребер , тем более что в примере ребра определены с атрибутом constraint=false.

Хотя это не полный ответ, я думаю, его можно найти где-то в следующих двух точках:

  • Важен порядок появления узлов в графе.
  • Изменение rankdir на LR содержит непредсказуемое (или, по крайней мере, трудно прогнозируемое) поведение и / или, возможно, все еще одну или две ошибки ( search rankdir ).

Я постараюсь объяснить как можно лучше и понять graphviz, но вы можете пойти дальше и сразу же прочитать этот ответ Эмдена Р. Ганснера в списке рассылки graphviz , а также следующий ответ Стивена Норта - они должны знать, поэтому я приведу некоторые из них ...


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

Поэтому без кластеров и rankdir=LR графики выглядят так (без сюрпризов):

A D G
B E H
C F I

Пока все хорошо. Но что происходит, когда применяется rankdir=LR?

ERG пишет:

Точка обрабатывает rankdir = LR с помощью обычной схемы TB, а затем поворачивает раскладка против часовой стрелки на 90 градусов (а потом, конечно же, обработка вращение узла, направление ребра и т. д.). Таким образом, подграф один расположен слева от подграфа два в макете TB, как вы бы ожидать, а затем оказывается ниже, чем после вращения. Если ты хочешь подграф один должен быть сверху, укажите его вторым на графике.

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

G H I
D E F
A B C

На самом деле они выглядят так:

A B C
D E F
G H I

Почему? Стивен Норт ответил:

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

Итак, график выложен TB, повернут против часовой стрелки и перевернуты плоские края:

A D G     G H I     A B C
B E H --> D E F --> D E F
C F I     A B C     G H I

Хотя это работает довольно хорошо для простых графиков, кажется, что когда речь идет о кластерах, все немного по-другому. Обычно ребра также переворачиваются внутри кластеров (как в clusterY), но есть случаи, когда переворот плоских ребер не работает, как можно было бы подумать. Ваш пример - один из таких случаев.

Почему ошибка или ограничение при переключении этих ребер? Поскольку при использовании rankdir=TB.

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

К счастью, обходные пути часто просты - например, вы можете использовать порядок появления узлов для влияния на макет:

digraph
{
   rankdir="LR";
   node[shape=record, height="0.4", width="0.4"];
   edge[dir=none];

   E; // E is first node to appear
   A -> B -> C;
   D -> E -> F;
   G -> H -> I;

   edge[constraint=false]
   A -> D -> G;

   subgraph clusterX { A; B; }
   subgraph clusterY { E; F; H; I; }
}
...