condensation

그래프 응축

구문

C = condensation(G)

설명

C = condensation(G)는 노드가 G의 강한 연결성분을 나타내는 유방향 그래프 C를 반환합니다. 이러한 축약은 성분 간의 연결에 대한 간소화된 보기를 제공합니다.

예제

강한 연결성분을 단일 노드로 응축하기

여러 개의 강한 연결성분을 포함하는 그래프를 만들고 플로팅합니다. 강한 연결성분을 강조 표시합니다.

s = [1 1 2 3 3 4 4 4 4 5 5 6 6 6 7 8 8 9 9 10 10 10 11 11 12 13 13 14 15];
t = [1 3 1 2 5 1 2 12 13 6 8 7 8 10 10 9 10 5 11 9 11 14 12 14 13 11 15 13 14];
G = digraph(s,t);
p = plot(G);

bins = conncomp(G);
p.MarkerSize = 7;
p.NodeCData = bins;
colormap(hsv(4))

condensation을 사용하여 각 성분을 단일 노드로 나타냅니다. 해당 노드가 나타내는 성분에 따라 노드 색을 지정합니다.

C = condensation(G);
p2 = plot(C);
p2.MarkerSize = 7;
p2.NodeCData = 1:4;
colormap(hsv(4))

입력 인수

G — 입력 그래프

digraph 객체

입력 그래프로, digraph 객체로 지정됩니다. digraph를 사용하여 유방향 graph 객체를 생성할 수 있습니다.

예: G = digraph([1 2],[2 3])

출력 인수

C — 응집 그래프

digraph 객체

응집 그래프로, digraph 객체로 반환됩니다. C는 DAG(유방향 비순환 그래프)이고 위상 정렬됩니다. C의 노드 수는 conncomp로 반환되는 Bin 번호에 해당합니다.

condensation은 성분별로 C의 노드와 간선을 확인하고 G의 연결을 확인합니다.

• C는 G의 강한 연결성분 각각에 대한 노드를 포함합니다.

• 성분 I의 노드에서 G의 성분 J에 있는 노드까지 간선이 있는 경우 C는 노드 I와 노드 J 사이의 간선을 포함합니다.

버전 내역

R2016b에 개발됨

참고 항목

conncomp | bctree

도움말 항목

• 유방향 그래프와 무방향 그래프
• 너비 우선 탐색(Breadth-First Search)과 깊이 우선 탐색(Depth-First Search) 시각화하기