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: sage-8.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 jmantysalo)

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 jmantysalo

  • Description modified (diff)

comment:2 Changed 2 years ago by dcoudert

  • Authors set to David Coudert
  • Branch set to public/25550_neighbors_nbrs
  • Commit set to 43dff26ea840c965ccac69024130c10339abfce0
  • Status changed from new to needs_review

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


New commits:

43dff26trac #25550: fix iterator_nbrs

comment:3 Changed 22 months ago by git

  • Commit changed from 43dff26ea840c965ccac69024130c10339abfce0 to fc1b7b0609de9369497fd9cdf42c6fd97c952409

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

fc1b7b0trac #25550: Merged with 8.3.rc3

comment:4 Changed 22 months ago by dcoudert

  • Milestone changed from sage-8.3 to sage-8.4

comment:5 Changed 22 months ago by tscrim

  • 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 git

  • Commit changed from fc1b7b0609de9369497fd9cdf42c6fd97c952409 to 508cf3e0abed8594fab8f65dfd3c9ce0db0b9978

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

508cf3etrac #25550: deal with multiedges in neighbor iterators

comment:7 Changed 22 months ago by dcoudert

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 tscrim

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 git

  • Commit changed from 508cf3e0abed8594fab8f65dfd3c9ce0db0b9978 to 8080e05ca9ed2e236ea68e460faa3f7f9a5b3f92

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

8080e05trac #25550: local use of seen

comment:10 Changed 22 months ago by dcoudert

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 tscrim

  • Status changed from needs_review to positive_review

Thanks. LGTM.

comment:12 Changed 22 months ago by dcoudert

Thank you.

comment:13 Changed 22 months ago by vbraun

  • Branch changed from public/25550_neighbors_nbrs to 8080e05ca9ed2e236ea68e460faa3f7f9a5b3f92
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.