# Shortest-paths algorithms¶

 `seed_competition`(seeds[, image, graph, image_3d]) Performs the shortest path classification from the seeds nodes using the image foresting transform algorithm 1. `dynamic_arc_weight`(seeds, image[, image_3d]) Performs the image foresting transform classification from the seeds nodes with dynamic arc-weights 2.
`pyift.shortestpath.``seed_competition`(seeds: numpy.ndarray, image: Optional[numpy.ndarray] = None, graph: Optional[scipy.sparse.csr.csr_matrix] = None, image_3d: bool = False) → Tuple[numpy.ndarray, numpy.ndarray, numpy.ndarray, numpy.ndarray][source]

Performs the shortest path classification from the seeds nodes using the image foresting transform algorithm 1.

Parameters
• seeds (array_like) – Positive values are the labels and shortest path sources, non-positives are ignored.

• image (array_like, optional) – Image data, seed competition is performed in the image grid graph, mutual exclusive with graph.

• graph (csr_matrix, optional) – Sparse graph, seed competition is performed in the given graph, mutual exclusive with image.

• image_3d (bool, optional) – Indicates if it is a 3D image or a 2D image with multiple bands, by default ‘False’

Returns

Image foresting transform costs, roots, predecessors and labels maps.

Return type

array_like, array_like, array_like, array_like

Examples

Image grid:

```>>> import numpy as np
>>> from pyift.shortestpath import seed_competition
>>>
>>> seeds = np.array([[1, 0, 0],
>>>                   [0, 0, 0],
>>>                   [0, 2, 0]])
>>> image = np.empty((3, 3, 2))
>>> image[:, :, 0] = np.array([[1, 2, 3],
>>>                            [2, 3, 4],
>>>                            [2, 2, 3]])
>>> image[:, :, 1] = np.array([[5, 6, 8],
>>>                            [6, 8, 9],
>>>                            [8, 9, 9]])
>>> seed_competition(seeds, image=image)
```

Sparse graph:

```>>> import numpy as np
>>> from scipy.sparse import csgraph
>>> from pyift.shortestpath import seed_competition
>>>
>>> seeds = np.array([1, 0, 0, 0, 2])
>>> graph = csgraph.csgraph_from_dense([[0, 3, 2, 0, 0],
>>>                                     [3, 0, 0, 3, 1],
>>>                                     [2, 0, 0, 3, 0],
>>>                                     [0, 3, 3, 0, 2],
>>>                                     [0, 1, 0, 2, 0]])
>>> seed_competition(seeds, graph=graph)
```

References

1(1,2)

Falcão, Alexandre X., Jorge Stolfi, and Roberto de Alencar Lotufo. “The image foresting transform: Theory, algorithms, and applications.” IEEE transactions on pattern analysis and machine intelligence 26.1 (2004): 19-29.

`pyift.shortestpath.``dynamic_arc_weight`(seeds: numpy.ndarray, image: numpy.ndarray, image_3d: bool = False) → Tuple[numpy.ndarray, numpy.ndarray, numpy.ndarray, numpy.ndarray, Dict[Tuple, numpy.ndarray]][source]

Performs the image foresting transform classification from the seeds nodes with dynamic arc-weights 2.

Parameters
• seeds (array_like) – Positive values are the labels and shortest path sources, non-positives are ignored.

• image (array_like, optional) – Image data, seed competition is performed in the image grid graph.

• image_3d (bool, optional) – Indicates if it is a 3D image or a 2D image with multiple bands, by default ‘False’

Returns

Image foresting transform costs, roots, predecessors, labels maps and a dictionary containing the average and size of each optimum-path tree.

Return type

array_like, array_like, array_like, array_like, dict

Examples

```>>> import numpy as np
>>> from pyift.shortestpath import dynamic_arc_weight
>>>
>>> seeds = np.array([[1, 0, 0],
>>>                   [0, 0, 0],
>>>                   [0, 2, 0]])
>>> image = np.empty((3, 3, 2))
>>> image[:, :, 0] = np.array([[1, 2, 3],
>>>                            [2, 3, 4],
>>>                            [2, 2, 3]])
>>> image[:, :, 1] = np.array([[5, 6, 8],
>>>                            [6, 8, 9],
>>>                            [8, 9, 9]])
>>> dynamic_arc_weight(seeds, image)
```

References

2(1,2)

Bragantini, Jordão, et al. “Graph-based image segmentation using dynamic trees.” Iberoamerican Congress on Pattern Recognition. Springer, Cham, 2018.