Revision history [back]
 | 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.
