Как преобразовать направленный ациклический граф в хеш-значение, чтобы любые два изоморфных графа хэш равны одному значению? Это приемлемо, но нежелательно для двух изоморфных графов к хешу к разным значениям, что я и сделал в приведенном ниже коде. Мы можем предположить, что число вершин в графе не превышает 11.
Меня особенно интересует код Python.
Вот что я сделал. Если self.lt - это отображение из node для потомков (а не дочерних!), То я переписываю узлы в соответствии с модифицированной топологической сортировкой (которая сначала предпочитает упорядочивать элементы с большим количеством потомков). Затем я использую отсортированный словарь. Некоторые изоморфные графики будут хешировать до разных значений, особенно по мере роста числа узлов.
Я включил весь код, чтобы мотивировать мой прецедент. Я рассчитываю количество сравнений, необходимых для поиска медианы из 7 чисел. Чем больше изоморфных графов хеш имеет одно и то же значение, тем меньше работы нужно переделать. Сначала я рассмотрел возможность добавления более крупных подключенных компонентов, но не видел, как это сделать быстро.
from tools.decorator import memoized # A standard memoization decorator
class Graph:
def __init__(self, n):
self.lt = {i: set() for i in range(n)}
def compared(self, i, j):
return j in self.lt[i] or i in self.lt[j]
def withedge(self, i, j):
retval = Graph(len(self.lt))
implied_lt = self.lt[j] | set([j])
for (s, lt_s), (k, lt_k) in zip(self.lt.items(),
retval.lt.items()):
lt_k |= lt_s
if i in lt_k or k == i:
lt_k |= implied_lt
return retval.toposort()
def toposort(self):
mapping = {}
while len(mapping) < len(self.lt):
for i, lt_i in self.lt.items():
if i in mapping:
continue
if any(i in lt_j or len(lt_i) < len(lt_j)
for j, lt_j in self.lt.items()
if j not in mapping):
continue
mapping[i] = len(mapping)
retval = Graph(0)
for i, lt_i in self.lt.items():
retval.lt[mapping[i]] = {mapping[j]
for j in lt_i}
return retval
def median_known(self):
n = len(self.lt)
for i, lt_i in self.lt.items():
if len(lt_i) != n // 2:
continue
if sum(1
for j, lt_j in self.lt.items()
if i in lt_j) == n // 2:
return True
return False
def __repr__(self):
return("[{}]".format(", ".join("{}: {{{}}}".format(
i,
", ".join(str(x) for x in lt_i))
for i, lt_i in self.lt.items())))
def hashkey(self):
return tuple(sorted({k: tuple(sorted(v))
for k, v in self.lt.items()}.items()))
def __hash__(self):
return hash(self.hashkey())
def __eq__(self, other):
return self.hashkey() == other.hashkey()
@memoized
def mincomps(g):
print("Calculating:", g)
if g.median_known():
return 0
nodes = g.lt.keys()
return 1 + min(max(mincomps(g.withedge(i, j)),
mincomps(g.withedge(j, i)))
for i in nodes
for j in nodes
if j > i and not g.compared(i, j))
g = Graph(7)
print(mincomps(g))
