Функции теории графов в Bioinformatics Toolbox™ применяют основные алгоритмы теории графов к разреженным матрицам. Разреженная матрица представляет график, любые ненулевые записи в матрице представляют ребра графика, и значения этих записей представляют связанный вес (стоимость, расстояние, длина или способность) ребра. Алгоритмы графика, которые используют информацию о весе, отменят ребро, если NaN или Inf будут найдены. Алгоритмы графика, которые не используют информацию о весе, рассмотрят ребро, если NaN или Inf будут найдены, потому что эти алгоритмы смотрят только на возможность соединения, описанную разреженной матрицей а не в значениях, сохраненных в разреженной матрице.
Разреженные матрицы могут представлять четыре типа графиков:
Directed Graph — Разреженная матрица, или дважды действительная или логическая. Строка (столбец) индекс указывает на источник (цель) ребра. Самоциклы (значения в диагонали) позволены, несмотря на то, что большинство алгоритмов игнорирует эти значения.
Undirected Graph — Понизьте треугольник разреженной матрицы, или удвойтесь действительный или логический. Алгоритм, ожидающий неориентированного графа, игнорирует значения, сохраненные в верхнем треугольнике разреженной матрицы и значений в диагонали.
Direct Acyclic Graph (DAG) — Разреженная матрица, дважды действительная или логическая, с нулевыми значениями в диагонали. В то время как диагональ с нулевым знаком является требованием DAG, она не гарантирует DAG. Алгоритм, ожидающий DAG, не протестирует на циклы, потому что это добавит нежелательную сложность.
Spanning Tree — Неориентированный граф без циклов и с одним связанным компонентом.
Нет никаких атрибутов, присоединенных к графикам; разреженные матрицы, представляющие все четыре типа графиков, могут быть переданы любому алгоритму графика. Все функции возвратят ошибку на неквадратных разреженных матрицах.
Алгоритмы графика не делают предварительный для свойств графика, потому что такие тесты могут ввести штраф времени. Например, существует эффективный алгоритм поиска кратчайшего пути для DAG, однако тестируя, если график является нециклическим, является дорогим по сравнению с алгоритмом. Поэтому важно выбрать функцию теории графов и свойства, подходящие для типа графика, представленного вашей входной матрицей. Если алгоритм получит тип графика, который отличается от того, что он ожидает, он будет также:
Возвратите ошибку, когда она достигнет несоответствия. Например, если вы передаете циклический график функции graphshortestpath и задаете Acyclic как свойство method.
Приведите к недопустимому результату. Например, если вы передадите ориентированного графа функции с алгоритмом, который ожидает неориентированного графа, это проигнорирует значения в верхнем треугольнике разреженной матрицы.
Функции теории графов включают graphallshortestpaths, graphconncomp, graphisdag, graphisomorphism, graphisspantree, graphmaxflow, graphminspantree, graphpred2path, graphshortestpath, graphtopoorder и graphtraverse.
