powerhash2.py

# ISC License
# Copyright (c) 2017, Lefteris Stamatogiannakis
# Permission to use, copy, modify, and/or distribute this software for any
# purpose with or without fee is hereby granted, provided that the above
# copyright notice and this permission notice appear in all copies.
# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
# REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
# AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
# INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
# LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
# OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
# PERFORMANCE OF THIS SOFTWARE.
#
# Powerhash2 function generates a hash from an input graph.
# By comparing the hashes from two graphs you can find out if they are potentially isomorphic (or you have a false positive).
# Input can be a directed or undirected graph with labels.

from hashlib import md5
import json
from binascii import b2a_base64
import math
import random
from copy import deepcopy
# from http://dabacon.org/pontiff/?p=4148
regular1 = {
        1:[[4,5,6], ''],
        2:[[4,5,6], ''],
        3:[[4,5,6], ''],
        4:[[1,2,3], ''],
        5:[[1,2,3], ''],
        6:[[2,3,1], ''],
    }

regular2 = {
        1:[[2,3,4], ''],
        2:[[1,3,5], ''],
        3:[[1,2,6], ''],
        4:[[1,5,6], ''],
        5:[[2,4,6], ''],
        6:[[3,4,5], ''],
    }

# from http://users.cecs.anu.edu.au/~pascal/docs/thesis_pascal_schweitzer.pdf page 28
furer1 = {
        1:[[2], ''],
        2:[[1,3], ''],
        3:[[2,4,13], ''],
        4:[[3,5,25], ''],
        5:[[4,6,14], ''],
        6:[[5,7], ''],
        7:[[6,8], ''],
        8:[[7,9], ''],
        9:[[8,10], ''],
        10:[[9,11], ''],
        11:[[10,12], ''],
        12:[[11,13,14], ''],
        13:[[3,12,18], ''],
        14:[[5,12,15], ''],
        15:[[14,16,17], ''],
        16:[[15], ''],
        17:[[15,18,25], ''],
        18:[[13,17,19], ''],
        19:[[18,20], ''],
        20:[[19,21], ''],
        21:[[20,22], ''],
        22:[[21,23], ''],
        23:[[22,24], ''],
        24:[[23,25], ''],
        25:[[4,17,24], ''],
}

furer2 = {
        1:[[2], ''],
        2:[[1,3], ''],
        3:[[2,4,13], ''],
        4:[[3,5,25], ''],
        5:[[4,14,19], ''],
        6:[[7,18], ''],
        7:[[6,8], ''],
        8:[[7,9], ''],
        9:[[8,10], ''],
        10:[[9,11], ''],
        11:[[10,12], ''],
        12:[[11,13,14], ''],
        13:[[3,12,18], ''],
        14:[[5,12,15], ''],
        15:[[14,16,17], ''],
        16:[[15], ''],
        17:[[15,18,25], ''],
        18:[[6,13,17], ''],
        19:[[5,20], ''],
        20:[[19,21], ''],
        21:[[20,22], ''],
        22:[[21,23], ''],
        23:[[22,24], ''],
        24:[[23,25], ''],
        25:[[4,17,24], ''],
}

def graphShuffle(graph):
    inkeys = graph.keys()
    outkeys = inkeys[:]
    random.shuffle(outkeys)
    maptable = dict(zip(inkeys,outkeys))
    outgraph = {}
    for n,v in graph.iteritems():
        outgraph[maptable[n]] = [[maptable[x] for x in v[0]], v[1]]
    return outgraph

def powerhash2(graph):
    nodes = deepcopy(graph)
    ncount=len(nodes)

    for n,v in nodes.iteritems():
        v[1]=str(len(v[0]))+chr(31)+v[1]

    # Calculate approximate worse case diameter
    degreeseq=set()
    mindegree=ncount
    maxdegree=0
    invdegree=0.0

    for n,v in nodes.iteritems():
        ndegree=len(v[0])
        mindegree=min(mindegree, ndegree)
        maxdegree=max(maxdegree, ndegree)
        degreeseq.add(ndegree)
        invdegree+=1.0/ndegree

    # TODO: Replace with proper graph radius calculation algorithm (eg. double BFS)
    radius=int(min(
    # Obvious upper bounds
    ncount-max(2, maxdegree) + 2,
    # P. Dankelmann "Diameter and inverse degree"
    (3*invdegree+3)*math.log(ncount)/math.log(math.log(ncount)) if ncount>16 else ncount,
    # Simon Mukwembi "A note on diameter and the degree sequence of a graph"
    1+3*(ncount - len(degreeseq)+1)/float((mindegree+1)), ncount - len(degreeseq)+2))/2

    if radius < 1:
        radius = ncount - max(2, maxdegree) + 2

    nhashes={}
    ghashes = []
    for _, va in nodes.iteritems():
        origlabel = va[1]
        va[1] = va[1] + chr(29) + 'A'
        for n,v in nodes.iteritems():
            nhashes[n]=md5(v[1]+chr(30)).digest()
        for s in xrange(radius):
            nhashes1={}
            for n, v in nodes.iteritems():
                nhashes1[n] = md5(v[1]+chr(30)+chr(30).join(sorted([nhashes[x] for x in v[0]]))).digest()
            nhashes = nhashes1
        va[1] = origlabel
        ghashes.append(md5(chr(28).join(sorted(nhashes.values()))).digest())

    return json.dumps([b2a_base64(x)[0:-3] for x in sorted(ghashes)], separators=(',',':'), ensure_ascii=False)

print 'Testing shuffled graphs:'
failfound = False
basehash = powerhash2(furer1)
for i in range(100):
    if basehash != powerhash2(graphShuffle(furer1)):
        failfound = True
        break
print 'correct' if failfound == False else 'fail'

print 'Testing regular graph:'
print 'correct' if powerhash2(regular1) != powerhash2(regular2) else 'fail'
print 'Testing Furer gadget graph:'
print 'correct' if powerhash2(furer1) != powerhash2(furer2) else 'fail'