ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 29 Jul 2014 09:49:27 +0200How to use Sage to find a pair of vertex-disjoint paths of minimal total length?https://ask.sagemath.org/question/23609/how-to-use-sage-to-find-a-pair-of-vertex-disjoint-paths-of-minimal-total-length/I want to find a pair of vertex-disjoint (s,t)-paths with minimal total length in a graph G, where the length is the sum of the edge weights of the paths. For this I would like to use the [Suurballe and Tarjan Algorithm](http://en.wikipedia.org/wiki/Suurballe%27s_algorithm"), but it seems to be a hidden (if I am right?) method. Is there any way I can still use this algorithm other than reprogram it myself?Mon, 28 Jul 2014 15:15:00 +0200https://ask.sagemath.org/question/23609/how-to-use-sage-to-find-a-pair-of-vertex-disjoint-paths-of-minimal-total-length/Answer by Nathann for <p>I want to find a pair of vertex-disjoint (s,t)-paths with minimal total length in a graph G, where the length is the sum of the edge weights of the paths. For this I would like to use the <a href="http://en.wikipedia.org/wiki/Suurballe%27s_algorithm">Suurballe and Tarjan Algorithm</a>, but it seems to be a hidden (if I am right?) method. Is there any way I can still use this algorithm other than reprogram it myself?</p>
https://ask.sagemath.org/question/23609/how-to-use-sage-to-find-a-pair-of-vertex-disjoint-paths-of-minimal-total-length/?answer=23615#post-id-23615The easiest seems to rewrite this problem as an integer linear program. Mon, 28 Jul 2014 18:00:12 +0200https://ask.sagemath.org/question/23609/how-to-use-sage-to-find-a-pair-of-vertex-disjoint-paths-of-minimal-total-length/?answer=23615#post-id-23615Comment by Bart for <p>The easiest seems to rewrite this problem as an integer linear program. </p>
https://ask.sagemath.org/question/23609/how-to-use-sage-to-find-a-pair-of-vertex-disjoint-paths-of-minimal-total-length/?comment=23621#post-id-23621This would indeed be my next step, but I hoped that the Suurballe and Tarjan algorithm would work. It would save some time. Thank you for your suggestion.Tue, 29 Jul 2014 09:48:41 +0200https://ask.sagemath.org/question/23609/how-to-use-sage-to-find-a-pair-of-vertex-disjoint-paths-of-minimal-total-length/?comment=23621#post-id-23621Answer by slelievre for <p>I want to find a pair of vertex-disjoint (s,t)-paths with minimal total length in a graph G, where the length is the sum of the edge weights of the paths. For this I would like to use the <a href="http://en.wikipedia.org/wiki/Suurballe%27s_algorithm">Suurballe and Tarjan Algorithm</a>, but it seems to be a hidden (if I am right?) method. Is there any way I can still use this algorithm other than reprogram it myself?</p>
https://ask.sagemath.org/question/23609/how-to-use-sage-to-find-a-pair-of-vertex-disjoint-paths-of-minimal-total-length/?answer=23614#post-id-23614Suurballe and Tarjan's algorithm is the object of [Sage trac ticket #13380](http://trac.sagemath.org/ticket/13380), which has not made its way into Sage yet. You could try applying the patches found at that ticket. Maybe your question will revive the work on that ticket.
Mon, 28 Jul 2014 17:52:17 +0200https://ask.sagemath.org/question/23609/how-to-use-sage-to-find-a-pair-of-vertex-disjoint-paths-of-minimal-total-length/?answer=23614#post-id-23614Comment by Bart for <p>Suurballe and Tarjan's algorithm is the object of <a href="http://trac.sagemath.org/ticket/13380">Sage trac ticket #13380</a>, which has not made its way into Sage yet. You could try applying the patches found at that ticket. Maybe your question will revive the work on that ticket.</p>
https://ask.sagemath.org/question/23609/how-to-use-sage-to-find-a-pair-of-vertex-disjoint-paths-of-minimal-total-length/?comment=23622#post-id-23622Hm, I was already afraid of that. Thank you for clarification.Tue, 29 Jul 2014 09:49:27 +0200https://ask.sagemath.org/question/23609/how-to-use-sage-to-find-a-pair-of-vertex-disjoint-paths-of-minimal-total-length/?comment=23622#post-id-23622