ВУЗ:
Составители:
лов в шаблоне
p
, которые допускают наличие исходящих дуг. Множества
)(_
pГРАНИЦАВХ
и
)(_ pГРАНИЦАИСХ
представляют входящие и исходящие границы шаблона
p
, т.е. множество узлов внутри
p
, которые могут быть "достигну-
ты" другими узлами извне. Заметим, что по определению входящая граница для w-шаблона не может содержать and-join за-
дачи. Аналогично, исходная граница не может содержать deterministic fork.
Границы могут быть использованы для соединения компонент. Так как дуга соединяет границы двух компонент, доста-
точно уделить все внимание частым дугам и итеративно генерировать новые кандидаты посредством слияния частых компо-
нент, чьи границы соединены посредством этих дуг.
На основе этих идей был разработан алгоритм ("s-поиска"), подробности которого приводятся ниже:
Вход: WF-модель
WS
, множество экземпляров
}...,,{
1 N
IIF
=
для модели
WS
Выход: Множество частых F-шаблонов
Метод:
eEWeeR ,|{: ∈=
является частым шаблоном с учетом
};F
;: RR =∆
Для всех
Eba ∈),(
выполнить
=),(_
babyconnected
∅;
Повторить
Для всех
Aa ∈
выполнить
∈∈= aRpaINF |{:)(
ВХ_ГРАНИЦА(
p
)},
=)(aINFP
∅;
∈∈= aRpaOUTF |{:)(
ИСХ_ГРАНИЦА(
p
)},
=)(aOUTFP
∅;
Конец Для всех;
),(|),{(: babaFA =
является частой дугой с учетом
F
,
/)( =aOUT
∅,
/)( =bINF
∅};
/|{: =∩∪= qpqpFP
∅,
};|,, qpWSRqRp ∪=∆∈∈
Для всех
FAba ∈),(
выполнить
Для всех
)(),(
21
bINFpaOUTFp ∈∈
с учетом
21
),( ppba ∪∉
и
),(_),(
21
babyconnectedpp ∉
выполнить
)},{(:
21
bappq ∪∪=
;
Если
qWS =|
, тогда
};{: qFPFP ∪
ВХ_ГРАНИА(
q
):=
);,,(
21
ppb
orderComputeInB
ИСХ_ГРАНИА(
q
):=
);,,(
21
ppaBorderComputeOut
Для всех
∈a
ВХ_ГРАНИЦА(
q
) выполнить
=:)(aINFP
}{)( qaINF ∪
;
Для всех
∈a
ИСХ_ГРАНИЦА(
q
) выполнить
=:)(aOUTF
=:)(aOUTFP };{)( qaOUTFP ∪
)},{(),(_:),(_
21
ppbabyconnectedbabyconnected ∪=
Конец Если;
Конец Для всех;
|{: FPpR ∈=∆
р-частый с учетом
};F
;: RRR ∆∪=
Пока
=∆R
∅;
Вернуть
R
;
Процедура
);,,(
21
ppborderComputeInB
Если
1)(|)(|
21
−<
∪
bInDegreebInDegree
pp
, тогда
ВХ_ГРАНИЦА
=:
}{b
;
Иначе _ГРАНИЦА
=:
∅;
Для всех
(∈c
ВХ_ГРАНИЦА(
1
p
)
∪
ВХ_ГРАНИЦА(
2
p
))-
}{b
выполнить
Если
|)(|
21
cInDegree
pp ∪
<
)(bInDegree
, тогда ВХ_ГРАНИЦА:= ВХ_ГРАНИЦА
};{c∪
Вернуть ВХ_ГРАНИЦА;
Процедура
);,,(
21
ppaBorderComputeOut
Если
)(|)(|
max
21
aOUTaOutDegree
pp
<
∪
-1, тогда
=:АИСХ_ГРАНИЦ
{a}
, тогда ИСХ_ГРАНИЦА:= ∅;
Для всех
(∈c
ИСХ_ГРАНИЦА(
1
p
)
∪
ИСХ_ГРАНИЦА(
2
p
))-{
a
} выполнить
Если
|)(|
21
cOutDegree
pp ∪
)(
max
aOUT<
, тогда ИСХ_ГРАНИЦА:= ИСХ_ГРАНИЦА
}{c∪
;
Вернуть ИСХ_ГРАНИЦА;
Ядром алгоритма является главный цикл, в котором для каждого узла
WSa ∈
множества
)(aINF
(или
)(aOUTF
) F-
шаблонов, содержащих
a
на входе (или выходе) вычисляются границы. Далее переменные
FA
и
FP
заполняются значе-
ниями частых дуг, которые могут соединить паттерны и кандидатами, которые могут быть получены составлением "совмес-
