의존관계 그래프

이 문서에는 일반적인 참조 목록이 포함되어 있지만 대응하는 충분한 인라인 인용이 없습니다. 좀 더 정밀한 인용문을 도입하여 이 글의 개선에 도움을 주시기 바랍니다.(2013년 6월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인)

수학, 컴퓨터 과학 및 디지털 전자 공학에서, 의존성 그래프는 서로에 대한 여러 개체의 의존성을 나타내는 유향 그래프입니다.의존관계 그래프에서 주어진 의존관계를 존중하는 평가순서 또는 평가순서의 부재를 도출할 수 있다.

정의.

개체 $집합{\displaystyle }$ S$(\displaystyle$ S$)$와 ${\displaystyle (a,}$ b${\displaystyle )}$ ${\displaystyle r}$ R$(\displaystyle (a, b)\in$R$){\displaystyle }$의 종속성을 모델링한 R$$ ×$$S$\times$ $S$가 주어진$$ 경우 $종속성$ "a displaystyle (a, b)\$in$ R"("먼저 평가된 b 요구")는 ${\displaystyle =}$ ${\displaystyle \mathrm{그래프}}$입니다.$$R의$$추이적 $감소를 보여줍니다$$.$

예를 들어 단순한 계산기를 가정해 보겠습니다.이 계산기는 변수에 상수 값을 할당하고 세 번째 변수에 정확히 두 변수의 합계를 할당할 수 있습니다."A = B+C; B = 5+D; C = 4; D = 2$$;"와 같은 여러 방정식이 $주어지면{\displaystyle }$, S${\displaystyle =}${ A${\displaystyle }$, ${\displaystyle B}$, ${\displaystyle C}$ , D$}$ (\$displaystyle$ S = \ { $A$, $B$, C , D $\}$ )와 R${\displaystyle =}$ { (${\displaystyle A}$, B , D ) ${\displaystyle 、D}$ ${\displaystyle 。}$두 변수 모두.따라서 A를 계산하기 전에 B를 계산해야 합니다.단, C와 D의 값은 수치 리터럴이기 때문에 즉시 알 수 있습니다.

불가능한 평가의 인식

의존관계 그래프에서 의존관계 사이클(순환 의존관계라고도 함)은 사이클 내의 어떤 오브젝트도 먼저 평가되지 않기 때문에 유효한 평가순서가 존재하지 않는 상황으로 이어집니다.의존관계 그래프가 원형 의존관계를 가지지 않는 경우, 지향성 비순환 그래프를 형성하고, 위상 정렬에 의해 평가순서를 찾을 수 있다.대부분의 토폴로지 정렬 알고리즘은 입력 사이클도 검출할 수 있지만 검출된 사이클에 적절한 처리를 제공하기 위해 토폴로지 정렬과는 별도로 사이클 검출을 실행하는 것이 바람직할 수 있습니다.

지금까지의 간단한 계산기를 가정해 봅시다.방정식계 "A=B;B=D+C;C=D+A;D=12;"는 A에 앞서 B를 먼저, C를 먼저 평가해야 하므로 A, B, C에 의해 형성된 순환의존성을 포함한다.

평가 순서 도출

$올바른{\displaystyle }$ 평가 순서는 ${\displaystyle n}$: S ${\displaystyle \to }$ \ $displaystyle$ n$:$$의존관계$ 그래프의 노드를 형성하는 객체의 S$\rightarrow \mathbb {N} }$。 () < ( )( ( , )R \ $display style$n ($a$ ) <$n$ ( $b$) \오른쪽 $화살표 (a, b$)\$notin$R $with$ a , ${\displaystyle bs}$S { $displaystyle$a , $b$\ $in$ S$$} 。이것은, 번호가 $2개$의 요소$$a { $displaystyle$a }와$$b { $displaystyle$b$$}의$$ 순서를 지정하면$,$ b { $displaystyle$b $}$보다 먼저 a $style$이 평가되기$$ $때문$에$,$ $b$ $style$에 $의존$하지 않는 것을 의미합니다.$b$

올바른 평가 순서가 여러 개 있을 수 있습니다.사실 올바른 번호는 토폴로지 순서이며 모든 토폴로지 순서는 올바른 번호입니다.따라서 올바른 토폴로지 순서를 도출하는 알고리즘은 올바른 평가 순서를 도출합니다.

다시 한 번 위에서 간단한 계산기를 가정합니다.방정식 시스템 "A = B+C; B = 5+D; C = 4; D = 2;"가 주어진다면, 올바른 평가 순서는 (D, C, B, A)가 될 것이다.단, (C, D, B, A)도 올바른 평가 순서입니다.

모노이드 구조

비순환 의존관계 그래프는 다음과 ^{[1]: 12} 같이 트레이스 모노이드의 트레이스에 대응합니다.

• $A{\displaystyle }$ 함수 ${\displaystyle :}$ : ${\displaystyle S}$ ${\displaystyle \to }$ \ $displaystyle \phi :$S$\to \Sigma }$는 각 정점에 $알파벳{\displaystyle \mathrm{}}${\(\$displaystyle$ \Sigma$)$의 기호를 붙입니다.
• $엣지{\displaystyle }$ a ${\displaystyle \to }$$$ {${\displaystyle \mathrm{displaystyle}}$ a$\to$ b$}$ $또는$ b ${\displaystyle \to }$ {$displaystyle$ b$\to$a}는${\displaystyle }$(${\displaystyle a}$),${\displaystyle }$($)$ {$displaystyle (a)},$ \$phi (b)}$가 $종속관계{\displaystyle }$D {\$displaystyle$ D$\}$에 있는 경우에만 존재합니다.
• 두 그래프는 레이블과 모서리가 일치하는 경우 동일한 것으로 간주됩니다.

