Note

This is the documentation for the current state of the development branch of rustworkx. The documentation or APIs here can change prior to being released.

rustworkx.hyperbolic_greedy_routing#

hyperbolic_greedy_routing(graph, pos, source, destination)#

Performs the greedy routing algorithm from source to destination using the hyperbolic distance.

The greedy routing algorithm attempts to find the shortest path between source and destination by starting from source and continuously going to the neighbor closest to destination. The closest neighbor of \(u\) is the node \(v\) that minimizes the hyperbolic distance

\[d(u,v) = \text{arccosh}\left[x_0(u) x_0(v) - \sum_{j=1}^D x_j(u) x_j(v) \right],\]

where \(D\) is the dimension of the hyperbolic space and \(x_d(u)\) is the \(d\) th-dimension coordinate of node \(u\) in the hyperboloid model. The distance is computed using pos, an array of shape (n, D) in which the \(i\)-th row is the position of the \(i\) -th indexed vertex in the graph. The dimension is inferred from the coordinates pos and the 0-dimension “time” coordinate is inferred from the other coordinates. Note that the hyperbolic space is at least 2 dimensional.

Note

Node indices are constant across removal of nodes. Since pos maps rows to node indices, the unused rows should not be deleted.

This algorithm has a time complexity of \(O(m)\) for \(m\) edges.

Parameters:

  • graph (PyGraph) – The input graph.

  • pos (list[list[float]]) – Hyperboloid coordinates of the nodes [[\(x_1(1)\), …, \(x_D(1)\)], [\(x_1(2)\), …, \(x_D(2)\)], …]. The “time” coordinate \(x_0\) is inferred from the other coordinates.

  • source (int) – source of the greedy routing path.

  • destination (int) – destination of the greedy routing path.

Returns:

A tuple (path, length) where path is the path followed and length is the sum of the distance between nodes on the path. Returns None if the greedy algorithm fails. to reach destination.

Return type:

Optional[tuple[list[int], float]]