Opened 11 years ago

Last modified 7 years ago

#10874 closed enhancement

Add support for keep_labels in Digraph.strongly_connected_components_digraph — at Version 5

Reported by: nthiery Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-4.7
Component: graph theory Keywords: strongly connected components
Cc: ncohen Merged in:
Authors: Nicolas M. Thiéry Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by nthiery)

With keep_labels=True, the method Digraph.strongly_connected_components_digraph keeps the label on edges when contracting strongly connected components, and returns a multi-digraph::

            sage: g = DiGraph({0:{1:"0-12", 2: "0-12", 3: "0-3"}, 1: {2: "1-2", 3: "1-3"}, 2:{1: "2-1", 3: "2-3"}})
            sage: scc_digraph = g.strongly_connected_components_digraph(keep_labels = True)
            sage: scc_digraph.edges()
            [({0}, {3}, "0-3"), ({0}, {1, 2}, '0-12'),
             ({1, 2}, {3}, '1-3'), ({1, 2}, {3}, '2-3'),
             ({1, 2}, {1, 2}, '1-2'), ({1, 2}, {1, 2}, '2-1')]

Apply: trac_10874-graph-strongly_connected_componnents-nt.patch

Change History (6)

comment:1 Changed 11 years ago by nthiery

  • Status changed from new to needs_review

comment:2 follow-up: Changed 11 years ago by ncohen

  • Description modified (diff)

What about avoiding to test "keep_labels" twice ? :-)

Here is a reviewer patch which does just that. Your patch is good to go, so you can set this ticket to "positive review" if you agree with my modifications, and also if you don't for some reason (please update the "apply" section in this case) :-)

Nathann

Changed 11 years ago by ncohen

comment:3 in reply to: ↑ 2 Changed 11 years ago by nthiery

  • Status changed from needs_review to positive_review

Hi Nathann,

Wow, that was a quick review! This patch has been basically ready in the queue since last July; it was time for me to post in on trac :-)

Thanks!

Replying to ncohen:

What about avoiding to test "keep_labels" twice ? :-)

That was to avoid having g.add_vertices(scc_set) twice :-) But it's probably more readable as you did it.

Here is a reviewer patch which does just that. Your patch is good to go, so you can set this ticket to "positive review" if you agree with my modifications, and also if you don't for some reason (please update the "apply" section in this case) :-)

Positive review it is (assuming of course the patch bot confirms that everything is good; it should).

comment:4 Changed 11 years ago by jdemeyer

Please change the commit message of trac_10874-graph-strongly_connected_componnents-nt.patch to something human-readable (make sure to include the ticket number of the first line).

comment:5 Changed 11 years ago by nthiery

  • Description modified (diff)

Oops; I need to recheck my workflow; I forgot this way too many times lately. Sorry!

While I was at it, I folded the two patches together. No other changes.

trac_10874-reviewer.patch can now be deleted from trac.

Cheers,

Nicolas

Note: See TracTickets for help on using tickets.