Обеспечиваемая планарность блок-схем

Question

Обеспечиваемая планарность блок-схем

У меня есть вопрос: есть ли ссылка (например, бумага) с доказательством плоскостности макетов блок-схем? Кто-нибудь может предложить алгоритм генерации схем (планарных) макетов?

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

4

algorithm graph graph-theory

Источник

user293722 15 мар '10 в 05:37

2 ответа

Другие вопросы по тегам algorithm graph graph-theory

user162895 07 апр '10 в 14:13 2010-04-07 14:13 · Answer 1 · 2010-04-07 14:13

Я не согласен с Hooked. Блок-схемы с некоторыми ограничениями (использование циклов НЕ является одним из них) являются плоскими. Некоторые примеры:

Одна примитивная команда преобразуется в планарный граф (один узел)
Последовательность операторов: если операторы могут быть переведены в плоские графы, последовательность сама может быть переведена в планарный граф (просто путем соединения этих подграфов)
Функция: такая же, как указано выше
А (repeat-until, while-doи т. д.) цикл - это последовательность операторов, образующая цикл. Циклы тоже хороши, если они правильно вложены (и такие конструкции предназначены для правильного размещения).
Перейти к заявлениям (goto, или же break/continue/return заявления, которые могут прыгать) не в порядке. Если у вас есть вложенный цикл, и изнутри вы выпрыгиваете из внешнего цикла, такой край явно пересекает цикл (цикл, функция), который его содержит. Если код транслируется для выхода по одному циклу за раз, это тоже хорошо. (Этот перевод не слишком отличается от простого введения узлов для моделирования пересечений).

Должен быть более систематический способ формально доказать, что блок-схема, полученная из композиций определенного набора конструкций, является плоской, я хотел бы подумать об этом за 5 минут, но не повезло:)

обновление: кстати, gotoМожно просто создать K3,3 или K5, например, это K5 (в старом добром QBasic!):

00 GOTO (INT(RND * 5) * 10) 
10 GOTO (INT(RND * 5) * 10)
20 GOTO (INT(RND * 5) * 10)
30 GOTO (INT(RND * 5) * 10)
40 GOTO (INT(RND * 5) * 10)

user249341 15 мар '10 в 06:04 2010-03-15 06:04 · Answer 2 · 2010-03-15 06:04

Это зависит от того, что вы называете "блок-схемой". Если блок-схема простой вид, т.е. ориентированный граф, где ни один узел не указывает вверх (на узел, который, возможно, был посещен ранее), тогда вы описали дерево, вложение которого в плоскость тривиально.

Однако, если ваша блок-схема имеет циклы (циклы), тогда просто построить контрпример, график, который нельзя встраивать в плоскость. Для надуманного примера (поскольку никаких ограничений не было указано) рассмотрим полный граф K5, в котором каждый узел связан с любым другим. Этот график не плоский.

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