id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
16005 Waste of time in iterator_edges 2 ncohen "As reported by Marc in #15978, `iterator_edges` wastes a lot of time. Computationally, returning all edges of a graph currently works this way:
{{{
for each edge E of the graph: # Okay, linear time
# Totally useless
return E
}}}
This can be solved by creating a function that is somehow between
- Returning all neighbors of a vertex (which is not sufficient to find the edges incident to this vertex)
- Work directly with the data structure, i.e. a binary tree
This function is named `out_neighbors_BTNode_unsafe` and does what some part of the code already did, before throwing the information away. It builds the list of `BTNodes` describing the [neighbors of/edges incident to] a vertex, from which all that we need can be deduced.
As a result, the useless computations reported above can be removed.
Nathann" enhancement closed major sage-6.3 graph theory fixed azi mmezzarobba Nathann Cohen Vincent Delecroix N/A 567600b943c81837a5bc525136b55c6f7878327b 567600b943c81837a5bc525136b55c6f7878327b #15978