Opened 6 years ago
Closed 6 years ago
#13785 closed enhancement (fixed)
Export a graph to a dictionary
Reported by: | ncohen | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-5.6 |
Component: | graph theory | Keywords: | |
Cc: | dcoudert | Merged in: | sage-5.6.beta1 |
Authors: | Nathann Cohen | Reviewers: | David Coudert |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #13784 | Stopgaps: |
Description
This can be useful, and it can even be used internally. dictionaries are faster than Sage graphs. We currently use networx to improve speed in some algorithms.
Attachments (1)
Change History (8)
comment:1 Changed 6 years ago by
- Status changed from new to needs_review
Changed 6 years ago by
comment:2 Changed 6 years ago by
comment:3 Changed 6 years ago by
Well. I actually begin to write that after a few seconds over you Suurballe algorithm. I read how it worked on wikipedia, and it looks like you just need to change vertex weights and remove a few edges. This can easily be done with dictionaries too :-)
Of course, if you need to run Dijkstra on the graph afterwards... :-P
But didn't you have a triangle_count code at Python-level which could use this method already ?
Nathann
comment:4 Changed 6 years ago by
In patch #13380, I need to modify a copy of the graph (including weights) and then to compute a shortest path on the modified copy. So turning the graph into a dictionary is not sufficient. Furthermore, since we not only modify the weights, but also the graph topology (addition of reverse arcs), a solution allowing to pass to the shortest path method a dictionary of weights is not sufficient.
For triangle counts (#13503), we can replace
ggnx = self.networkx_graph() for u in ggnx.nodes_iter(): tr += sum(ggnx.has_edge(v,w) for v,w in combinations_iterator(ggnx.neighbors(u),2)) return tr/3
with
gg = self.to_dictionary() for u in gg.iterkeys(): tr += sum(w in gg[v] for v,w in combinations_iterator(gg[u],2)) return tr/3
This will certainly be faster since we don't need edge labels or any other decoration to count.
comment:5 follow-up: ↓ 6 Changed 6 years ago by
- Reviewers set to David Coudert
- Status changed from needs_review to positive_review
The patch is working properly and passes all tests (including docbuild). Loops in digraphs are also properly taken into account.
We shall later use it to speed up some methods (e.g., triangle count)
comment:6 in reply to: ↑ 5 Changed 6 years ago by
Thaaaaaaaaaaaaaaaaaanks !!!
Nathann
comment:7 Changed 6 years ago by
- Merged in set to sage-5.6.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
Hello,
This will certainly be useful when one wants to iterate many times over the neighbors and so. But networkx graphs will remain useful when one wants to modify the graph during the algorithm (remove edge or vertex), unless patch #13730 is able to speed up iterations.
I'm waiting for patch #13784 before starting reviewing this patch.