lex_BFS method of DiGraph is not well-defined (the method could compute ordering that fails doctests)

[cyrilbouvier]

Steps To Reproduce

Load the content of the function _is_valid_lex_BFS_order from graphs/traversals.pyx, then run

sage: _is_valid_lex_BFS_order(DiGraph([(0,1), (0,2), (1, 2)]), [1,0,2])
sage: _is_valid_lex_BFS_order(Graph([(0,1), (0,2), (1, 2)]), [1,0,2])

Expected Behavior

True
True

Actual Behavior

False
True

Additional Information

As the code is written, it is not clear what is the semantic of a lexBFS ordering for directed graphs (DiGraph).

In the lex_BFS method in graphs/traversals.pyx, the graph is first converted to a simple undirected graph, via the hidden default parameter to_undirected=True of the call to the to_simple method of those lines

if G.has_loops() or G.has_multiple_edges():
  G = G.to_simple(immutable=False)

It seems to indicate that directed graphs are considered as undirected for lexBFS.
The doctest of the function strengthens this impression

r"""
    Lex BFS ordering of a symmetric digraph should be the same as the Lex BFS
    ordering of the corresponding undirected graph::
"""

But, in the function _is_valid_lex_BFS_order that is used in doctests, directed graphs are considered directed, as shown by the use of the methods G.neighbor_in_iterator and G.has_edge that are direction-dependent.

So it is possible to build graphs where the lexBFS ordering computed by lex_BFS is not considered valid.

What should be the fix ?
My first impulse would be to do the two following changes in _is_valid_lex_BFS_order:

• use G.neighbor_iterator for Graph and DiGraph
• use G.has_edge(u,v) or G.has_edge(v,u)

Is it the correct approch ?

I am very interested by the response as I am currently writing an extended lexBFS algorithm, and I would like to be able to rely on this function to test the output of the new implementation.

Environment

- **OS**: Debian 11
- **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]

Thanks for reporting this issue.
Indeed, lex_BFS returns an ordering on the underlying undirected graph (this should be clearly documented), but _is_valid_lex_BFS_order considers something else.
You can do the modifications you proposed in _is_valid_lex_BFS_order as this is an internal method used only to check the output of lex_BFS. As long are we are consistent, this is ok.

[cyrilbouvier]

Thanks for reporting this issue. Indeed, lex_BFS returns an ordering on the underlying undirected graph (this should be clearly documented), but _is_valid_lex_BFS_order considers something else. You can do the modifications you proposed in _is_valid_lex_BFS_order as this is an internal method used only to check the output of lex_BFS. As long are we are consistent, this is ok.

I writing the PR but I may have found errors in the doctests (I am still new to graph theory so it may be a misunderstanding from my part).
In the doctests of _is_valid_lex_BFS_order, there is the following check:

         sage: G = DiGraph("I?O@??A?CCA?A??C??")
         sage: _is_valid_lex_BFS_order(G, [0, 7, 1, 2, 3, 4, 5, 8, 6, 9])
         True

But from what I understand of lex_BFS ordering [0, 7, 1, 2, 3, 4, 5, 8, 6, 9] is not a valid lex_BFS order for the undirected graph corresponding to G: 2 is an isolated vertex but 8 and 5 are neighbors of 7 and 1, so 2 must appear after them in the lex_BFS order.
Can anyone confirm this ?

The problem is that with Sage 10.4.beta9, the output of G.lex_BFS() (which is [0, 7, 2, 3, 4, 5, 1, 8, 6, 9]) is, with the same reasoning as above, not a valid lex_BFS order.
So the following statements from the docs may be wrong

r"""
    Lex BFS ordering of a symmetric digraph should be the same as the Lex BFS
    ordering of the corresponding undirected graph::
"""

[cyrilbouvier]

I think I found a problem in the lex_BFS code for Digraph. Consider the following example:

sage: G = DiGraph("I?O@??A?CCA?A??C??")
sage: G.lex_BFS()
[0, 7, 2, 3, 4, 5, 1, 8, 6, 9] # not valid
sage: G.allow_loops(True)
sage: G.add_edge(0,0)
sage: G.lex_BFS()
[0, 7, 1, 8, 5, 4, 3, 2, 6, 9] # valid

The problem comes from the following lines

    # Loops and multiple edges are not needed in Lex BFS
    if G.has_loops() or G.has_multiple_edges():
        G = G.to_simple(immutable=False)

The graph is converted to undirected graph only if it has loops or multiedges. Otherwise the conversion never happens and the algorithm is applied to a directed graph (so only out_neighbors are considered for DiGraph).

If someone confirm my reasoning, I will include the fix in my PR and update the wrong doctests.

[dcoudert]

You are right, this is a bug when considering digraphs. A simple fix is to use:

    # Loops and multiple edges are not needed in Lex BFS
    if G.is_directed() or G.has_loops() or G.has_multiple_edges():
        G = G.to_simple(to_undirected=True, immutable=False)

The alternative is to avoid the conversion to short_digraph, but I don't know if the resulting code will be as fast...

The same fix should certainly be done in all lex_* methods.

Note also that parameter immutable could be True as G is not modified.

[cyrilbouvier]

I just open PR #38269

The alternative is to avoid the conversion to short_digraph, but I don't know if the resulting code will be as fast...

I think it will be faster to avoid the conversion to short_digraph (there would be one enumeration of the edges instead of two). But I kept this change for another PR.