диграф

График с ориентированными ребрами

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

Описание

Объекты digraph представляют ориентированных графов, которые имеют направленные ребра, соединяющие узлы. После того, как вы создадите объект digraph, можно узнать больше о графике при помощи объектных функций, чтобы выполнить запросы против объекта. Например, можно добавить или удалить узлы или ребра, определить кратчайший путь между двумя узлами или определить местоположение определенного узла или ребра.

G = digraph([1 1], [2 3])
e = G.Edges
G = addedge(G,2,3)
G = addnode(G,4)
plot(G)

Создание

Синтаксис

G = digraph
G = digraph(A)
G = digraph(A,nodenames)
G = digraph(A,NodeTable)
G = digraph(A,___,'omitselfloops')
G = digraph(s,t)
G = digraph(s,t,weights)
G = digraph(s,t,weights,nodenames)
G = digraph(s,t,weights,NodeTable)
G = digraph(s,t,weights,num)
G = digraph(s,t,___,'omitselfloops')
G = digraph(s,t,EdgeTable,___)
G = digraph(EdgeTable)
G = digraph(EdgeTable,NodeTable)
G = digraph(EdgeTable,___,'omitselfloops')

Описание

пример

G = digraph создает пустой объект ориентированного графа, G, который не имеет никаких узлов или ребер.

пример

G = digraph(A) создает взвешенного ориентированного графа с помощью квадратной матрицы смежности, A. Местоположение каждой ненулевой записи в A задает ребро для графика, и вес ребра равен значению записи. Например, если A(2,1) = 10, то G содержит ребро от узла 2 к узлу 1 с весом 10.

пример

G = digraph(A,nodenames) дополнительно задает имена узла. Число элементов в nodenames должно быть равно size(A,1).

G = digraph(A,NodeTable) задает имена узла (и возможно другие атрибуты узла) использование таблицы, NodeTable. Таблица должна иметь одинаковое число строк как A. Задайте имена узла с помощью табличной переменной Name.

пример

G = digraph(A,___,'omitselfloops') игнорирует диагональные элементы A и возвращает график без любых самоциклов. Можно использовать любую из комбинаций входных аргументов в предыдущих синтаксисах.

пример

G = digraph(s,t) задает ребра ориентированного графа (s,t) в парах, чтобы представлять входные и выходные узлы. s и t могут задать индексы узла или имена узла.

пример

G = digraph(s,t,weights) также задает вес ребра с массивом weights.

пример

G = digraph(s,t,weights,nodenames) дополнительно задает имена узла с помощью массива ячеек из символьных векторов или массива строк, nodenames. s и t не могут содержать имена узла, которые не находятся в nodenames.

G = digraph(s,t,weights,NodeTable) задает имена узла (и возможно другие атрибуты узла) использование таблицы, NodeTable. Задайте имена узла с помощью табличной переменной Name. s и t не могут содержать имена узла, которые не находятся в NodeTable.

пример

G = digraph(s,t,weights,num) задает количество узлов в графике с числовым скаляром num.

G = digraph(s,t,___,'omitselfloops') не добавляют никакие самоциклы к графику. Таким образом, любой k, который удовлетворяет s(k) == t(k), проигнорирован. Можно использовать любую из комбинаций входных аргументов в предыдущих синтаксисах.

G = digraph(s,t,EdgeTable,___) использует таблицу, чтобы задать атрибуты ребра вместо того, чтобы задать weights. Вход EdgeTable должен быть таблицей со строкой для каждой соответствующей пары элементов в s и t. Задайте вес ребра с помощью табличной переменной Weight.

пример

G = digraph(EdgeTable) использует таблицу EdgeTable, чтобы задать график. С этим синтаксисом первую переменную в EdgeTable нужно назвать EndNodes, и это должен быть массив 2D столбца, задающий список ребер графика.

пример

G = digraph(EdgeTable,NodeTable) дополнительно задает имена (и возможно другие атрибуты) вершин графика с помощью таблицы, NodeTable.

