Ask Your Question
0

Generating a unique file name for each graph

asked 2013-04-18 22:52:38 -0500

updated 2013-04-18 22:53:44 -0500

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?

edit retag flag offensive close merge delete

Comments

1

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

fidbc gravatar imagefidbc ( 2013-04-19 07:29:25 -0500 )edit

@fidelbc Thanks for the comments, and bringing MongoDB to my attention.

Amri gravatar imageAmri ( 2013-04-20 02:26:51 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
1

answered 2013-04-18 23:23:19 -0500

tmonteil gravatar image

updated 2013-04-18 23:28:46 -0500

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.

edit flag offensive delete link more

Comments

Thanks. This was both enlightening and useful.

Amri gravatar imageAmri ( 2013-04-18 23:36:57 -0500 )edit
1

It 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?'

fidbc gravatar imagefidbc ( 2013-04-19 07:25:37 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2013-04-18 22:52:38 -0500

Seen: 121 times

Last updated: Apr 18 '13