Opened 2 years ago
Closed 22 months ago
#25550 closed defect (fixed)
is_comparability() fails for immutable graph
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage8.4 
Component:  graph theory  Keywords:  
Cc:  Merged in:  
Authors:  David Coudert  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  8080e05 (Commits)  Commit:  8080e05ca9ed2e236ea68e460faa3f7f9a5b3f92 
Dependencies:  Stopgaps: 
Description (last modified by )
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
.
Change History (13)
comment:1 Changed 2 years ago by
 Description modified (diff)
comment:2 Changed 2 years ago by
 Branch set to public/25550_neighbors_nbrs
 Commit set to 43dff26ea840c965ccac69024130c10339abfce0
 Status changed from new to needs_review
comment:3 Changed 22 months ago by
 Commit changed from 43dff26ea840c965ccac69024130c10339abfce0 to fc1b7b0609de9369497fd9cdf42c6fd97c952409
Branch pushed to git repo; I updated commit sha1. New commits:
fc1b7b0  trac #25550: Merged with 8.3.rc3

comment:4 Changed 22 months ago by
 Milestone changed from sage8.3 to sage8.4
comment:5 Changed 22 months ago by
 Reviewers set to Travis Scrimshaw
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))
?
comment:6 Changed 22 months ago by
 Commit changed from fc1b7b0609de9369497fd9cdf42c6fd97c952409 to 508cf3e0abed8594fab8f65dfd3c9ce0db0b9978
Branch pushed to git repo; I updated commit sha1. New commits:
508cf3e  trac #25550: deal with multiedges in neighbor iterators

comment:7 Changed 22 months ago by
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 ?
comment:8 Changed 22 months ago by
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
.
comment:9 Changed 22 months ago by
 Commit changed from 508cf3e0abed8594fab8f65dfd3c9ce0db0b9978 to 8080e05ca9ed2e236ea68e460faa3f7f9a5b3f92
Branch pushed to git repo; I updated commit sha1. New commits:
8080e05  trac #25550: local use of seen

comment:10 Changed 22 months ago by
You are perfectly right. Should be better now. I'm using set again since it might be sufficiently fast here.
comment:11 Changed 22 months ago by
 Status changed from needs_review to positive_review
Thanks. LGTM.
comment:12 Changed 22 months ago by
Thank you.
comment:13 Changed 22 months ago by
 Branch changed from public/25550_neighbors_nbrs to 8080e05ca9ed2e236ea68e460faa3f7f9a5b3f92
 Resolution set to fixed
 Status changed from positive_review to closed
Right, method
iterator_nbrs
instatic_sparse_backend.pyx
only considered out neighbors. This should fix it.New commits:
trac #25550: fix iterator_nbrs