Exponenta Banner

самый близкий

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

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

Синтаксис

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

Входные параметры

свернуть все

Входной график, заданный как объект граф или диграф. Используйте граф для создания неориентированного графа или диграф для создания ориентированного графа.

Пример: 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 должен появиться в кавычках. Вы можете задать несколько аргументов в виде пар имен и значений в любом порядке, например: 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
Поддержка