G = digraph(EdgeTable,___,'omitselfloops') не добавляют самоциклы к графику. Таким образом, любой k, который удовлетворяет EdgeTable.EndNodes(k,1) == EdgeTable.EndNodes(k,2), проигнорирован. Вы должны задать EdgeTable и опционально можете задать NodeTable.

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

развернуть все

Матрица смежности, заданная как полная или разреженная, числовая матрица. Записи в A задают сеть связей (ребра) между вершинами графика. Местоположение каждой ненулевой записи в A задает ребро между двумя узлами. Значение той записи обеспечивает вес ребра. Логическая матрица смежности приводит к невзвешенному графику.

Ненулевые записи на основной диагонали A задают самоциклы или узлы, которые соединяются с собой с ребром. Используйте опцию входа 'omitselfloops', чтобы проигнорировать диагональные элементы.

Пример: A = [0 1 0; 0 0 0; 5 0 0] описывает график с тремя узлами и двумя ребрами. Ребро от узла 1 к узлу 2 имеет вес 1, и ребро от узла 3 к узлу 1 имеет вес 5.

Типы данных: single | double | logical

Имена узла, заданные как массив ячеек из символьных векторов или массив строк. nodenames должен иметь длину, равную numnodes(G) так, чтобы это содержало непустое, уникальное имя для каждого узла в графике.

Пример: G = digraph(A,{'n1','n2','n3'}) задает три имени узла для 3х3 матрицы смежности, A.

Типы данных: cell | string

Входные и выходные пары узла, заданные как индексы узла или имена узла. digraph создает ориентированные ребра между соответствующими узлами в s и t, который должен оба быть числовым, или оба быть векторами символов, массивами ячеек из символьных векторов, категориальными массивами или строковыми массивами. Во всех случаях s и t должны иметь то же число элементов.

  • Если s и t являются числовыми, то они соответствуют индексам вершин графика. Числовые индексы узла должны быть положительными целыми числами, больше, чем или равный 1.

  • Если s и t являются векторами символов, массивами ячеек из символьных векторов или строковыми массивами, то они задают имена для узлов. Свойство Nodes графика является таблицей, содержащей переменную Name с именами узла, G.Nodes.Name.

  • Если s и t являются категориальными массивами, то категории в s и t используются в качестве имен узла в графике. Это может включать категории, которые не являются элементами в s или t.

  • Если s и t задают несколько ребер между теми же двумя узлами, то результатом является мультиграф.

Эта таблица показывает различные способы относиться к одному или нескольким узлам или их числовыми индексами узла или их именами узла.

ФормаОдин узелНесколько узлов
Индекс узла

Скаляр

Пример 1

Вектор

Пример: [1 2 3]

Имя узла

Символьный вектор

Пример: 'A'

Массив ячеек из символьных векторов

Пример: {'A' 'B' 'C'}

Скаляр строки

Пример: "A"

StringArray

Пример: ["A" "B" "C"]

Категориальный массив

Пример: categorical("A")

Категориальный массив

Пример: categorical(["A" "B" "C"])

Пример: G = digraph([1 2 3],[2 4 5]) создает график с пятью узлами и тремя ребрами.

Пример: G = digraph({'Boston' 'New York' 'Washington D.C.'},{'New York' 'New Jersey' 'Pittsburgh'}) создает график с пятью именованными узлами и тремя ребрами.

Вес ребра, заданный как скаляр, вектор, матрица или многомерный массив. weights должен быть скаляром или массивом с тем же числом элементов как s и t.

digraph хранит вес ребра как переменную Weight в таблице свойства G.Edges. Чтобы добавить или изменить веса после создания графика, можно изменить табличную переменную непосредственно, например, G.Edges.Weight = [25 50 75]'.

Если вы задаете weights как пустой массив [], то это проигнорировано.

Пример: G = digraph([1 2],[2 3],[100 200]) создает график с тремя узлами и двумя ребрами. Ребра имеют веса 100 и 200.

Типы данных: single | double

Количество вершин графика, заданных как положительное скалярное целое число. num должен быть больше, чем или равным самым большим элементам в s и t.

Пример: G = digraph([1 2],[2 3],[],5) создает график с тремя связанными узлами и двумя изолированными узлами.

