is_comparability() fails for immutable graph

[jm58660]

g = DiGraph({0: [1]}, immutable=True)
sage.graphs.comparability.is_comparability(g)

outputs IndexError: list index out of range. Works with immutable=False.

This follows from this:

g = DiGraph({0: [1]}, immutable=True)
print g.neighbors(1)

g = DiGraph({0: [1]}, immutable=False)
print g.neighbors(1)

which outputs 0 and 1.

Component: graph theory

Author: David Coudert

Branch/Commit: 8080e05

Reviewer: Travis Scrimshaw

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

[dcoudert]

Author: David Coudert

[dcoudert]

Commit: 43dff26

[dcoudert]

Branch: public/25550_neighbors_nbrs

[dcoudert]

comment:2

Right, method iterator_nbrs in static_sparse_backend.pyx only considered out neighbors. This should fix it.

---

New commits:

43dff26

trac #25550: fix iterator_nbrs

[sagetrac-git]

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

fc1b7b0

trac #25550: Merged with 8.3.rc3

[sagetrac-git]

Changed commit from 43dff26 to fc1b7b0

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:5

LGTM modulo two trivial things:

• Could you add a test showing the need for the seen set (to help prevent regressions)?
• Why the print in this test: print(g.neighbors_in(1))?

[sagetrac-git]

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

508cf3e

trac #25550: deal with multiedges in neighbor iterators

[sagetrac-git]

Changed commit from fc1b7b0 to 508cf3e

[dcoudert]

comment:7

I have changed the seen data structure. I'm not sure it's best way to do it. May be a set is easier and sufficiently fast here.

One issue I don't know how to solve is: were to free the bitset ? I don't find appropriate dealloc method. Should I add it ?

[tscrim]

comment:8

I don't like how you are using _seen as it gets doubly used: create one iterator, advance it 1 step, then create another iterator and _seen becomes empty. I think you are better defining it local to each function where you free it upon exit.

I also would like to see a test for 0 <-> 1 (an arrow point each way) so that 1 does not appear twice as a neighbor of 0.

[sagetrac-git]

Changed commit from 508cf3e to 8080e05

[sagetrac-git]

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

8080e05

trac #25550: local use of seen

[dcoudert]

comment:10

You are perfectly right. Should be better now. I'm using set again since it might be sufficiently fast here.

[tscrim]

comment:11

Thanks. LGTM.

[dcoudert]

comment:12

Thank you.

[vbraun]

Changed branch from public/25550_neighbors_nbrs to 8080e05