lex_BFS method of Graph is not linear as written in the documentation

[cyrilbouvier]

Steps To Reproduce

for i in range(100, 1000, 25):
     G = graphs.CompleteGraph(i) # any infinite family of graphs of increasing size should work
     s = timeit("G.lex_BFS()", seconds=True)
     m = G.size()
     n = G.order()
     print (i, s, s/(m+n))

Expected Behavior

A linear time algorithm as written in the documentation: https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.lex_BFS

The time complexity of this algorithm is in O(n+m)

Actual Behavior

From what I understand (see below) the complexity is at least O(n+m*log(m))

Additional Information

From what I was able to understand, the problem comes from the lex_BFS function. In this function the input graph is converted to a short_digraph by calling init_short_digraph (see here). My claim is that the function init_short_digraph is not linear.
Note that the function lex_BFS_fast_short_digraph doing the actual computation is linear, the problem comes from before, when the graph is converted to the data structure expected by this function.

Looking at the code of init_short_digraph, I found two places where the list of edges is sorted, which imply a complexity of at least m*log(m) [ I only considered the case where the function is called with edge_labelled=False and vertex_list is provided, as in lex_BFS, otherwise more sorting can probably be found ]:

• In line 275, G.edge_iterator(labels=False) is called with the default value for sort_vertices, which is True; this one is easy to fix, using G.edge_iterator(labels=False,sort_vertices=False) should be enough.
• 17 lines below the edges of each vertices are once again sorted; this one is more tricky to remove, because the functions has_edge and triangle_count assumed that the sort is done during initialization.
  In the case of lex_BFS, these two functions are not used, so the sort could be remove.

But even with these two changes:

diff --git a/src/sage/graphs/base/static_sparse_graph.pyx b/src/sage/graphs/base/static_sparse_graph.pyx
index 35f3de67c9..36ed7d6a01 100644
--- a/src/sage/graphs/base/static_sparse_graph.pyx
+++ b/src/sage/graphs/base/static_sparse_graph.pyx
@@ -272,7 +272,7 @@ cdef int init_short_digraph(short_digraph g, G, edge_labelled=False, vertex_list
             g.neighbors[i] = g.neighbors[i - 1] + <int> len(G.edges_incident(vertices[i - 1]))
 
     if not edge_labelled:
-        for u, v in G.edge_iterator(labels=False):
+        for u, v in G.edge_iterator(labels=False,sort_vertices=False):
             i = v_to_id[u]
             j = v_to_id[v]
 
@@ -290,8 +290,8 @@ cdef int init_short_digraph(short_digraph g, G, edge_labelled=False, vertex_list
         g.neighbors[0] = g.edges
 
         # Sorting the neighbors
-        for i in range(g.n):
-            qsort(g.neighbors[i], g.neighbors[i + 1] - g.neighbors[i], sizeof(int), compare_uint32_p)
+        #for i in range(g.n):
+        #    qsort(g.neighbors[i], g.neighbors[i + 1] - g.neighbors[i], sizeof(int), compare_uint32_p)
 
     else:
         from operator import itemgetter

the function does not seem to be linear. I am not able to track where the non linear part is coming from (I suspect from the edge_iterator but I was not able to track it down).

An easy fix would be to add a sort parameter to init_short_digraph to disable all sorting inside this function and use it in lex_BFS. Does this sound like a good idea ? If yes, I could propose a PR.

Environment

- **OS**: Debian
- **Sage Version**: 10.3

Checklist

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

[dcoudert]

You are right, the time complexity of method init_short_digraph is in O(n * log(m) + m) as for each vertex the method sorts the neighbors. Unfortunately, it is not easy to change that. Indeed, some methods assume that the neighbors are sorted. This is for instance the case of method has_edge that performs a binary search in the list of neighbors.
If we stop sorting neighbors, the cost of method has_edge might increase from O(log(m)) to O(m).

I agree with the idea of adding a parameter sort_neighbors to init_short_digraph, with default value True. It must be properly documented and in particular its impact on the complexity of some methods. This parameter must be stored in the data structure in order to use the right method in has_edge (binary search or full scan of the list of neighbors).

Then we will have to check methods using short_digraph. When the order of the neighbors is not taken into account by the algorithm (e.g., no call to has_edge), then we can switch the new parameter to False.

[dcoudert]

I did proposed changes in #37662.

[cyrilbouvier]

Note that the same problem is also present for

• lex_UP method (see source)
• lex_DFS method (see source)
• lex_DOWN (see source)
• diameter method with algorithm='2sweep' (see source)