search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.47k stars 488 forks source link

GSoC: Edge connectivity and edge disjoint spanning trees in digraphs #33543

Closed enjeck closed 2 years ago

enjeck commented 2 years ago

I'm interested is doing this project as part of GSoC 2022 and this ticket is for discussions about it.

The goal of this project is to implement an algorithm for finding edge disjoint spanning trees in digraphs using the algorithm: Harold N. Gabow: A Matroid Approach to Finding Edge Connectivity and Packing Arborescences. J. Comput. Syst. Sci. 50(2): 259-273 (1995) ​https://doi.org/10.1006/jcss.1995.1022

I'm currently trying to get a feel of the work involved. Here are some comments and questions. Please correct any wrong assumptions:

Component: graph theory

Reviewer: David Coudert

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

enjeck commented 2 years ago

Description changed:

--- 
+++ 
@@ -6,4 +6,5 @@
 - dcoudert already has a Cython implementation ([#32169 comment:40](https://github.com/sagemath/sage/issues/32169#comment:40)) of computing the edge connectivity of a digraph, but it lacks comments and doctests. Since this work has already been done, there's no need to implement the Round Robin algorithm for edge connectivity stated in Gabow's paper, right? So we can just move on to adding the missing comments and doctests?  
 - Continuing from where dcoudert stopped, work on the second part of the paper about extracting the k-edge-disjoint spanning trees.
 - There currently exists an ILP approach for edge-disjoint spanning trees in Sage. Will this be removed or kept for comparison purposes?
+- The description on the ideas page says "The goal of this project is to implement combinatorial algorithms". Since "algorithms" is in plural, does this mean I'll have to find/implement other algorithms apart from Gabow's? 
 - Is there anything else about this project I should know?
enjeck commented 2 years ago

Description changed:

--- 
+++ 
@@ -6,5 +6,5 @@
 - dcoudert already has a Cython implementation ([#32169 comment:40](https://github.com/sagemath/sage/issues/32169#comment:40)) of computing the edge connectivity of a digraph, but it lacks comments and doctests. Since this work has already been done, there's no need to implement the Round Robin algorithm for edge connectivity stated in Gabow's paper, right? So we can just move on to adding the missing comments and doctests?  
 - Continuing from where dcoudert stopped, work on the second part of the paper about extracting the k-edge-disjoint spanning trees.
 - There currently exists an ILP approach for edge-disjoint spanning trees in Sage. Will this be removed or kept for comparison purposes?
-- The description on the ideas page says "The goal of this project is to implement combinatorial algorithms". Since "algorithms" is in plural, does this mean I'll have to find/implement other algorithms apart from Gabow's? 
+- The description on the GSoC ideas page (https://wiki.sagemath.org/GSoC/2022) says "The goal of this project is to implement combinatorial algorithms". Since "algorithms" is in plural, does this mean I'll have to find/implement other algorithms apart from Gabow's? 
 - Is there anything else about this project I should know?
dcoudert commented 2 years ago
comment:3

Welcome to Sagemath.

I don't think this is the best place to comment the project (email ?), but let me give some answers:

enjeck commented 2 years ago
comment:4

Thanks, dcoudert. I'll email you :)

enjeck commented 2 years ago
comment:6

Can someone please close this ticket? Not sure how to do it myself

mkoeppe commented 2 years ago
comment:7

See https://doc.sagemath.org/html/en/developer/trac.html#reviewing-and-closing-tickets

enjeck commented 2 years ago

Changed reviewer from dcoudert to none

dcoudert commented 2 years ago

Author: Enjeck Cleopatra

dcoudert commented 2 years ago

Reviewer: David Coudert

mkoeppe commented 2 years ago

Changed author from Enjeck Cleopatra to none