nearest

반지름 내 최근접이웃

구문

nodeIDs = nearest(G,s,d)

nodeIDs = nearest(G,s,d,Name,Value)

[nodeIDs,dist] = nearest(___)

설명

nodeIDs = nearest(G,s,d)는 그래프 G에서 노드 s로부터의 거리 d 내에 있는 모든 노드를 반환합니다. 그래프가 가중 그래프인 경우(즉, G.Edges가 변수 Weight를 포함한 경우) 해당 가중치(Weight)가 그래프에서 간선의 거리로 사용됩니다. 가중 그래프가 아닌 경우에는 모든 간선 거리가 1로 처리됩니다.

nodeIDs = nearest(G,s,d,Name,Value)는 하나 이상의 이름-값 쌍의 인수로 지정된 추가 옵션을 사용합니다. 예를 들어, G가 가중 그래프이면 nearest(G,s,d,'Method','unweighted')가 그래프 G의 간선 가중치를 무시하고, 그 대신 모든 간선 가중치를 1로 처리합니다.

[nodeIDs,dist] = nearest(___)는 각 최근접이웃까지의 거리를 추가로 반환하며, dist(j)는 소스 노드 s에서 노드 nodeIDs(j)까지의 거리입니다. 위에 열거된 구문에 나와 있는 입력 인수를 원하는 대로 조합하여 사용할 수 있습니다.

예제

가장 가까운 노드

가중치 간선이 있는 그래프를 생성하고 플로팅합니다.

s = [1 1 1 1 1 2 2 2 3 3 3 3 3];
t = [2 4 5 6 7 3 8 9 10 11 12 13 14];
weights = randi([1 10],1,13);
G = graph(s,t,weights);
p = plot(G,'Layout','force','EdgeLabel',G.Edges.Weight);

노드 1부터 반지름 15 이내에 있는 노드를 확인합니다.

nn = nearest(G,1,15)

nn = 9×1

     5
     7
     2
     3
     4
     6
     8
    12
     9

소스 노드는 녹색으로, 최근접이웃은 빨간색으로 강조 표시합니다.

highlight(p,1,'NodeColor','g')
highlight(p,nn,'NodeColor','r')

가장 가까운 노드의 거리

가중치 간선이 있는 그래프를 생성하고 플로팅합니다.

s = [1 1 1 2 2 6 6 7 7 3 3 9 9 4 4 11 11 8];
t = [2 3 4 5 6 7 8 5 8 9 10 5 10 11 12 10 12 12];
weights = [10 10 10 10 10 1 1 1 1 1 1 1 1 1 1 1 1 1];
G = graph(s,t,weights);
plot(G,'EdgeLabel',G.Edges.Weight)

노드 3부터 반지름 5 이내에 있는 노드를 확인하고, 각 노드까지의 거리를 반환합니다.

[nn,dist] = nearest(G,3,5)

nn = 9×1

     9
    10
     5
    11
     4
     7
    12
     6
     8

dist = 9×1

     1
     1
     2
     2
     3
     3
     3
     4
     4

유방향 그래프의 들어오는 이웃 거리

가중치 간선이 있는 유방향 그래프를 생성하고 플로팅합니다.

s = {'a' 'a' 'a' 'b' 'c' 'c' 'e' 'f' 'f'};
t = {'b' 'c' 'd' 'a' 'a' 'd' 'f' 'a' 'b'};
weights = [1 1 1 2 2 2 2 2 2];
G = digraph(s,t,weights);
plot(G,'EdgeLabel',G.Edges.Weight)

노드 'a'부터 반지름 1 이내에 있는 가장 가까운 노드를 확인합니다. 노드 'a'에서 나가는 경로 거리로 측정합니다.

nn_out = nearest(G,'a',1)

nn_out = 3x1 cell
    {'b'}
    {'c'}
    {'d'}

반지름을 Inf로 지정하여 노드 'a'로 들어오는 경로가 있는 모든 노드를 확인합니다.

nn_in = nearest(G,'a',Inf,'Direction','incoming')

nn_in = 4x1 cell
    {'b'}
    {'c'}
    {'f'}
    {'e'}

입력 인수

G — 입력 그래프

graph 객체 | digraph 객체

입력 그래프로, graph 객체 또는 digraph 객체로 지정됩니다. 무방향 그래프를 생성하려면 graph를 사용하고 유방향 그래프를 생성하려면 digraph를 사용하십시오.

예: G = graph(1,2)

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

s — 소스 노드

노드 인덱스 | 노드 이름

소스 노드로, 다음 표에 있는 형식 중 하나로 된 노드 인덱스 또는 노드 이름으로 지정됩니다.

값	예제
스칼라 노드 인덱스	1
문자형 벡터 노드 이름	'A'
string형 스칼라 노드 이름	"A"

예: nearest(G,3,1)

예: nearest(G,'a',5)

d — 이웃 거리 반지름

스칼라

