ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 20 Apr 2013 02:26:51 -0500Generating a unique file name for each graphhttp://ask.sagemath.org/question/10040/generating-a-unique-file-name-for-each-graph/I am writing a function whose input is a graph and some other data. I would like to store the computations that this program does each time it is run in a file with one file for each graph, so that, the next time it is run, it need not recalculate the calculations it has already done. In order to do this, I would like to assign a unique file name to each graph. I was thinking of using the hash function of the combinatorial object constructed from the graph to generate file names: `CombinatorialObject(G).__hash__()`
I have two questions:
1. Will this always work (the function taking a graph to this hash is well-defined and injective)?
2. Is there a better way to do this?
Thu, 18 Apr 2013 22:52:38 -0500http://ask.sagemath.org/question/10040/generating-a-unique-file-name-for-each-graph/Comment by fidbc for <p>I am writing a function whose input is a graph and some other data. I would like to store the computations that this program does each time it is run in a file with one file for each graph, so that, the next time it is run, it need not recalculate the calculations it has already done. In order to do this, I would like to assign a unique file name to each graph. I was thinking of using the hash function of the combinatorial object constructed from the graph to generate file names: <code>CombinatorialObject(G).__hash__()</code></p>
<p>I have two questions:</p>
<ol>
<li><p>Will this always work (the function taking a graph to this hash is well-defined and injective)?</p></li>
<li><p>Is there a better way to do this?</p></li>
</ol>
http://ask.sagemath.org/question/10040/generating-a-unique-file-name-for-each-graph/?comment=17848#post-id-17848I get the impression that `CombinatorialObject(G)` just captures the vertex set of `G`. Eg
sage: CombinatorialObject(graphs.PetersenGraph()).__hash__()
4020364995504644057
sage: CombinatorialObject(graphs.CycleGraph(10)).__hash__()
4020364995504644057
Perhaps using a database would be an alternative for this? You can use the graph6 string of the canonically labelled graph for querys. I've used mongodb with sage and it works pretty well.Fri, 19 Apr 2013 07:29:25 -0500http://ask.sagemath.org/question/10040/generating-a-unique-file-name-for-each-graph/?comment=17848#post-id-17848Comment by Amri for <p>I am writing a function whose input is a graph and some other data. I would like to store the computations that this program does each time it is run in a file with one file for each graph, so that, the next time it is run, it need not recalculate the calculations it has already done. In order to do this, I would like to assign a unique file name to each graph. I was thinking of using the hash function of the combinatorial object constructed from the graph to generate file names: <code>CombinatorialObject(G).__hash__()</code></p>
<p>I have two questions:</p>
<ol>
<li><p>Will this always work (the function taking a graph to this hash is well-defined and injective)?</p></li>
<li><p>Is there a better way to do this?</p></li>
</ol>
http://ask.sagemath.org/question/10040/generating-a-unique-file-name-for-each-graph/?comment=17841#post-id-17841@fidelbc Thanks for the comments, and bringing MongoDB to my attention.Sat, 20 Apr 2013 02:26:51 -0500http://ask.sagemath.org/question/10040/generating-a-unique-file-name-for-each-graph/?comment=17841#post-id-17841Answer by tmonteil for <p>I am writing a function whose input is a graph and some other data. I would like to store the computations that this program does each time it is run in a file with one file for each graph, so that, the next time it is run, it need not recalculate the calculations it has already done. In order to do this, I would like to assign a unique file name to each graph. I was thinking of using the hash function of the combinatorial object constructed from the graph to generate file names: <code>CombinatorialObject(G).__hash__()</code></p>
<p>I have two questions:</p>
<ol>
<li><p>Will this always work (the function taking a graph to this hash is well-defined and injective)?</p></li>
<li><p>Is there a better way to do this?</p></li>
</ol>
http://ask.sagemath.org/question/10040/generating-a-unique-file-name-for-each-graph/?answer=14807#post-id-14807The 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](http://en.wikipedia.org/wiki/Hash_function)).
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](http://en.wikipedia.org/wiki/Birthday_paradox)). 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.
Thu, 18 Apr 2013 23:23:19 -0500http://ask.sagemath.org/question/10040/generating-a-unique-file-name-for-each-graph/?answer=14807#post-id-14807Comment by fidbc for <p>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. <a href="http://en.wikipedia.org/wiki/Hash_function">wikipedia</a>).</p>
<p>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. <a href="http://en.wikipedia.org/wiki/Birthday_paradox">wikipedia</a>). 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).</p>
<p>That said, especially for simple graphs with less than 262143 vertices, there is a compact ASCII representation (which is injective), given by the method <code>.graph6_string()</code>:</p>
<pre><code>sage: G = graphs.PetersenGraph()
sage: G.graph6_string()
'IheA@GUAo'
</code></pre>
<p>The hash method seems faster.</p>
http://ask.sagemath.org/question/10040/generating-a-unique-file-name-for-each-graph/?comment=17849#post-id-17849It might be worth noting that the graph6_string depends on the labelling of the graph.
sage: g=graphs.PetersenGraph(); h=graphs.PetersenGraph()
sage: new_labels={0: 4, 1: 6, 2: 5, 3: 7, 4: 0, 5: 8, 6: 3, 7: 1, 8: 9, 9: 2};h.relabel(perm=new_labels)
sage: h.is_isomorphic(g)
True
sage: g.graph6_string()
'IheA@GUAo'
sage: h.graph6_string()
'IX`?{HGCW'
It might better to get the g6 string of the graph after using the `canonical_label` method.
sage: g.canonical_label().graph6_string()
'I@OZCMgs?'
sage: h.canonical_label().graph6_string()
'I@OZCMgs?'
Fri, 19 Apr 2013 07:25:37 -0500http://ask.sagemath.org/question/10040/generating-a-unique-file-name-for-each-graph/?comment=17849#post-id-17849Comment by Amri for <p>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. <a href="http://en.wikipedia.org/wiki/Hash_function">wikipedia</a>).</p>
<p>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. <a href="http://en.wikipedia.org/wiki/Birthday_paradox">wikipedia</a>). 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).</p>
<p>That said, especially for simple graphs with less than 262143 vertices, there is a compact ASCII representation (which is injective), given by the method <code>.graph6_string()</code>:</p>
<pre><code>sage: G = graphs.PetersenGraph()
sage: G.graph6_string()
'IheA@GUAo'
</code></pre>
<p>The hash method seems faster.</p>
http://ask.sagemath.org/question/10040/generating-a-unique-file-name-for-each-graph/?comment=17856#post-id-17856Thanks. This was both enlightening and useful.Thu, 18 Apr 2013 23:36:57 -0500http://ask.sagemath.org/question/10040/generating-a-unique-file-name-for-each-graph/?comment=17856#post-id-17856