Таблица информации о ребре. Если вы не задаете s и t, то первая переменная в EdgeTable требуется, чтобы быть матрицей 2D столбца, массивом ячеек из символьных векторов или массивом строк под названием EndNodes, который задает ребра графика. Для веса ребра используйте переменную Weight, поскольку это имя табличной переменной используется некоторыми функциями графика. Если существует переменная Weight, то это должен быть числовой вектор-столбец. Смотрите table для получения дополнительной информации о построении таблицы.

После создания графика запросите таблицу информации о ребре с помощью G.Edges.

Пример: EdgeTable = table([1 2; 2 3; 3 5; 4 5],'VariableNames',{'EndNodes'})

Типы данных: table

Таблица информации об узле. NodeTable может содержать любое количество переменных, чтобы описать атрибуты вершин графика. Для имен узла используйте переменную Name, поскольку это имя переменной используется некоторыми функциями графика. Если существует переменная Name, то это должен быть массив ячеек из символьных векторов или массив строк, задающий уникальное имя в каждой строке. Смотрите table для получения дополнительной информации о построении таблицы.

После того, как график создается, запросите таблицу информации об узле с помощью G.Nodes.

Пример: NodeTable = table({'a'; 'b'; 'c'; 'd'},'VariableNames',{'Name'})

Типы данных: table

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

развернуть все

Ориентированный граф, возвращенный как объект digraph. Для получения дополнительной информации смотрите digraph.

Свойства

развернуть все

Ребра графика, возвращенного как таблица. По умолчанию это - M-by-1 таблица, где M является количеством ребер в графике.

  • Чтобы добавить новые свойства ребра в график, создайте новую переменную в таблице Edges.

  • Чтобы добавить или удалить ребра из графика, используйте функции объекта addedge или rmedge.

Пример: G.Edges возвращает таблицу, перечисляющую ребра в графике

Пример: G.Edges.Weight возвращает числовой вектор веса ребра.

Пример: G.Edges.Weight = [10 20 30 55]' задает новый вес ребра для графика.

Пример: G.Edges.NormWeight = G.Edges.Weight/sum(G.Edges.Weight) добавляет новое свойство ребра в таблицу, содержащую нормированные веса ребер.

Типы данных: table

Вершины графика, возвращенного как таблица. По умолчанию это - пустой N-by-0 таблица, где N является количеством узлов в графике.

  • Чтобы добавить новые свойства узла в график, создайте новую переменную в таблице Nodes.

  • Чтобы добавить или удалить узлы из графика, используйте функции объекта addnode или rmnode.

Пример: G.Nodes возвращает таблицу, перечисляющую свойства узла графика. Эта таблица пуста по умолчанию.

Пример: G.Nodes.Names = {'Montana', 'New York', 'Washington', 'California'}' добавляет имена узла в график путем добавления переменной Names в таблицу Nodes.

