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