Opened 8 years ago

Closed 8 years ago

# Export a graph to a dictionary

Reported by: Owned by: ncohen jason, ncohen, rlm major sage-5.6 graph theory dcoudert sage-5.6.beta1 Nathann Cohen David Coudert N/A #13784

### 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.

### comment:1 Changed 8 years ago by ncohen

• Status changed from new to needs_review

### comment:2 Changed 8 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 8 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 8 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: ↓ 6 Changed 8 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 8 years ago by ncohen

Thaaaaaaaaaaaaaaaaaanks !!!

Nathann

### comment:7 Changed 8 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.