bug in strongly connected test for static digraphs

[videlec]

sage: G = DiGraph([(0,1),(1,0)])
sage: G2 = G.copy(immutable=True)
sage: G2.is_strongly_connected()
False

The problem comes from bad initialization of some attributes in static sparse backend. We add two lines to fix this problem. We also deprecate four methods of CGraph to simplify its usage (namely _in_degree, _out_degree, _num_verts, _num_arcs).

CC: @dimpase

Component: graph theory

Keywords: bug

Author: Vincent Delecroix

Branch/Commit: dd0a55d

Reviewer: David Coudert

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

[videlec]

comment:1

I guess that there are much more methods that actually do not work. The thing is that there are uninitialized variables used by some of the methods in CGraph that are not initialized by StaticSparseCGraph. In the current case it is num_verts (that is available as self.g.n) and num_arcs (that is available as self.g.m). Adding at the end of __init__.

diff --git a/src/sage/graphs/base/static_sparse_backend.pyx b/src/sage/graphs/base/static_sparse_backend.pyx
index 06b19cf..2a98a96 100644
--- a/src/sage/graphs/base/static_sparse_backend.pyx
+++ b/src/sage/graphs/base/static_sparse_backend.pyx
@@ -95,6 +95,9 @@ cdef class StaticSparseCGraph(CGraph):
         bitset_init(self.active_vertices,  self.g.n+1)
         bitset_set_first_n(self.active_vertices, self.g.n)
 
+        self.num_verts = self.g.n
+        self.num_arcs = self.g.m
+
     def __dealloc__(self):
         r"""
         Freeing the memory

But it looks like more a "work around" than a "real fix".

[dcoudert]

comment:2

At least adding these lines at the end of the init method, with possibly other initialization, we ensure that all backends provide the same information.
I'm surprized none of us noticed that before.
David.

[videlec]

comment:3

There are other weird stuff

sage: G = Graph([(0,1)])
sage: G2 = G.copy(immutable=True)
sage: G2._backend.is_connected()
Traceback (most recent call last):
...
AttributeError: 'sage.graphs.base.static_sparse_backend.StaticSpars'
object has no attribute 'num_edges'

The thing is that it is not clear to me what attributes and methods should be implemented in a new backend.

[dcoudert]

comment:4

Well, at least basic features like number of nodes and edges should be in all backends.

[videlec]

Author: Vincent Delecroix

[videlec]

Commit: cc2217d

[videlec]

New commits:

47ea2c7	Trac 20253: initialize num_verts and num_arcs
cc2217d	Trac 20253: deprecate the "private" CGraph methods

[videlec]

Branch: u/vdelecroix/20253

[dcoudert]

comment:7

the patch is working well and passes but has one doctest error (I tried sage -tp src/sage/graphs/

sage -t src/sage/graphs/base/c_graph.pyx
    Error: Source line number found

certainly due to:
doctest:858: DeprecationWarning: _out_degree is deprecated

David.

[sagetrac-git]

Changed commit from cc2217d to dd0a55d

[sagetrac-git]

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

dd0a55d

Trac 20253: remove a number in doctest

[videlec]

comment:9

That was it! Thanks.

[dcoudert]

comment:10

why are you using notation "Graph size mismatch: %s vs. %s" % (g.num_arcs, randg.size())) instead of "Graph size mismatch: {} vs. {}".format(g.num_arcs, randg.size())) ?

[videlec]

comment:11

I did not change anything there. Just g_num.verts() -> g.num_verts and g._num_arcs() -> g.num_arcs. Though I can use format.

[dcoudert]

comment:12

ok, let it as is.

[dcoudert]

Reviewer: David Coudert

[videlec]

comment:13

Thanks!

[vbraun]

Changed branch from u/vdelecroix/20253 to dd0a55d