主要内容

图论函数

生物信息学工具箱™中的图论功能将基本图论算法应用于稀疏矩阵。一个稀疏矩阵表示一个图，矩阵中的任何非零项表示图的边，这些项的值表示边的相关权重(代价、距离、长度或容量)。使用权值信息的图算法将取消边南或者一个正是发现。不使用权值信息的图算法将考虑边缘南或者一个正，因为这些算法只查看稀疏矩阵描述的连通性，而不查看存储在稀疏矩阵中的值。

稀疏矩阵可以表示四种类型的图:

  • 有向图-稀疏矩阵，无论是双实或逻辑。行(列)索引表示边缘的源(目标)。自循环(对角线上的值)是允许的，尽管大多数算法都会忽略这些值。

  • 无向图-一个稀疏矩阵的下三角形，要么双实要么逻辑。一个期望无向图的算法忽略了存储在稀疏矩阵的上三角形和对角线上的值。

  • 直接无环图(DAG)-稀疏矩阵，双实或逻辑，对角线上为零值。虽然零值对角线是DAG的要求，但它并不能保证DAG的存在。一个期待DAG的算法会不测试循环，因为这会增加不必要的复杂性。

  • 生成树-无环且只有一个连通分量的无向图。

图上没有附加属性;表示所有四种图类型的稀疏矩阵可以传递给任何图算法。所有函数都会在非平方稀疏矩阵上返回错误。

图算法不会对图属性进行预测试，因为这样的测试可能会带来时间损失。例如，DAG有一种有效的最短路径算法，但是与该算法相比，测试图是否为无环的代价昂贵。因此，选择一个适合输入矩阵所表示的图的类型的图论函数和属性是很重要的。如果算法接收到与预期不同的图类型，它将:

  • 当它达到不一致时返回错误。例如，如果将循环图传递给graphshortestpath函数和指定无环随着方法财产。

  • 产生无效的结果。例如，如果您将一个有向图传递给一个函数，该函数的算法期望得到一个无向图，那么它将忽略稀疏矩阵的上三角形中的值。

另请参阅

|||