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

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

4 голосов
/ 15 марта 2010

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

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

Ответы [ 2 ]

4 голосов
/ 07 апреля 2010

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

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

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

update : Кстати, goto s может тривиально создать 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)
1 голос
/ 15 марта 2010

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

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

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

...