Как скрипт оптимально размещает чистый иерархический граф / точечный граф?

Question

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

1. Все, кроме одного узла, имеют ровно один родительский узел (так что это дерево).
2. Если два или более узла совместно используют родительский узел sampe, они сами находятся в определенном порядке.

С этими характеристиками я хотел бы получить свои результаты (это сгенерированный точками график)чтобы выглядеть так:

1. Ни одно ребро не должно пересекаться
2. Узлы с одинаковым родителем должны иметь одинаковое расстояние от верхней границы графиков.
3. Узлы с одинаковымродительский элемент должен быть нарисован слева направо в соответствии с их порядком

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

digraph G {

  node [shape=plaintext fontname="Arial"];

  0  [label="zero"      ];
  1  [label="one"       ];
  2  [label="two"       ];
  3  [label="three"     ];
  4  [label="four"      ];
  5  [label="five"      ];
  6  [label="six"       ];
  7  [label="seven"     ];
  8  [label="eight"     ];
  9  [label="nine"      ];
  10 [label="ten"       ];
  11 [label="eleven"    ];
  12 [label="twelve"    ];
  13 [label="thirteen"  ];
  14 [label="fourteen"  ];
  15 [label="fivteen"   ];
  16 [label="sixteen"   ];
  17 [label="seventeen" ];
  18 [label="eighteen"  ];
  19 [label="nineteen"  ];
  20 [label="twenty"    ];
  21 [label="twenty-one"];
  22 [label="twenty-two"];

  0  -> 1  [arrowhead=none];
  1  -> 2  [arrowhead=none];
  2  -> 7  [arrowhead=none];
  7  -> 8  [arrowhead=none];
  8  -> 9  [arrowhead=none];
  8  -> 10 [arrowhead=none];
  9  -> 10 [color="#aaaaaa" constraint=false];
  10 -> 11 [arrowhead=none];
  10 -> 12 [arrowhead=none];
  11 -> 12 [color="#aaaaaa" constraint=false];
  7  -> 13 [arrowhead=none];
  8  -> 13 [color="#aaaaaa" constraint=false];
  13 -> 14 [arrowhead=none];
  7  -> 15 [arrowhead=none];
  13 -> 15 [color="#aaaaaa" constraint=false];
  15 -> 16 [arrowhead=none];
  15 -> 17 [arrowhead=none];
  16 -> 17 [color="#aaaaaa" constraint=false];
  2  -> 3  [arrowhead=none];
  7  -> 3  [color="#aaaaaa" constraint=false];
  3  -> 4  [arrowhead=none];
  2  -> 5  [arrowhead=none];
  3  -> 5  [color="#aaaaaa" constraint=false];
  5  -> 6  [arrowhead=none];
  2  -> 18 [arrowhead=none];
  5  -> 18 [color="#aaaaaa" constraint=false];
  18 -> 19 [arrowhead=none];
  19 -> 20 [arrowhead=none];
  19 -> 21 [arrowhead=none];
  20 -> 21 [color="#aaaaaa" constraint=false];
  18 -> 22 [arrowhead=none];
  19 -> 22 [color="#aaaaaa" constraint=false];
}

приводит к

Обратите внимание, упорядочение между братьями и сестрами обозначено серыми краями (стрелки).

Так, например, я счастлив с семь -> три -> пять -> восемнадцать братьев и сестер, так как они нарисованы слева направо в правильном порядке (как указанострелками).

Но я недоволен братьями и сестрами восемь -> тринадцать -> пятнадцать , потому что их края пересекают другие края и потому что их порядок не слева направо, как я

Кроме того, девять -> десять , двадцать -> двадцать один и девятнадцать -> двадцать два находятся внеправильное направление.

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

Итак, есть ли способ достичь того, чего я хочу?

Answer 1

В этом случае на самом деле все очень просто: порядок появления узлов в скрипте имеет значение. В вашем скрипте они появляются от узла 0 до узла 22 и расположены так, чтобы максимально уважать это. Однако они должны появляться в том порядке, в котором вы добавили ребра (0,1,2,7,3,5,18, ...). Поэтому самое простое решение - переместить блок, который определяет метки после блок, который определяет края , и вы получите:

Нет весов, нет невидимых ребер и нет невидимых узлов.