nearest

Самые близкие соседи в радиусе

свернуть все на странице

Синтаксис

nodeIDs = nearest(G,s,d)
nodeIDs = nearest(G,s,d,Name,Value)
[nodeIDs,dist] = nearest(___)

Описание

пример

nodeIDs = nearest(G,s,d) возвращает все узлы в графике G это - на расстоянии d от узла s. Если график взвешивается (то есть, если G.Edges содержит переменную 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). Можно использовать любую из комбинаций входных аргументов в предыдущих синтаксисах.

Примеры

свернуть все

Скрипт Open Live Script

Создайте и постройте график со взвешенными ребрами.

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);

Определите, какие узлы в радиусе 15 от узла 1.

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')

Скрипт Open Live Script

Создайте и постройте график со взвешенными ребрами.

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)

Определите, какие узлы в радиусе 5 от узла 3 и возвращают расстояние до каждого узла.

[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
Скрипт Open Live Script

Создайте и постройте ориентированного графа со взвешенными ребрами.

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)

Определите самые близкие узлы в радиусе 1 от узла 'a', измеренный исходящим расстоянием пути от узла 'a'.

nn_out = nearest(G,'a',1)
nn_out = 3x1 cell array
    {'b'}
    {'c'}
    {'d'}

Определите все узлы, которые имеют входящее продвижение путей к узлу 'a' путем определения радиуса как Inf.

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'
Представьте скалярное имя узла в виде строки"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' опция автоматически выбирает алгоритм:

  • 'unweighted' используется в graph и digraph входные параметры без веса ребра.

  • 'positive' используется во всем graph входные параметры, которые имеют вес ребра и требуют, чтобы веса были неотрицательными. Эта опция также используется в digraph входные параметры с неотрицательным весом ребра.

  • 'mixed' используется в digraph входные параметры, вес ребра которых содержит некоторые отрицательные величины. График не может иметь отрицательных циклов.

'unweighted'

Расчет в ширину, который обрабатывает весь вес ребра как 1.

'positive'

Алгоритм Дейкстры, который требует, чтобы весь вес ребра был неотрицательным.

'mixed' (только для digraph)

Алгоритм Форда Белмана для ориентированных графов, который требует, чтобы график не имел никаких отрицательных циклов.

В то время как 'mixed' медленнее, чем 'positive' для той же проблемы, 'mixed' более универсально, когда это позволяет некоторому весу ребра быть отрицательным.

Примечание

Для большинства графиков, 'unweighted' самый быстрый алгоритм, сопровождаемый 'positive' и 'mixed'.

Пример: nearest(G,s,d,'Method','positive')

Выходные аргументы

свернуть все

Самые близкие соседние идентификаторы узла, возвращенные как индексы узла, если s является числовым, или как имена узла если s имя узла. Узлы сортируются от самого близкого до дальше всего. nodeIDs пусто, если никакие узлы не на заданном расстоянии. nodeIDs никогда не содержит исходный узел s даже если график имеет самоциклы.

Используйте H = subgraph(G,[s; nodeIDs]) извлекать подграф самых близких соседей из исходного графика G.

Соседние расстояния, возвращенные как вектор. dist(j) расстояние от исходного узла s к соседнему узлу nodeIDs(j).

Смотрите также

| | | | |

Темы

Введенный в R2016a

Документация MATLAB
Поддержка
Для просмотра документации необходимо авторизоваться на сайте