Opened 6 years ago

Closed 5 years ago

#14690 closed enhancement (invalid)

Useless memory allocation in listing neighbors of a graph

Reported by: vdelecroix Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: graph theory Keywords: sparse graph, allocation
Cc: ncohen Merged in:
Authors: Vincent Delecroix Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by vdelecroix)

This patch exist because I am an idiot. I reviewed #14659 and did not notice that the creation of the list of neighbors actually allocates an array! So #14659 only solves half of the problem.

The patch here remediates to the problem by adding an attribute up for the node of the binary tree (SparseGraphBTNode) that allows to do depth first search without storing anything.

Once #16005 is merged there is no need for that ticket.

Attachments (1)

trac_14690.patch (53.0 KB) - added by vdelecroix 6 years ago.

Download all attachments as: .zip

Change History (12)

comment:1 follow-up: Changed 6 years ago by vdelecroix

  • Description modified (diff)
  • Status changed from new to needs_review

The patch is not yet finished but at least, with it applied, I can build the PetersonGraph and random_stress does not complain ;-)

I would like some comments before going further.

comment:2 in reply to: ↑ 1 Changed 6 years ago by vdelecroix

  • Status changed from needs_review to needs_work

Replying to vdelecroix:

The patch is not yet finished but at least, with it applied, I can build the PetersonGraph and random_stress does not complain ;-)

I would like some comments before going further.

The code to remove an edge does not work (del_arc_unsafe). I have to check it more carefully before asking somebody else to review the patch.

Changed 6 years ago by vdelecroix

comment:3 Changed 6 years ago by vdelecroix

  • Status changed from needs_work to needs_review

All right! After one morning: at least no more memory corruption. I added many comments and documentation in order to be able to reread it later.

Many (~20) doctests now fail in sage.graphs. For some of them is just a matter of the output ordering but for some others it is quite a mystery...

comment:4 follow-up: Changed 6 years ago by ncohen

Well, if doctests fails how can this patch be waiting for a review O_o

By the way, why do you use sys.stdout.write/flush instead of print ?

Nathan

comment:5 in reply to: ↑ 4 Changed 6 years ago by vdelecroix

Replying to ncohen:

Well, if doctests fails how can this patch be waiting for a review O_o

Because I am not used enough with the code of graphs to see if I break something or if something was broken. I am 90% sure of what I have done for SparseGraph and all test passes on sage.graphs.base.sparse_graph.

Needs review for me means that I want that somebody crazy enough spend some time on looking at it.

By the way, why do you use sys.stdout.write/flush instead of print ?

All of them are in comments! The reason is because I want to use flush (print puts the text in the cache not on the screen). If your program crashes few lines after a print then you do not see anything.

comment:6 Changed 6 years ago by vdelecroix

  • Status changed from needs_review to needs_work

All right, I found one concrete problem. With the patch applied

sage: edges = [(1,4),(7,16),(9,11),(11,8),(12,6),(14,5),(5,8),(15,4),(4,10),
....:          (10,6),(6,3),(3,8),(8,16),(16,13),(13,0),(0,2),(2,17)]
sage: G1 = Graph(); G2 = Graph()
sage: G1.add_vertices(range(18))
sage: for e in edges:
....:     G1.add_edge(e); G2.add_edge(e)

Now G1 and G2 should be the same graph but G1 is completely bugged

sage: G1.has_edge(13,16)
True
sage: (13,16) in G1.edges(labels=False)
False

while it works for G2

sage: G2.has_edge(13,16)
True
sage: (13,16) in G2.edges(labels=False)
True

comment:7 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:8 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:9 Changed 5 years ago by vdelecroix

  • Description modified (diff)
  • Milestone changed from sage-6.2 to sage-duplicate/invalid/wontfix
  • Status changed from needs_work to needs_review

comment:10 Changed 5 years ago by ncohen

  • Status changed from needs_review to positive_review

comment:11 Changed 5 years ago by vbraun

  • Resolution set to invalid
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.