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