Opened 12 years ago
Closed 12 years ago
#9422 closed enhancement (fixed)
Slightly improving is_forest
Reported by: | Nathann Cohen | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-4.6 |
Component: | graph theory | Keywords: | |
Cc: | Robert Miller, Minh Van Nguyen | Merged in: | sage-4.6.rc0 |
Authors: | Nathann Cohen | Reviewers: | Leonardo Sampaio |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
As it is implemented at the moment, the method is_forest creates a new graph for each connected component of the graph, then calls the is_tree method for each of them, which checks again that the connected components are....connected !
We can do it a bit faster :-)
Nathann
Attachments (1)
Change History (10)
Changed 12 years ago by
Attachment: | trac_9422.patch added |
---|
comment:1 Changed 12 years ago by
Status: | new → needs_review |
---|
comment:2 Changed 12 years ago by
comment:3 follow-up: 4 Changed 12 years ago by
See comment 20ff at #9925 for a flaky doctest that #9422 and #10067 should fix.
comment:4 Changed 12 years ago by
comment:5 Changed 12 years ago by
Reviewers: | → Leonardo Sampaio |
---|---|
Status: | needs_review → positive_review |
"Short and useful..." ... and quite easy to review :P
comment:7 Changed 12 years ago by
Authors: | → Nathann Cohen |
---|
comment:8 Changed 12 years ago by
Merged in: | → sage-4.6.rc0 |
---|
comment:9 Changed 12 years ago by
Resolution: | → fixed |
---|---|
Status: | positive_review → closed |
Note: See
TracTickets for help on using
tickets.
Creating a large forest :
Then using two different versions of is_forest
Short and useful... All I love ! :-)
Nathann