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 array
    {'b'}
    {'c'}
    {'d'}

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

nn_in = nearest(G,'a',Inf,'Direction','incoming')
nn_in = 4x1 cell array
    {'b'}
    {'c'}
    {'f'}
    {'e'}

입력 인수

모두 축소

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

예: G = graph(1,2)

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

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

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

예: nearest(G,3,1)

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

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

예: nearest(G,3,1)

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

이름-값 쌍의 인수

선택적으로 Name,Value 인수가 쉼표로 구분되어 지정됩니다. 여기서 Name은 인수 이름이고 Value는 대응값입니다. Name은 따옴표 안에 표시해야 합니다. Name1,Value1,...,NameN,ValueN과 같이 여러 개의 이름-값 쌍의 인수를 어떤 순서로든 지정할 수 있습니다.

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

참고

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

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

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

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

최단 경로 알고리즘으로, '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')

출력 인수

모두 축소

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

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

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

R2016a에 개발됨