-
Notifications
You must be signed in to change notification settings - Fork 56
Open
Labels
difficulty: 0A label for feature requests that should be easyA label for feature requests that should be easyhelp wantedA label for issues or PRs where help is wantedA label for issues or PRs where help is wantednewcomer-friendlyA label for issues that someone thought might be friendly newcomers.A label for issues that someone thought might be friendly newcomers.performanceA label for issues or PR related to performanceA label for issues or PR related to performance
Description
The method for UndirectedSpanningTree
for IsMutableDigraph
creates two undirected spanning forests, but it should be able to get by with creating only one:
Lines 2283 to 2293 in 119adb3
InstallMethod(UndirectedSpanningTree, "for a mutable digraph", | |
[IsMutableDigraph], | |
function(D) | |
if not (DigraphHasAVertex(D) | |
and IsStronglyConnectedDigraph(D) | |
and IsConnectedDigraph(UndirectedSpanningForest(DigraphMutableCopy(D)))) | |
then | |
return fail; | |
fi; | |
return UndirectedSpanningForest(D); | |
end); |
Specifically, an undirected spanning tree is created as part of the big if
statement, and then again at the end.
I believe that eliminating this inefficiency would need only a simple refactoring and should be an doable for a newcomer to Digraphs.
Metadata
Metadata
Assignees
Labels
difficulty: 0A label for feature requests that should be easyA label for feature requests that should be easyhelp wantedA label for issues or PRs where help is wantedA label for issues or PRs where help is wantednewcomer-friendlyA label for issues that someone thought might be friendly newcomers.A label for issues that someone thought might be friendly newcomers.performanceA label for issues or PR related to performanceA label for issues or PR related to performance