Graph Theory Functions
Graph theory functions in the Bioinformatics Toolbox™ apply
basic graph theory algorithms to sparse matrices. A sparse matrix
represents a graph, any nonzero entries in the matrix represent the
edges of the graph, and the values of these entries represent the
associated weight (cost, distance, length, or capacity) of the edge.
Graph algorithms that use the weight information will cancel the edge
NaN or an
Inf is found.
Graph algorithms that do not use the weight information will consider
the edge if a
NaN or an
found, because these algorithms look only at the connectivity described
by the sparse matrix and not at the values stored in the sparse matrix.
Sparse matrices can represent four types of graphs:
Directed Graph — Sparse matrix, either double real or logical. Row (column) index indicates the source (target) of the edge. Self-loops (values in the diagonal) are allowed, although most of the algorithms ignore these values.
Undirected Graph — Lower triangle of a sparse matrix, either double real or logical. An algorithm expecting an undirected graph ignores values stored in the upper triangle of the sparse matrix and values in the diagonal.
Direct Acyclic Graph (DAG) — Sparse matrix, double real or logical, with zero values in the diagonal. While a zero-valued diagonal is a requirement of a DAG, it does not guarantee a DAG. An algorithm expecting a DAG will not test for cycles because this will add unwanted complexity.
Spanning Tree — Undirected graph with no cycles and with one connected component.
There are no attributes attached to the graphs; sparse matrices representing all four types of graphs can be passed to any graph algorithm. All functions will return an error on nonsquare sparse matrices.
Graph algorithms do not pretest for graph properties because such tests can introduce a time penalty. For example, there is an efficient shortest path algorithm for DAG, however testing if a graph is acyclic is expensive compared to the algorithm. Therefore, it is important to select a graph theory function and properties appropriate for the type of the graph represented by your input matrix. If the algorithm receives a graph type that differs from what it expects, it will either:
Return an error when it reaches an inconsistency. For example, if you pass a cyclic graph to the
graphshortestpathfunction and specify
Produce an invalid result. For example, if you pass a directed graph to a function with an algorithm that expects an undirected graph, it will ignore values in the upper triangle of the sparse matrix.