1 | initial version |

The set of graphs Sage can produce is virtually infinite (depends on your RAM), whereas a hash is a uniformly bounded number. Hence there can not be an injection between them (see e.g. wikipedia).

However, a hash function is assumed to be quite "mixing", so that the probability to get a collision is close to the estimation given by the birthday paradox (see e.g. wikipedia). Hence, unless your graph database is very huge, you can consider that you won't get a collision (or that the number of useless recalculations will be very small).

That said, especially for simple graphs with less than 262143 vertices, there is a compact ASCII representation (which is injective), given by the method `.graph6_string()`

:

```
sage: G = graphs.PetersenGraph()
sage: G.graph6_string()
'IheA@GUAo'
```

2 | No.2 Revision |

The set of graphs Sage can produce is virtually infinite (depends on your RAM), whereas a hash is a uniformly bounded number. Hence there can not be an injection between them (see e.g. wikipedia).

However, a hash function is assumed to be quite "mixing", so that the probability to get a collision is close to the estimation given by the birthday paradox (see e.g. wikipedia). Hence, unless your graph database is very huge, you can consider that you won't get a collision (or that the number of useless recalculations will be very small).

That said, especially for simple graphs with less than 262143 vertices, there is a compact ASCII representation (which is injective), given by the method `.graph6_string()`

:

```
sage: G = graphs.PetersenGraph()
sage: G.graph6_string()
'IheA@GUAo'
```

The hash method seems faster.

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.