이웃 거리 반지름으로, 숫자형 스칼라로 지정됩니다.

예: nearest(G,3,1)

예: nearest(G,'a',2.5)

이름-값 인수

선택적 인수 쌍을 Name1=Value1,...,NameN=ValueN으로 지정합니다. 여기서 Name은 인수 이름이고 Value는 대응값입니다. 이름-값 인수는 다른 인수 뒤에 와야 하지만, 인수 쌍의 순서는 상관없습니다.

R2021a 이전 릴리스에서는 쉼표를 사용하여 각 이름과 값을 구분하고 Name을 따옴표로 묶으십시오.

예: [nodeIDs,dist] = nearest(G,s,5,'Method','unweighted','Direction','incoming')

Direction — 거리 측정 방향

'outgoing' (디폴트 값) | 'incoming'

참고

'Direction' 옵션은 유방향 그래프에서만 지정할 수 있습니다.

거리 측정 방향으로, 'Direction'과 함께 다음 표에 나와 있는 옵션 중 하나가 쉼표로 구분되어 지정됩니다.

옵션	설명
'outgoing'(디폴트 값)	소스 노드 s에서 밖으로 나가는 경로를 사용하여 거리가 계산됩니다.
'incoming'	소스 노드 s에서 안으로 들어오는 경로를 사용하여 거리가 계산됩니다.

예: nearest(G,s,d,'Direction','incoming')

Method — 최단 경로 알고리즘

'auto' (디폴트 값) | 'unweighted' | 'positive' | 'mixed'

최단 경로 알고리즘으로, 'Method'와 함께 아래 표에 나와 있는 옵션 중 하나가 쉼표로 구분되어 지정됩니다.

옵션	설명
'auto'(디폴트 값)	'auto' 옵션은 다음과 같이 알고리즘을 자동으로 선택합니다. 간선 가중치가 없는 graph 입력값과 digraph 입력값에는 'unweighted'가 사용됩니다. 음수가 아닌 간선 가중치를 갖는 모든 graph 입력값에는 'positive'가 사용됩니다. 이 옵션은 음수가 아닌 간선 가중치를 갖는 digraph 입력값에도 사용됩니다. 음수 값을 일부 포함하는 간선 가중치를 갖는 digraph 입력값에는 'mixed'가 사용됩니다. 그래프는 음의 순환(Negative Cycle)을 가질 수 없습니다.
'unweighted'	모든 간선 가중치를 1로 처리하는 너비 우선 계산입니다.
'positive'	모든 간선 가중치가 음수가 아니어야 하는 데이크스트라 알고리즘(Dijkstra Algorithm)입니다.
'mixed'(digraph에만 해당)	그래프에 음의 순환을 허용하지 않는 유방향 그래프에 대한 벨만-포드 알고리즘(Bellman-Ford Algorithm)입니다. 'mixed'는 동일한 문제에 대해 'positive'보다 속도가 느리지만, 'mixed'는 일부 간선 가중치에 음수 값을 사용할 수 있으므로 더 유연합니다.

참고

대부분의 그래프에 대해 'unweighted' 알고리즘이 가장 빠르며, 그다음이 'positive', 'mixed' 순입니다.

예: nearest(G,s,d,'Method','positive')

출력 인수

nodeIDs — 최근접이웃 노드 ID

노드 인덱스 | 노드 이름

최근접이웃 노드 ID로, s가 숫자인 경우 노드 인덱스로 반환되거나 s가 노드 이름인 경우 노드 이름으로 반환됩니다. 노드는 가장 가까운 곳부터 가장 먼 곳으로 정렬됩니다. nodeIDs는 지정된 거리 내에 노드가 없는 경우 비어 있습니다. 그래프에 자가 루프가 있는 경우에도 nodeIDs에는 소스 노드 s가 포함되지 않습니다.

원래 그래프 G에서 최근접이웃의 부분 그래프를 추출하려면 H = subgraph(G,[s; nodeIDs])를 사용합니다.

dist — 이웃 거리

벡터

이웃 거리로, 벡터로 반환됩니다. dist(j)는 소스 노드 s부터 인접 노드 nodeIDs(j)까지의 거리입니다.

확장 기능

C/C++ 코드 생성

MATLAB® Coder™를 사용하여 C 코드나 C++ 코드를 생성할 수 있습니다.

사용법 관련 참고 및 제한 사항:

• 이름 값 인수는 상수여야 합니다.

• 'positive', 'unweighted' 및 'auto' 방법만 지원됩니다.

스레드 기반 환경
MATLAB®의 backgroundPool을 사용해 백그라운드에서 코드를 실행하거나 Parallel Computing Toolbox™의 ThreadPool을 사용해 코드 실행 속도를 높일 수 있습니다.

버전 내역

R2016a에 개발됨

참고 항목

shortestpath | distances | shortestpathtree | neighbors | successors | predecessors

도움말 항목

• graph
• digraph