Arborescence packing with Gabow DFS

[264c63e9-79e4-426c-ab2d-7ce38c7c4a27]

Expansion of graphs module edge connectivity to include packing arborescences.

CC: @dcoudert

Component: graph theory

Keywords: GSoC2022

Author: Georgia Channing

Branch/Commit: public/graphs/34230_arborescence_packing_with_gabow_dfs @ 0e93fe6

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

[dcoudert]

Changed dependencies from #33839 to none

[dcoudert]

comment:1

Since #33839 has been merged in 9.7.beta6, we don't need the dependency.

[264c63e9-79e4-426c-ab2d-7ce38c7c4a27]

Branch: /public/graphs/34230_arbor

[264c63e9-79e4-426c-ab2d-7ce38c7c4a27]

Changed branch from /public/graphs/34230_arbor to none

[264c63e9-79e4-426c-ab2d-7ce38c7c4a27]

Branch: public/graphs/34230_arborescence_packing_with_gabow_dfs

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Commit: ec29d54

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

fd4ba5c	infrastructure for packing gabow dfs
ec29d54	infrastructure for packing arborescences

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from ec29d54 to 11d4e1c

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

b742c7c	build out period step and find tree
11d4e1c	80%+ implemented

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 11d4e1c to 378989c

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

51713ff	tuesday 11:46 pm
db9fe28	tuesday 11:46 pm
378989c	writing to trac, 95% but still not compiling

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 378989c to 5efa917

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

79939e4	trac #34230: Merged with 9.7.rc0
5efa917	trac #34230: less compilation errors

[dcoudert]

comment:10

I did a few edits to reduce the number of compilation errors. However I cannot do more yet as for several variables, I don't know what's the goal of the variables, what it should contain (e.g., array A), it's expected size (e.g., root_size is used as a 2 dimensional array but was defined as one dimensional array. The second dimension must be initialized).

So please add more useful comments. May be some variables should be vectors and not arrays, etc.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

aee14a4	stashing
5314800	testing with deletions
c919631	moving enjeck
e2de4cb	it compiles

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 5efa917 to e2de4cb

[dcoudert]

comment:12

• The commits contains file src/sage/graphs/edge_connectivity.pyx copy which should not be here.
• may be you should not build your ticket with the data from #34123. We can figure out later how to merge the modifications.
• I don't understand method G_minus_A. If I understand well, it does nothing

The good news is that you are able to compile ;)

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

e7ecb76

doc strings

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e2de4cb to e7ecb76

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e7ecb76 to 44b3612

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

44b3612

new dfs, but no g minus a

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

0e93fe6

remove copy

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 44b3612 to 0e93fe6