Add support for keep_labels in Digraph.strongly_connected_components_digraph

[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

CC: @nathanncohen

Component: graph theory

Keywords: strongly connected components

Author: Nicolas M. Thiéry

Reviewer: Nathann Cohen

Merged: sage-4.7.alpha3

Issue created by migration from https://trac.sagemath.org/ticket/10874

[nathanncohen]

comment:2

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

[nathanncohen]

Attachment: trac_10874-reviewer.patch.gz

[nthiery]

comment:3

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 @nathanncohen:

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).

[jdemeyer]

comment:4

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

[nthiery]

comment:5

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

[nthiery]

comment:6

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.

[nthiery]

Apply only this patch

[nathanncohen]

comment:8

Attachment: trac_10874-graph-strongly_connected_componnents-nt.patch.gz

Good to go !

Nathann

[jdemeyer]

Merged: sage-4.7.alpha3

[jdemeyer]

comment:10

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.