codegeneration

← →
neuro (2003-06-11 20:54) [0]

Кто-нть сталкивался с проблемой кодегенерации на графе?

Есть граф, он представляет автомат, мы по нему этот автомат в некотором представлении записываем. Это просто. А вот если, граф стягивается по интервалам своим, и надо сквозь этот (итеративный) процесс сделать кодегенерацию..Если ничего не понятно, то могу еще подробнее =).

← →
wicked (2003-06-11 21:46) [1]

задача интересная, но лучше поподробнее.... :)

← →
neuro (2003-06-12 00:30) [2]

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

Выделив интервалы, по ним происходит факторизация. То есть каждый интервал стягивается в вершину, с сохранением всех внешних линков интервала. Потом убиваются self-линки.

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

Дык вот. Этот процесс позволяет представить автомат как несколько вложенных циклов. Вот..И надо по этим всем итерациям (когда граф стягивали) восстановить код автомата, при условии, что код исходного автомата есть..У меня все это сделано, но вот дробящиеся вершины ОЧЕНЬ портят жизнь..Никак не могу справится =(

Если кто знает Tcl/Tk могу выслать на мыло скриптик, который это дело делает и пару примеров..Может укажете, где грабли..

← →
neuro (2003-06-12 18:06) [3]

Ну что? Так никто и не знает? Тогда хоть апну..

← →
neuro (2003-06-13 17:04) [4]

ПИПЛ!!!ГОРЮ!!!ХЕЛП!!!

← →
Soft (2003-06-13 17:41) [5]

Кинь куда-то(на свой сайт) рисунок, того что ты хочешь получить. Понятнее будет.

← →
neuro (2003-06-16 21:32) [6]

Гы.Рисунок могу намылить всем желающим, ибо сайта у мене нету. (тот что есть -- уже не мой). Если на мастерах можно выкладывать что-нть, то могу.

Вкратце. Дан граф:
1
|
2
|\
3 |
/| |
\4/
|
5
(1->2,2->3,3->4,4->2,4->3,4->5). Дуги помечены: 1->2 - d12, и т.п.
Надо что-то типа:
d12
Loop begin;
d23
d34
Loop begin;
Alternative begin;
Alt;
d43
Alt;
d42
break
Alternative end;
Loop end;
Loop end;

Мой пример тривиален =) и он уже реализован. А вот на больших графах все гораздо хуже. Все происходит так. Выделяются некоторые множества в графе (про которые легко проверяется их зацикленность) -- они наз. интервалами. Строим отдельно для каждого интервала свой код примерно так:
INTERVAL1:
d12
TO_INTERVAL2

INTERVAL2:
Loop begin;
d23
TO_INTERVAL3
Loop end;

И т.п. Потом проходимся по интервалам (после факторизации) и правим код - если ссылка на вершину, которая включаена в наш интервал теперь, то ссылку заменяем на код того интервала, куда ссылались, если ссылка на себя, то ее заменяем на continue, иначе переписываем ссылку в соотв. с новыми номерами вершин (от итерации к итерации вершины, вообще говоря, нумеруются по-разному).

Вот. А вот, если разбили вершину, то что делать? Я и так и эдак к этому подходил..Ни в какую..Желающим могу послать исходники моих потуг.Правда они на Tcl.

codegeneration Найти похожие ветки