Problem Description

The problem we are seeking to solve with this feature request is the absence of a "power" function in the SageMath library for graph theory. In graph theory, a branch of mathematics, the kth power G^k of an undirected graph G is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in G is at most k.

Proposed Solution

One implementation for the power of the graph is a brute-force one that computes the shortest distances between all pairs of nodes using Breadth-First Search (BFS).

Alternatives Considered

The above approach is inefficient for large graphs and results in a time complexity of O(n^3) in the worst case, where n is the number of vertices in the graph. This can be a performance bottleneck when working with graphs of significant size.

Some optimization methods:

• For unweighted graphs, we can utilize matrix exponentiation techniques to compute the kth power of the graph efficiently.
• For weighted graphs, we can adapt the Floyd-Warshall algorithm to compute all-pairs shortest paths efficiently and then construct the kth power graph based on these shortest paths.

Additional Information

No response

Is there an existing issue for this?

• I have searched the existing issues for a bug report that matches the one I want to file, without success.