[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] Faster way to detect duplicate graphs in a vector ptr?
From: |
Timothy Rice |
Subject: |
Re: [igraph] Faster way to detect duplicate graphs in a vector ptr? |
Date: |
Thu, 30 Jan 2014 11:29:20 +1100 |
User-agent: |
Mutt/1.5.21 (2010-09-15) |
Hi Gabor,
Thank you for responding.
> first, all this would be much-much simpler in R or Python, so you might
> consider using a high level language.
The thought crossed my mind but I think coding in C is good for the soul
:-)
> Second, you can define a hash function on the graph, and then calculate
> that for each graph. If the hash function is good, then you don't need to
> compare most pairs of graphs, because their hash will be different if they
> are different. If their hash is the same, then you need to compare them.
> This can be done by querying their edge lists, sorting them and then
> comparing them.
>
> An additional trick would be to sort the graphs according to their hash,
> and then only compare neighboring elements in the list with the same hash.
This seems like something I could do. I haven't implemented hashing before
so it will be a good learning exercise :-)
Thanks for your help!
Cheers,
Tim
--
PhD Candidate
A: Room 210, Richard Berry (Maths & Stats), Melbourne University
E: address@hidden
W: http://www.ms.unimelb.edu.au/~trice
G: https://github.com/cryptarch
pgp3rXWN50uit.pgp
Description: PGP signature