Opened 7 years ago

Closed 7 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)

trac_13785.patch (6.8 KB) - added by ncohen 7 years ago.

Download all attachments as: .zip

Change History (8)

comment:1 Changed 7 years ago by ncohen

  • Status changed from new to needs_review

Changed 7 years ago by ncohen

comment:2 Changed 7 years ago by dcoudert

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.

comment:3 Changed 7 years ago by ncohen

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 7 years ago by dcoudert

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: Changed 7 years ago by dcoudert

  • 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 7 years ago by ncohen

Thaaaaaaaaaaaaaaaaaanks !!!

Nathann

comment:7 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.6.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.