그런 다음 올바른 평가 순서로 정렬된 정점 레이블로 구성된 문자열은 트레이스의 문자열에 해당합니다.

단방향 연산$({\displaystyle }$ ${\displaystyle {}_{}}$ ${\displaystyle {12}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}{12}_{}}$ ) ${\displaystyle =}$ ( ${\displaystyle {S\mathrm{}}_{}{}_{}}$ , ${\displaystyle {R\mathrm{}}_{}}$ 1)${\displaystyle {}_{}}$ ( ${\displaystyle {S\mathrm{}}_{}}$2 ,${\displaystyle {}_{}{R\mathrm{}}_{}}$ 2 )$$、 { $displaystyle$($S$_ { $12$, $R$_ { $12$ ) = ($S$_ { 1 } )\ $bullet$( S _ { 2 , R _ { { $}$ )\ ${\displaystyle {}_{}}$ ( $S_$ { 2 , R _ { 2 ${\displaystyle {}_{}}$ 1 ${\displaystyle {}_{}}$ ） ${\displaystyle {}_{}}$ ${\displaystyle {\mathrm{S}}_{}}$ )의존관계에서 ^{[1]: 14} 허용되는 첫 번째 에지에서 두 번째 에지로 새 에지를 만듭니다.

$\displaystyle R_{12}=R_{1}\sqcup R_{2}\sqcup \{(a, b)\mid a\in S_{1}\land b\in S_{2}\land (\phi (a),\phi (b)\in D\})$

ID는 빈 그래프입니다.

예

의존관계 그래프는 다음에서 사용됩니다.

• 자동 소프트웨어 설치:필요한 소프트웨어 패키지는 필요하지만 아직 설치되지 않은 소프트웨어 패키지를 찾습니다.의존성은 패키지의 결합에 의해 부여됩니다.
• Unix Make, Node np install, php composer, Twitter bower install, Apache Ant 등의 소프트웨어 빌드 스크립트.어떤 파일이 변경되었는지 알아야 하기 때문에 올바른 파일만 다시 컴파일하면 됩니다.
• 컴파일러 테크놀로지 및 정식 언어 구현:
  • 명령 스케줄링:의존관계 그래프는 어셈블리 또는 중간 명령의 피연산자에 대해 계산되며 명령의 최적의 순서를 결정하기 위해 사용됩니다.
  • 데드 코드 제거:변수에 의존하는 부작용 동작이 없는 경우 이 변수는 비활성 상태로 간주되어 제거할 수 있습니다.
• 동적^[2] 그래프 분석: GraphBolt 및 KickStarter는^[3] 그래프 구조가 변경되었을 때 증분 컴퓨팅의 가치 종속성을 포착합니다.
• Spreadsheet상에서 계산기였다.그들은 정확한 계산 그 한 예 이 기사에 사용되고 있는 것과 유사한 파생될 필요가 있다.
• XForms 같은 WebForms기준이 시각적 요소를 업데이트할 줄 아는 경우에는 모델 변화에 데이터입니다.
• 자주 장난스런 행동 사이에 종속의 관계를 그래프로 설계된다 비디오 게임, 특히 모험 퍼즐 비디오 게임,.[4]

의 Dependency 그래프 하나이다:.

• 제조업 공장 형식:원료 제품들로 여러개의 의존적 단계를 통해 처리된다.
• Job가게 스케줄링:컴퓨터 과학에 관련 이론적 문제의 컬렉션입니다.

「 」를 참조해 주세요.

• 콜 그래프
• 위상 정렬
• 데이터 의존

레퍼런스

• Balmas, 프랑수아즈(2001년) 의존도 그래프:계층적 접근,[1]wcre 페이지의 주 261, 여덟째 실무 회의 역 공학(WCRE'01)에 보여.