싱글 엔트리 싱글 출구
Single-entry single-exit수학 그래프 이론에서, 주어진 그래프에서 단일 엔트리 단일 출구(SESE) 영역은 순서 에지 쌍입니다.
예를 들어, 순서 있는 에지 쌍의 경우 (a, b) 개별 제어 흐름 에지 a 및 b의 경우 다음과 같습니다.
- a가 b를 지배하다
- b 포스트도미네이트 a
- a를 포함하는 모든 사이클에는 b도 포함되며 그 반대도 포함됩니다.
여기서 노드 x는 시작부터 y까지의 모든 경로에 x가 포함되어 있는 경우 방향 그래프에서 노드 y를 지배한다고 합니다.노드 x는 y에서 끝까지의 모든 경로에 x가 포함되어 있는 경우 노드 y를 포스트도메이션한다고 합니다.
따라서 a와 b는 각각 입구 및 출구 에지를 나타냅니다.
- 첫 번째 조건은 시작부터 영역까지의 모든 경로가 영역의 입구 가장자리 a를 통과하도록 합니다.
- 두 번째 조건은 영역 내부에서 끝까지 모든 경로가 영역의 출구 가장자리 b를 통과하도록 합니다.
- 첫 번째 두 가지 조건은 필요하지만 SESE 지역을 특징짓기에는 충분하지 않습니다.백백이 우세 또는 포스트 디맨드 관계를 바꾸지 않기 때문에 처음 두 가지 조건만으로는 백백이 지역에 출입하는 것을 금지하지 않습니다.
- 세 번째 조건은 두 가지 제약조건을 인코딩합니다. 영역 내부에서 '위' a로 가는 모든 경로와 '아래' b에서 영역 내부로 가는 모든 경로가 [1]a를 통과합니다.
