Алгоритм для рисования графика

Question

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

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

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

Было легко придумать «формулу», которая возвращает координату X: каждый уровень, который мы делаем глубже в графе/дереве, мы продвигаемся по оси X.

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

Answer 1

Получение координат X и Y для большинства общих случаев построения графика - непростая задача.

Возможно, вы захотите ознакомиться с некоторыми инструментами с открытым исходным кодом, чтобы узнать, как они это делают.

Graphviz имеет некоторые хорошие алгоритмы для разметки http://www.graphviz.org/

Antlr является еще одним http://www.antlr.org/