Opened 9 years ago

Closed 9 years ago

#9422 closed enhancement (fixed)

Slightly improving is_forest

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-4.6
Component: graph theory Keywords:
Cc: rlm, mvngu 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)

trac_9422.patch (877 bytes) - added by ncohen 9 years ago.

Download all attachments as: .zip

Change History (10)

Changed 9 years ago by ncohen

comment:1 Changed 9 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 9 years ago by ncohen

Creating a large forest :

g = graphs.RandomGNP(300,.1)
g = g.subgraph(edges=g.min_spanning_tree())
g.delete_edges([e for e in g.edges() if random()<.5])
sage: g.sparse6_string()
':~?Ck_O?gF?MAo?_??W@_AC?D`G?oE_I@GU?EE??`s@GCa??gb?[CWQa[BW?ak?wp@AEGt?m@GE_IM_?_A?g?`Y@WA_aOoAcSDHH?QAgGc{CwI`AEgPdS?HW?QCWC_IVOCeCCXc@yAW@e_Axn?U[_DfOAhu?M]?\\fgDX}@y_??`e?Ga_m`o?ggIG@`EGGY_AcOBhK?IT?Ye?I_uAGNhwCwRiC?WGiO?Yf?A?g?ikEIl?]AGAjC@Ir@alOJ_YAwJ_AAGAk?AgF_I?W@\
kW?g@kk@JL?QroN_A?zX?U?WFlw@WAmG@GD`q@Zf?M{?G_y{oa_Q|oO_E~?IoC@KGBfA_@osEw@p??wF_BD?L_rE_?poCk]?NGoCqW?[h?aAWE'

Then using two different versions of is_forest

sage: %timeit g.is_forest()
125 loops, best of 3: 5.06 ms per loop

sage: %timeit g.is_forest()
5 loops, best of 3: 43.8 ms per loop

Short and useful... All I love ! :-)

Nathann

comment:3 follow-up: Changed 9 years ago by mpatel

See comment 20ff at #9925 for a flaky doctest that #9422 and #10067 should fix.

comment:4 in reply to: ↑ 3 Changed 9 years ago by mpatel

Replying to mpatel:

See comment 20ff at #9925 for a flaky doctest that #9422 and #10067 should fix.

I've opened #10081 for this failure.

comment:5 Changed 9 years ago by lsampaio

  • Reviewers set to Leonardo Sampaio
  • Status changed from needs_review to positive_review

"Short and useful..." ... and quite easy to review :P

comment:6 Changed 9 years ago by ncohen

Thanks !!!

Nathann

comment:7 Changed 9 years ago by mpatel

  • Authors set to Nathann Cohen

comment:8 Changed 9 years ago by mpatel

  • Merged in set to sage-4.6.rc0

comment:9 Changed 9 years ago by mpatel

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.