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 )
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)
Change History (12)
comment:1 follow-up: ↓ 2 Changed 6 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 in reply to: ↑ 1 Changed 6 years ago by
- 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
andrandom_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
comment:3 Changed 6 years ago by
- 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: ↓ 5 Changed 6 years ago by
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
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
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
- 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
- Milestone changed from sage-5.11 to sage-5.12
comment:8 Changed 6 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:9 Changed 5 years ago by
- 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
- Status changed from needs_review to positive_review
comment:11 Changed 5 years ago by
- Resolution set to invalid
- Status changed from positive_review to closed
The patch is not yet finished but at least, with it applied, I can build the
PetersonGraph
andrandom_stress
does not complain ;-)I would like some comments before going further.