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

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

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

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

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

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

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

результаты в

Resulting graph

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

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

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

Также, девять -> десять, двадцать -> двадцать один и девятнадцать -> двадцать два расположены в неправильном направлении.

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

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

5
задан René Nyffenegger 11 February 2012 в 07:43
поделиться