graph
Module: graph
| skimage.graph.route_through_array（array，...） | 如何使用MCP和MCP_Geometric类的简单示例。 |
|---|---|
| skimage.graph.shortest_path（arr，reach，...） | 通过nd数组从一边到另一边找到最短路径。 |
| skimage.graph.MCP（成本，抵消...） | 通过给定nd成本数组查找最小成本路径的类。 |
| skimage.graph.MCP_Connect（成本，抵消...） | 使用距离加权最小成本函数连接源点。 |
| skimage.graph.MCP_Flexible（成本，补偿，...） | 通过Nd成本阵列查找最小成本路径。 |
| skimage.graph.MCP_Geometric（费用，...） | 通过nd成本数组查找距离加权的最小成本路径。 |
| skimage.graph.heap | Cython实现一个二进制最小堆。 |
| skimage.graph.mcp | |
| skimage.graph.spath | |
route_through_array
skimage.graph.route_through_array(array, start, end, fully_connected=True, geometric=True)[source]
如何使用MCP和MCP_Geometric类的简单示例。
有关寻路算法的说明，请参阅MCP和MCP_Geometric类文档。
| 参数： | array：ndarray成本数组。start：iterable nd index定义数组起始点end：iterable nd index定义数组定义终点fully_connected：bool（可选）如果为True，则允许对角线移动，如果为False，则只允许轴向移动。geometric：bool（可选）如果为True，则使用MCP_Geometric类来计算成本，如果使用False，则使用MCP基类。有关MCP和MCP_Geometric之间差异的解释，请参阅类文档。 |
|---|---|
| 返回： | path：list定义从开始到结束的路径的nd索引元组列表。成本：float路径的成本。如果几何为False，则路径的成本是路径上数组的值的总和。如果几何为真，则会进行更精细的计算（请参阅MCP_Geometric类的文档）。 |
另请参阅
MCP, MCP_Geometric
例子
>>> import numpy as np
>>> from skimage.graph import route_through_array
>>>
>>> image = np.array([[1, 3], [10, 12]])
>>> image
array([[ 1, 3],
[10, 12]])
>>> # Forbid diagonal steps
>>> route_through_array(image, [0, 0], [1, 1], fully_connected=False)
([(0, 0), (0, 1), (1, 1)], 9.5)
>>> # Now allow diagonal steps: the path goes directly from start to end
>>> route_through_array(image, [0, 0], [1, 1])
([(0, 0), (1, 1)], 9.1923881554251192)
>>> # Cost is the sum of array values along the path (16 = 1 + 3 + 12)
>>> route_through_array(image, [0, 0], [1, 1], fully_connected=False,
... geometric=False)
([(0, 0), (0, 1), (1, 1)], 16.0)
>>> # Larger array where we display the path that is selected
>>> image = np.arange((36)).reshape((6, 6))
>>> image
array([[ 0, 1, 2, 3, 4, 5],
[ 6, 7, 8, 9, 10, 11],
[12, 13, 14, 15, 16, 17],
[18, 19, 20, 21, 22, 23],
[24, 25, 26, 27, 28, 29],
[30, 31, 32, 33, 34, 35]])
>>> # Find the path with lowest cost
>>> indices, weight = route_through_array(image, (0, 0), (5, 5))
>>> indices = np.array(indices).T
>>> path = np.zeros_like(image)
>>> path[indices[0], indices[1]] = 1
>>> path
array([[1, 1, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 1]])
shortest_path
skimage.graph.shortest_path(arr, reach=1, axis=-1, output_indexlist=False)[source]
通过nd数组从一边到另一边找到最短路径。
| 参数： | arr：float64的ndarray达到：int，可选默认情况下（达到= 1），最短路径只能向前或向下移动一行（即路径渐变限制为1）。达到定义可以在每个步骤沿着每个非轴维度跳过的元素的数量。axis：int，可选路径必须始终向前移动的轴（默认为-1）output_indexlist：bool，可选参见返回值p以获取解释。 |
|---|---|
| 返回： | p：iterable int对于沿轴的每一步，最短路径的坐标。如果output_indexlist为True，那么该路径将作为索引到arr的nd元组列表返回。如果为False，则路径以数组的形式返回，列出沿着轴维度的每个步骤沿着非轴维度的路径坐标。也就是说，p.shape ==（arr.shapeaxis，arr.ndim-1）除了p在返回前被挤压，所以如果arr.ndim == 2，则p.shape ==（arr.shapeaxis，）cost：float路径成本。这是沿途所有差异的绝对总和。 |
MCP
class skimage.graph.MCP(costs, offsets=None, fully_connected=True, sampling=None)
Bases: object
通过给定nd成本数组查找最小成本路径的类。
给定一个nd成本数组，该类可用于从任意点集合到任何其他点集合中查找通过该数组的最小成本路径。基本用法是初始化类，并用一个或多个起始索引（以及可选的结束索引列表）调用find_costs()。之后，调用traceback()一次或多次以查找从任何给定结束位置到最接近起始索引的路径。通过重复调用find_costs()可以找到通过相同成本数组的新路径。
路径的成本只是计算路径costs上每个点的数组值。另一方面，MCP_Geometric类考虑到对角线对轴向移动具有不同长度的事实，并相应地对路径成本进行加权。
具有无限或负成本的数组元素将被忽略，其累积成本溢出到无限的路径也将被忽略。
| 参数： | 成本：ndarray偏移量：可迭代，可选偏移量元组列表：每个偏移量指定从给定nd位置的有效移动。如果未提供，则使用make_offsets()使用fully_connected参数值构造与单个或完全连接的nd邻域对应的偏移量。fully_connected：bool，可选如果未提供偏移量，则会确定生成的邻域的连通性。如果为true，则路径可沿着成本数组元素之间的对角线行进; 否则只允许轴向移动。采样：元组，可选对于每个维度，指定两个单元格/体素之间的距离。如果没有给出或无，则距离为假设单位。 |
|---|
属性
| 偏移 | （ndarray）相当于提供给构造函数的偏移量，或者如果没有提供偏移量，则为请求的nd邻域创建偏移量。这些对于解释find_costs()方法返回的跟踪数组非常有用。 |
|---|
__init__(costs, offsets=None, fully_connected=True, sampling=None)
请参阅班级文件。
find_costs()
从给定的起点找到最小成本路径。
此方法从任何一个指定的起始索引中查找指定结束索引的最小成本路径。如果没有给出结束位置，则会找到费用数组中每个位置的最小成本路径。
| 参数： | 开始：iterable nd起始索引列表（其中n是成本数组的维数）。到最近/最便宜起点的最低成本路径将被找到。结束：可迭代，可选结束索引列表。find_all_ends：bool，可选如果为'True'（默认），则会找到每个指定结束位置的最小成本路径; 否则当找到一个路径到任何结束位置时，该算法将停止。（如果没有指定结束，则此参数无效。） |
|---|---|
| 返回： | cumulative_costs：ndarray与费用数组的形状相同; 此数组记录从最近/最便宜的起始索引到每个考虑的索引的最小成本路径。（如果指定了结尾，则并非必须考虑数组中的所有元素：未评估的头寸将具有inf的累积成本。如果find_all_ends为'False'，则只有一个指定的头寸位置具有有限的累积成本。 ）traceback：ndarray与费用数组的形状相同; 此数组包含从其前任索引中的任何给定索引的偏移量。offsetset属性中的偏移索引索引，它是一个偏移量数组。在2-d情况下，如果偏移量[tracebackx，y]为（-1，-1），这意味着在某个起始位置的最小成本路径中x，y的前趋是x + 1，y + 1。请注意，如果offset_index是-1， |
goal_reached()
int goal_reached（int index，float cumcost）在检查邻居之前，从堆中弹出索引之后，每次迭代都会调用此方法。
该方法可以被重载以修改MCP算法的行为。一个例子可能是当达到某个累计成本时，或者当前方距离种子点一定距离时停止算法。
如果算法不应该检查当前点的邻居，那么该方法应该返回1，如果算法现在已经完成，则应该返回2。
traceback(end)
通过预先计算的追踪数组追踪最小成本路径。
这个便利函数从提供给find_costs()的起始索引之一重建到给定结束位置的最小成本路径，该起始索引必须先前已被调用。在find_costs()运行后，可以根据需要多次调用此函数。
| 参数： | end：迭代成本数组中的索引。 |
|---|---|
| 返回： | traceback：nd元组列表成本数组中的索引列表，以传递给find_costs()的开始位置之一开始，以给定的结束索引结束。这些指数指定从任何给定起始索引到结束索引的最小成本路径。（该路径的总成本可以从find_costs()返回的cumulative_costs数组中读出。） |
MCP_Connect
class skimage.graph.MCP_Connect(costs, offsets=None, fully_connected=True)
Bases: skimage.graph._mcp.MCP
使用距离加权最小成本函数连接源点。
同时从每个种子点开始生长正面，同时也跟踪正面的起源。当两条战线相遇时，调用create_connection()。必须重载此方法以适合应用程序的方式处理找到的边。
__init__()
初始化sefl。请参阅帮助（type(self)）以获得准确的签名。
create_connection()
create_connection id1, id2, pos1, pos2, cost1, cost2)
重载此方法以跟踪MCP处理期间发现的连接。请注意，可以多次找到具有相同ID的连接（但具有不同的位置和成本）。
在调用此方法时，两个点都将被“frozen”，并且MCP算法不会再次访问这些点。
| 参数： | id1：int第一个邻居起源的种子点id。id2：int第二个邻居源自的种子点标识。pos1：元组连接中第一个邻居的索引。pos2：元组连接中第二个邻居的索引。cost1：float pos1的累积成本。cost2：float pos2的累计成本。 |
|---|
MCP_Flexible
class skimage.graph.MCP_Flexible(costs, offsets=None, fully_connected=True)
基础： skimage.graph._mcp.MCP
通过Nd成本阵列查找最小成本路径。
有关完整详细信息，请参阅MCP的文档。这个类与MCP的不同之处在于可以重载几个方法（来自纯Python）来修改算法的行为和/或创建基于MCP的自定义算法。请注意，goal_reached也可以在MCP类中过载。
__init__(costs, offsets=None, fully_connected=True, sampling=None)
请参阅类别文件。
examine_neighbor(index, new_index, offset_length)
只要两个节点都被冻结，这种方法就会在每对相邻节点中调用一次。
这种方法可以被重载以获得关于邻居节点的信息，和/或修改MCP算法的行为。一个例子是MCP_Connect类，它使用该钩子检查会议前沿。
travel_cost(old_cost, new_cost, offset_length)
此方法计算从当前节点到下一节点的旅行成本。默认实现返回new_cost。重载此方法以适应算法的行为。
update_node(index, new_index, offset_length)
当更新节点时，在将new_index推入堆并且更新回溯映射之后调用此方法。
可以重载此方法以跟踪算法的特定实现所使用的其他数组。例如MCP_Connect类使用它来更新一个id映射。
MCP_Geometric
class skimage.graph.MCP_Geometric(costs, offsets=None, fully_connected=True)
Bases: skimage.graph._mcp.MCP
通过nd成本数组查找距离加权的最小成本路径。
有关完整详细信息，请参阅MCP的文档。这一类与MCP的不同之处在于，路径的成本不仅仅是沿着该路径的成本的总和。
这个类别假定成本数组在每个位置包含通过该位置的单位行程距离的“成本”。例如，假定从（1,1）到（1,2）的移动（在2-d中）起始于像素（1,1）的中心并终止于（1,2）的中心。整个移动距离为1，半到（1，1）和半到（1，2）; 因此这一举措的成本是(1/2)*costs[1,1] + (1/2)*costs[1,2]。
另一方面，从（1,1）到（2,2）的移动沿着对角线并且是sqrt（2）的长度。这一步的一半是在像素（1,1）内，另一半在（2，2）内，所以这个移动的成本计算为(sqrt(2)/2)*costs[1,1] + (sqrt(2)/2)*costs[2,2]。
这些计算对于幅度大于1的偏移量没有多大意义。使用该sampling参数来处理各向异性数据。
__init__(costs, offsets=None, fully_connected=True, sampling=None)
请参阅类别文件。
