grep-ing for sort() in graphs

[Georgi Guninski]

In a QA attempt I tried to find calling sort() in graphs without
|key|, which may raise exception.

On sage 9.6:

$cd /usr/lib64/python3.11/site-packages/sage/graphs/
$grep -rnI 'sort(' . | grep -v 'key=' | grep -v 'topological'

#15 results


./base/static_sparse_backend.pyx:512: vertices.sort()
./base/static_sparse_graph.pxd:10: void qsort(void *base, int
nmemb, int size,
./base/static_sparse_graph.pyx:293: qsort(g.neighbors[i],
g.neighbors[i+1] - g.neighbors[i], sizeof(int), compare_uint32_p)
./graph_decompositions/vertex_separation.pyx:1841: delta.sort()
./connectivity.pyx:287: c.sort()
./generic_graph.py:3413: multi_edges.sort()
./generic_graph.py:12124: output.sort()
./generic_graph.py:21508: sage: lap.sort(reverse=True)
./generic_graph.py:21521: evals.sort(reverse=True)
./graph.py:2715: e.sort()
./graph_database.py:75: degree_sequence.sort()
./schnyder.py:278: l.sort()
./schnyder.py:427: ones.sort()
./schnyder.py:428: twos.sort()
./schnyder.py:429: threes.sort()

[David Coudert]

Most of these calls are done on purpose and safe, but some may raise an error.

> ./base/static_sparse_backend.pyx:512: vertices.sort() 

It's inside a try ... except...  statement. We may certainly remove it in the future.

> ./base/static_sparse_graph.pxd:10: void qsort(void *base, int  nmemb, int size, 

This is the declaration of a sort method

> ./base/static_sparse_graph.pyx:293: qsort(g.neighbors[i],  g.neighbors[i+1] - g.neighbors[i], sizeof(int), compare_uint32_p) 

Sort integers, so it's OK.

> ./graph_decompositions/vertex_separation.pyx:1841: delta.sort() 

The list delta contains only tuples (int, int), so it's fine.

> ./connectivity.pyx:287: c.sort() 

This one is considered in https://github.com/sagemath/sage/pull/35891

> ./generic_graph.py:3413: multi_edges.sort() 

> ./generic_graph.py:12124: output.sort() 

These two calls mays lead to an error when parameter `sort` is set to `True` by users. We should at least add parameter `key` to the method -> TODO

> ./generic_graph.py:21508: sage: lap.sort(reverse=True) 

Inside a doctest. Done carefully.

> ./generic_graph.py:21521: evals.sort(reverse=True) 

Sorts a list of eigenvalues, so it's fine.

> ./graph.py:2715: e.sort() 

Always sorts integer values. See method  `is_edge_transitive`

> ./graph_database.py:75: degree_sequence.sort() 

Sorts a list of integers (degree sequence), so it's fine.

> ./schnyder.py:278: l.sort() 
> ./schnyder.py:427: ones.sort() 
> ./schnyder.py:428: twos.sort() 
> ./schnyder.py:429: threes.sort() 

I don't know if these calls are safe or not. This code is used only in `src/sage/combinat/interval_posets.py`.

Someone with expertise in this code should certainly improve it to make it safer and more efficient.