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,Nathann Cohen,,"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,,Jernej Azarija Marc Mezzarobba,,Nathann Cohen,Vincent Delecroix,N/A,,567600b943c81837a5bc525136b55c6f7878327b,567600b943c81837a5bc525136b55c6f7878327b,#15978,