Fast initialization for edge connectivity

[enjeck]

Related to #33839

Depends on #33839

Component: graph theory

Keywords: GSoC2022

Author: Enjeck Cleopatra

Branch/Commit: 8340185

Reviewer: David Coudert

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

[enjeck]

New commits:

6801eb7	trac #33839: initial commit
6db0026	trac #33839: references and link in documentation
9e08a28	trac #33839: typos
b0ce59e	trac #33839: some reviewers comments
3566e6c	trac #33839: check signals
98136da	Initialize forest
d2aeca8	trac #33839: Merged with 9.7.beta3
a9c7d46	Merge branch 'public/graphs/33839_gabow' of trac.sagemath.org:sage into fast_initialization

[enjeck]

Branch: u/gh-enjeck/34123/fast_initialization

[enjeck]

Commit: a9c7d46

[enjeck]

Dependencies: #33839

[dcoudert]

comment:3

Can you add more comments to better explain the steps.

You define visited as a list. Be aware that with lists, a test like v in visited requires linear time (in the size of the list). You should use a set instead as testing membership to a set requires constant time.

[dcoudert]

Changed keywords from none to GSoC2022

[enjeck]

comment:4

Yeah, I can add more comments. Right, I should be using a set, totally missed that.

By the way, I had been trying to make this ticket's diffs show just my commits, excluding yours from #33839, but I haven't figured out how yet.

[dcoudert]

comment:5

By the way, I had been trying to make this ticket's diffs show just my commits, excluding yours from #33839, but I haven't figured out how yet.

I don't know if it's possible to do that. At least, when #33839 will be merged, it will remain only the diff.

[sagetrac-git]

Changed commit from a9c7d46 to c68ccfc

[sagetrac-git]

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

c68ccfc

Initialization

[enjeck]

comment:7

I'm not sure where I'm going wrong. My DFS initialization is not fast. In fact, it's slower than the implementation without it.

Here are the results of some tests carried out on complete digraphs:

Without initialization

300 vertices
CPU times: user 648 ms, sys: 0 ns, total: 648 ms
Wall time: 646 ms
299

500 vertices
CPU times: user 3.53 s, sys: 8 ms, total: 3.54 s
Wall time: 3.54 s
499

1000 vertices
CPU times: user 29.7 s, sys: 27.2 ms, total: 29.7 s
Wall time: 29.8 s
999

Mine, with initialization

300 vertices
CPU times: user 844 ms, sys: 0 ns, total: 844 ms
Wall time: 841 ms
299

500 vertices
CPU times: user 3.85 s, sys: 7.46 ms, total: 3.85 s
Wall time: 3.84 s
499

1000 vertices
CPU times: user 31.1 s, sys: 3.45 ms, total: 31.1 s
Wall time: 31.2 s
999

[enjeck]

comment:8

I'm obviously missing something. Not sure what :/

[sagetrac-git]

Changed commit from c68ccfc to 9b95c47

[sagetrac-git]

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

9b95c47

Remove unnecessary variable

[dcoudert]

comment:10

Could be because your method is recursive. Can you try a non-recursive DFS ?

Also, have you checked that your method is valid with other types of graphs ?

[enjeck]

comment:11

Could be because your method is recursive. Can you try a non-recursive DFS ?

Okay. I'll try to implement an iterative version.

Also, have you checked that your method is valid with other types of graphs ?

Just did. It works on the Peterson graph, fails on Regular graphs. I get the error message " ValueError: did not find the right edge".

I'll try to fix this and do more extensive testing

[sagetrac-git]

Changed commit from 9b95c47 to 5368f71

[sagetrac-git]

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

5368f71

Replace G_minus_T function with inline code

[enjeck]

comment:13

My latest commit removed the G_minus_T function, and instead updates the current k-1 intersection inline. I expected this to speed up the code a little bit, but that doesn't happen. Instead, it's slower than before. I'm confused

Test results, which are slower than that reported earlier:

500 vertices CPU times: user 5.83 s, sys: 4.03 ms, total: 5.84 s Wall time: 5.84 s 499

1000 vertices CPU times: user 53.4 s, sys: 158 ms, total: 53.5 s Wall time: 54.1 s 999

[enjeck]

comment:14

Also, I haven't yet figured out how to get the code to work on regular graphs. The " ValueError?: did not find the right edge" error stems from the fundamental cycle step, and is linked to the my_depths, my_parent and my_parent_edge vectors. I attempt to fix this by updating these vectors while doing the initalization DFS, compute_dfs_tree(). But this leads to an infinite loop in some other DFS call, update_parents_dfs().

[dcoudert]

comment:15

You never set any edge in T to True...

[sagetrac-git]

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

7984773

Mark (k-1)-intersection edges as True

[sagetrac-git]

Changed commit from 5368f71 to 7984773

[enjeck]

comment:17

Somehow, the code is even slower:

''
500 vertices''
CPU times: user 7.47 s, sys: 31.5 ms, total: 7.5 s
Wall time: 7.53 s
499

1000 vertices
CPU times: user 1min 8s, sys: 71.9 ms, total: 1min 8s
Wall time: 1min 10s
999

I'll get to the bottom of this!

[sagetrac-git]

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

328db20

Allow DFS starting from root_vertex

[sagetrac-git]

Changed commit from 7984773 to 328db20

[sagetrac-git]

Changed commit from 41e006e to 98041eb

[sagetrac-git]

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

9af76d6	trac #34123: merged with 9.8.beta1
98041eb	trac #34123: review commit

[sagetrac-git]

Changed commit from 98041eb to 96e1cd9

[sagetrac-git]

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

96e1cd9

trac #34123: extra care

[dcoudert]

comment:50

I did some minor review edits. Do you agree with these changes ?

[enjeck]

comment:51

Looks good to me!

[dcoudert]

comment:52

So then.

[vbraun]

comment:53

See patchbot:

[sagemath_doc_html-none] OSError: docstring of sage.graphs.edge_connectivity.GabowEdgeConnectivity:19: WARNING: Literal block expected; none found.

[enjeck]

comment:54

Hmm. This is weird. I've checked, and can't seem to find where the error is stemming from. I even tried looking up other tickets where this error showed up (e.g #33971 comment:21) to see how they fixed it, but that doesn't help me here :/

[dcoudert]

comment:55

can you revert this change

-    EXAMPLES:
+    EXAMPLES::

[sagetrac-git]

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

fefa13b

trac #34123: revert a change

[sagetrac-git]

Changed commit from 96e1cd9 to fefa13b

[dcoudert]

comment:57

This should fix the issue. Let's wait to know if the patchbot is happy or not.

[sagetrac-git]

Changed commit from fefa13b to 8340185

[sagetrac-git]

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

8340185

trac #34123: fix doctest

[dcoudert]

comment:59

The docbuild issue is now fixed but the patchbot has reported an error on the doctests using graphs.RandomBarabasiAlbert(100, 2). This is due to the fact that this graph is built starting from a tree, and so there is non zero probability to get a vertex of degree 1 when the graph is small. This is now fixed.

[dcoudert]

comment:60

The patchbot is now happy.

[vbraun]

Changed branch from public/graphs/34123_dfs_init to 8340185