Opened 10 years ago

Closed 10 years ago

Last modified 6 years ago

#10874 closed enhancement (fixed)

Add support for keep_labels in Digraph.strongly_connected_components_digraph

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: sage-4.7.alpha3
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

Attachments (2)

trac_10874-reviewer.patch (1.4 KB) - added by ncohen 10 years ago.
trac_10874-graph-strongly_connected_componnents-nt.patch (3.5 KB) - added by nthiery 10 years ago.
Apply only this patch

Download all attachments as: .zip

Change History (12)

comment:1 Changed 10 years ago by nthiery

  • Status changed from new to needs_review

comment:2 follow-up: Changed 10 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 10 years ago by ncohen

comment:3 in reply to: ↑ 2 Changed 10 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 10 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 10 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

comment:6 Changed 10 years ago by nthiery

  • Status changed from positive_review to needs_work

Ah, Nathann, sorry, while looking back to the patch, I could not resist making the setting of the multiedges option more consistent. Please have a quick check.

comment:7 Changed 10 years ago by nthiery

  • Status changed from needs_work to needs_review

Changed 10 years ago by nthiery

Apply only this patch

comment:8 Changed 10 years ago by ncohen

  • Status changed from needs_review to positive_review

Good to go !

Nathann

comment:9 Changed 10 years ago by jdemeyer

  • Merged in set to sage-4.7.alpha3
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:10 Changed 6 years ago by jdemeyer

Hi, is this a typo?

g = DiGraph({0:{1:"01", 2: "02", 3: 03}, 1: {2: "12"}, 2:{1: "21", 3: "23"}})

Note the missing quotes around 03, which is therefore interpreted as the octal number 3.

Note: See TracTickets for help on using tickets.