Пример: G.Nodes.WiFi = logical([1 0 0 1 1]') добавляет переменную WiFi в таблицу Nodes. Это свойство указывает, что определенные аэропорты имеют покрытие беспроводного Интернета.

Типы данных: table

Функции объекта

развернуть все

addedgeДобавьте новое ребро в график
rmedgeУдалите ребро из графика
flipedgeПротивоположные направления ребра
addnodeДобавьте новый узел в график
rmnodeУдаление узла из графика
findedgeНайдите ребро в графике
findnodeНайдите узел в графике
numedgesКоличество ребер в графике
numnodesКоличество узлов в графике
edgecountКоличество ребер между двумя узлами
reordernodesПереупорядочение вершин графика
subgraphИзвлечение подграфа
bfsearchПоиск графика в ширину
dfsearchПоиск графика в глубину
centralityИзмерьте важность узла
toposortТопологический порядок направленного графа без петель
transclosureПереходное закрытие
transreductionПереходное сокращение
isdagОпределите, является ли график нециклическим
conncompКомпоненты связного графа
condensationКонденсация графика
maxflowМаксимальный поток в графике
isisomorphicОпределите, изоморфны ли два графика
isomorphismВычислите изоморфизм между двумя графиками
ismultigraphОпределите, имеет ли график несколько ребер
simplifyУменьшайте мультиграф до простого графика
shortestpathКратчайший путь между двумя одним узлами
shortestpathtreeДерево кратчайшего пути от узла
distancesРасстояния кратчайшего пути всех пар узла
adjacencyМатрица смежности графика
incidenceМатрица падения графика
indegreeВ степени узлов
outdegree-Степень узлов
predecessorsПредшественники узла
successorsПреемники узла
nearestСамые близкие соседи в радиусе
inedgesВходящие ребра к узлу
outedgesИсходящие ребра от узла
plotПостройте вершины графика и ребра

Примеры

свернуть все

Скрипт Open Live Script

Создайте объект digraph с тремя узлами и тремя ребрами. Одно ребро от узла 1 к узлу 2, другой от узла 1 к узлу 3, и третье от узла 2 к узлу 1. 

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

    Edges: [3x1 table]
    Nodes: [3x0 table]

Просмотрите таблицу ребра графика. Для ориентированных графов первый столбец указывает на исходные узлы каждого ребра, и второй столбец указывает на целевые узлы.

G.Edges
ans=3×1 table
    EndNodes
    ________

     1    2 
     1    3 
     2    1

Добавьте имена узла в график, затем просмотрите новый узел и таблицы ребра. Входные и выходные узлы каждого ребра теперь выражаются с помощью их имен узла.

G.Nodes.Name = {'A' 'B' 'C'}';
G.Nodes
ans=3×1 table
    Name
    ____

    'A' 
    'B' 
    'C' 


G.Edges
ans=3×1 table
     EndNodes 
    __________

    'A'    'B'
    'A'    'C'
    'B'    'A'

Можно добавить или изменить дополнительные переменные в таблицах Nodes и Edges, чтобы описать атрибуты вершин графика или ребер. Однако вы не можете непосредственно изменить количество узлов или ребер в графике путем изменения этих таблиц. Вместо этого используйте addedge, rmedge, addnode или функции rmnode, чтобы изменить количество узлов или ребер в графике.

Например, добавьте ребро в график между узлами 2 и 3 и просмотрите новый список ребер.

G = addedge(G,2,3)
G = 
  digraph with properties:

    Edges: [4x1 table]
    Nodes: [3x1 table]


G.Edges
ans=4×1 table
     EndNodes 
    __________

    'A'    'B'
    'A'    'C'
    'B'    'A'
    'B'    'C'
Скрипт Open Live Script

Создайте симметричную матрицу смежности, A, который создает полного ориентированного графа порядка 4. Используйте логическую матрицу смежности, чтобы создать график без весов.

A = ones(4) - diag([1 1 1 1])
A = 4×4

     0     1     1     1
     1     0     1     1
     1     1     0     1
     1     1     1     0


G = digraph(A~=0)
G = 
  digraph with properties:

    Edges: [12x1 table]
    Nodes: [4x0 table]

Просмотрите список ребер графика.

G.Edges
ans=12×1 table
    EndNodes
    ________

     1    2 
     1    3 
     1    4 
     2    1 
     2    3 
     2    4 
     3    1 
     3    2 
     3    4 
     4    1 
     4    2 
     4    3
Скрипт Open Live Script

Создайте матрицу смежности.

A = magic(4);
A(A>10) = 0
A = 4×4

     0     2     3     0
     5     0    10     8
     9     7     6     0
     4     0     0     1

Создайте график с именованными узлами с помощью матрицы смежности. Задайте 'omitselfloops', чтобы проигнорировать записи на диагонали A.

names = {'alpha' 'beta' 'gamma' 'delta'};
G = digraph(A,names,'omitselfloops')
G = 
  digraph with properties:

    Edges: [8x2 table]
    Nodes: [4x1 table]

Просмотрите информация об узле и ребро.

G.Edges
ans=8×2 table
         EndNodes         Weight
    __________________    ______

    'alpha'    'beta'        2  
    'alpha'    'gamma'       3  
    'beta'     'alpha'       5  
    'beta'     'gamma'      10  
    'beta'     'delta'       8  
    'gamma'    'alpha'       9  
    'gamma'    'beta'        7  
    'delta'    'alpha'       4  


G.Nodes
ans=4×1 table
     Name  
    _______

    'alpha'
    'beta' 
    'gamma'
    'delta'
Скрипт Open Live Script

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

s = [1 1 1 2 2 3 3 4 5 5 6 7];
t = [2 4 8 3 7 4 6 5 6 8 7 8];
G = digraph(s,t)
G = 
  digraph with properties:

    Edges: [12x1 table]
    Nodes: [8x0 table]


plot(G,'Layout','force')

Скрипт Open Live Script

Создайте и постройте график куба с помощью списка конечных узлов каждого ребра. Задайте имена узла и вес ребра как отдельные входные параметры.

s = [1 1 1 2 2 3 3 4 5 5 6 7];
t = [2 4 8 3 7 4 6 5 6 8 7 8];
weights = [10 10 1 10 1 10 1 1 12 12 12 12];
names = {'A' 'B' 'C' 'D' 'E' 'F' 'G' 'H'};
G = digraph(s,t,weights,names)
G = 
  digraph with properties:

    Edges: [12x2 table]
    Nodes: [8x1 table]


plot(G,'Layout','force','EdgeLabel',G.Edges.Weight)

Скрипт Open Live Script

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

s = [1 1 1 1 1];
t = [2 3 4 5 6];
weights = [5 5 5 6 9];
G = digraph(s,t,weights,10)
G = 
  digraph with properties:

    Edges: [5x2 table]
    Nodes: [10x0 table]

Постройте график. Дополнительные узлы отключаются от первичного связанного компонента.

plot(G)

Скрипт Open Live Script

Создайте пустой объект диграфа, G.

G = digraph;

Добавьте три узла и три ребра к графику. Соответствующие записи в s и t задают входные и выходные узлы ребер. addedge автоматически добавляет соответствующие узлы в график, если они уже не присутствуют.

s = [1 2 1];
t = [2 3 3];
G = addedge(G,s,t)
G = 
  digraph with properties:

    Edges: [3x1 table]
    Nodes: [3x0 table]

Просмотрите список ребер. Каждая строка описывает ребро в графике.

G.Edges
ans=3×1 table
    EndNodes
    ________

     1    2 
     1    3 
     2    3

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

Скрипт Open Live Script

Составьте таблицу ребра, которая содержит переменные EndNodes, Weight и Code. Затем составьте таблицу узла, которая содержит переменные Name и Country. Переменные в каждой таблице задают свойства вершин графика и ребер.

s = [1 1 1 2 2 3];
t = [2 3 4 3 4 4];
weights = [6 6.5 7 11.5 12 17]';
code = {'1/44' '1/49' '1/33' '44/49' '44/33' '49/33'}';
EdgeTable = table([s' t'],weights,code, ...
    'VariableNames',{'EndNodes' 'Weight' 'Code'})
EdgeTable=6×3 table
    EndNodes    Weight     Code  
    ________    ______    _______

     1    2         6     '1/44' 
     1    3       6.5     '1/49' 
     1    4         7     '1/33' 
     2    3      11.5     '44/49'
     2    4        12     '44/33'
     3    4        17     '49/33'


names = {'USA' 'GBR' 'DEU' 'FRA'}';
country_code = {'1' '44' '49' '33'}';
NodeTable = table(names,country_code,'VariableNames',{'Name' 'Country'})
NodeTable=4×2 table
    Name     Country
    _____    _______

    'USA'     '1'   
    'GBR'     '44'  
    'DEU'     '49'  
    'FRA'     '33'

Создайте график с помощью таблиц ребра и узла. Постройте график с помощью кодов страны в качестве меток ребра и узла.

G = digraph(EdgeTable,NodeTable);
plot(G,'NodeLabel',G.Nodes.Country,'EdgeLabel',G.Edges.Code)

Вопросы совместимости

развернуть все

Поведение изменяется в R2018a

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

|

Темы

Введенный в R2015b

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