종속성 그래프에서 추가 충돌 정보를 확인하는 방법은 무엇입니까?

Question

일련의 항목에 대한 종속성 그래프가있는 경우 그래프에 순환이 포함되어 있는지 확인하기 위해 표준 주제별 정렬을 수행 할 수 있습니다. 주기가 있으면 다른 것을 위반하지 않고 만족할 수없는 종속성이 있습니다.

하지만 충돌 정보는 어떻게됩니까?

 
V - a set of items 
E - a set of dependency edges: E\subset V\times V 
C - a set of conflict edges: C\subset V\times V 

종속성 그래프가 만족 될 수없는 충돌 정보가 포함되어 있는지 확인하는 표준 알고리즘은 무엇입니까 : 나는 당신이 가지고있는 구조를 의미? 예를 들어

: 그것은 c가 a와 a 주어진 c의 존재 충돌로 지정되는 동시에 의존한다는 것을 이해할 수 없기 때문

 
V = { a, b, c } 
E = { (a -> b), (b->c) } 
C = { (a -> c) } 

이 예 약해서 종속성 그래프이다.

이러한 모델의 실례로는 패키지 관리자가 있습니다. 여기에는 패키지 설명에 종속 및 충돌 사양이 포함될 수 있습니다. 또 다른 예는 충돌하는 작업이 이미 실행중인 경우에만 작업을 시작할 수있는 종속성 기반 실행 서비스입니다.

Answer 1

나는 표준 알고리즘 모르는

하지만,이 작품 :

1. 평소와 같이 (V,E)의 위상 ​​종류를 찾기 (순환 종속성이 발견 경우 불안정 반환).
2. DFS/BFS 방식에서는 각 종속성 흔적/구성 요소에 고유하게 레이블을 지정합니다 (아래 설명 참조).
3. 트래버스 C 및 label(u) = label(v)과 같은 쌍 (u,v)가 존재하지 않는지 확인하십시오. 그러한 쌍이있는 경우 ==> 불안정한 반환, 그렇지 않으면 ==> 반환 안정. 실행 시간 O(|E|+|V|+|C|)

:
위상 정렬 DFS 보낸 (V,E) 선형이며, 세 번째 부분 C 선형이다. 2 단계의

설명 :

우리는 종속성 그래프 상단에서 시작 (또는 당신이 좋아하는 경우에, 위상 종류의 시작), 첫 번째 노드, 그리고 첫 번째 레이블을 선택, 1 말 . 그래프의 각 에지를 DFS (또는 BFS) 방식으로 트래버스합니다. 여전히 연결되어있는 한 동일한 레이블을 가진 노드를 계속 레이블링합니다. 연결이 끊어 지 자마자 레이블을 증가시키고 DFS/BFS에서 계속 진행합니다.

e.e. 첫 번째 노드에서 도달 할 수있는 모든 것은 1입니다. 노드의 도달 가능성 (DFS 또는 BFS 알고리즘의 외부 루프)이 없어지면 레이블을 증가시키고 검색되지 않은 다음 노드를 선택합니다.정확성의

증명 :

우리는 하나 개의 키 관찰을 - C 등이 label(u) = label(v)의 일부 쌍 (u,v)이 존재 IFF에 그래프가 불안정이다.

우선 대칭이 있기 때문에, 우선은 C의 요소를 언급하지 않습니다. (u -> v)이 C 인 경우 즉, u, v이 주어지지 않는다는 의미입니다. 따라서 그들은 함께 존재할 수 없습니다. 즉 u은 에 종속 될 수 없으므로 (u이 존재하기 때문에 v이 존재해야하며 이는 불가능합니다) 또는 그 반대가 아닙니다. 우리는 위의 관찰을 입증 할 수있는 이해와

:
우리는 label(u) = label(v) u 두 경우가 v에 의존, 또는 다른 방법으로 주위 있습니다. 이것은 도달 가능성 (따라서 의존성)이 레이블을 정의한 간단한 구성 결과입니다. 따라서 우리가 그러한 쌍을 가정한다면, 그래프는 불안정합니다 (위의 단락에서 설명했듯이).

관찰의 다른 방향 (불안정한 == 쌍)도 쉽게 볼 수 있습니다. 그래프가 불안정하다고 가정하면 u이 존재할 수 없습니다. 이 u은 충돌하는 항목에 종속되어 있거나 다른 노드가 이에 종속되어 있고 그 쌍이 충돌합니다. 어느 쪽이든, 같은 레이블을 가진 (u,v)이 C에 있습니다.