Дан связный направленный граф (E,V), где E - множество узлов и V - множество ребер. Пусть имеется подграф (F, W) со следующими свойствами 1) F содержит единственный "входной узел"(entry point) A. То есть все ребра из E\F в F имеют своей целью A. Для любого узла C, принадлежащего F, существует путь из A в C. 2) Cуществует такой узел B из E\F, что все ребра из F в E\F имеют своей целью B. 3) F минимален относительно A. То есть при удалении любых (одного или нескольких) узлов из F за исключением A теряется минимум одно из первых двух свойств Назовем такой подграф узлом второго порядка. Теперь собственно сам вопрос: как наиболее быстро найти все узлы второго порядка в заданном графе?
Непонятно свойство 3) - как, например, при удалении узлов из F может потеряться свойство 2) ? Уж если 2) выполняется, то удали хоть весь F, оно по-прежнему будет выполняться (для пустого множества ребер). А вообще поиск F лучше начать с поиска вершин A и B. Они обладают уникальным свойством - их удаление нарушает связность графа...
RElf Если взять например граф с узлами 1,2,3,4 и ребрами 1->2, 1->3, 2->4, 3->4. Пусть 1 будет A. В качестве F можно взять подграф 1,2,3 c ребрами 1->2, 1->3. То есть 4 будет B. Теперь если удалить из F узел 2, то второе условие будет нарушено(ребра 1->2 и 3->4 ведут наружу, B не существует). Вроде так? Ага, A и B - это пары доминатор/постдоминатор для F. Но это не достаточное условие, только необходимое. Получается, что надо строить сначала все такие пары, а потом проверять их на пригодность? В принципе наверное все уже поняли, куда я клоню Такой узел второго порядка - это отображение statement'a, языковой конструкции высокого уровня(if,for и т.д.) на control flow graph. Хочется применить подобное разложение графа в процессе написания декомпилятора.
