python - Valor de hash para gráfico acíclico dirigido

algorithm directed-acyclic-graphs

Question

¿Cómo transformo un gráfico acíclico dirigido en un valor hash tal que dos gráficos isomórficos hash tengan el mismo valor? Es aceptable, pero no es deseable que dos gráficos isomórficos resuenen valores diferentes, que es lo que hice en el siguiente código. Podemos suponer que la cantidad de vértices en el gráfico es como mucho 11.

Estoy particularmente interesado en el código de Python.

Aquí esta lo que hice. Si self.lt es una asignación de nodo a descendientes (¡no hijos!), Entonces vuelvo a etiquetar los nodos de acuerdo con un tipo topológico modificado (que prefiere ordenar primero los elementos con más descendientes, si es posible). Entonces, tengo hash el diccionario ordenado. Algunos gráficos isomórficos ajustarán valores diferentes, especialmente a medida que crezca el número de nodos.

He incluido todo el código para motivar mi caso de uso. Estoy calculando el número de comparaciones necesarias para encontrar la mediana de 7 números. Cuanto más hash de gráficos isomórficos tenga el mismo valor, menos trabajo habrá que rehacer. Consideré poner componentes conectados más grandes primero, pero no vi cómo hacerlo rápidamente.

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))

Answer 1

¿Qué tan bueno tiene que ser el hash? Supongo que no quiere una serialización completa del gráfico. Un hash rara vez garantiza que no hay un segundo elemento (gráfico) que evalúa el mismo hash. Si es muy importante para usted, que los gráficos isomorfos (en diferentes representaciones) tienen el mismo hash, entonces solo use valores que son invariantes bajo un cambio de representación. P.ej:

• la cantidad total de nodos
• el número total de conexiones (dirigidas)
• el número total de nodos con (indegree, outdegree) = (i,j) para cualquier tupla (i,j) hasta (max(indegree), max(outdegree)) (o limitado para tuplas hasta un cierto valor fijo (m,n) )

Todas estas informaciones se pueden recopilar en O (# nodes) [suponiendo que el gráfico se almacena correctamente]. Concatenarlos y tienes un hash. Si lo prefiere, puede utilizar algún conocido algoritmo hash como sha en estas informaciones concatenadas. Sin hashing adicional es un hash continuo (permite encontrar gráficos similares), con hash adicional es uniforme y de tamaño fijo si el algoritmo hash elegido tiene estas propiedades.

Tal como está, ya es lo suficientemente bueno para registrar cualquier conexión agregada o eliminada. Sin embargo, podría pasar por alto las conexiones que se cambiaron ( a -> c lugar de a -> b ).

Este enfoque es modular y puede extenderse tanto como desee. Cualquier propiedad adicional que se incluya reducirá el número de colisiones, pero aumentará el esfuerzo necesario para obtener el valor hash. Algunas ideas más:

• Igual que arriba, pero con un segundo orden de entrada y salida. Es decir. la cantidad de nodos a los que puede acceder un node->child->child cadena node->child->child (= segundo orden de grado) o respectivamente la cantidad de nodos que conducen al nodo determinado en dos pasos.
• o más n-ésimo orden de entrada y salida (se puede calcular en O ((promedio-número-de-conexiones) ^ (n-1) * #nodes))
• número de nodos con eccentricity = x (nuevamente para cualquier x)
• si los nodos almacenan cualquier información (que no sean sus vecinos) utilice un xor de cualquier tipo de hash de todos los contenidos del nodo. Debido al xor el orden específico en el que los nodos se agregaron al hash no importa.

Usted solicitó "un valor hash único" y claramente no puedo ofrecerle uno. Pero veo los términos "hash" y "exclusivo para cada gráfico" como mutuamente excluyentes (no del todo cierto por supuesto) y decidí responder a la parte "hash" y no a la parte "única". Un "hash único" ( hash perfecto ) básicamente necesita ser una serialización completa del gráfico (porque la cantidad de información almacenada en el hash debe reflejar la cantidad total de información en el gráfico). Si eso es lo que realmente quiere, simplemente defina un orden único de nodos (por ejemplo, ordenado por su propio grado de desacuerdo, luego indegree, luego por grado de niños hasta que el orden no sea ambiguo) y serialice el gráfico de cualquier forma (usando la posición en la ordenación mencionada como índice de los nodos).

Por supuesto, esto es mucho más complejo.

Answer 2

Con el pedido adecuado de sus descendientes (y si tiene un único nodo raíz, no dado, pero con un orden adecuado (tal vez incluyendo un nodo raíz virtual)), el método para hash de un árbol debería funcionar con una ligera modificación.

Código de ejemplo en esta respuesta de , la modificación sería ordenar los niños en un orden determinista (¿aumentar hash?) Antes de hash el padre.

Incluso si tiene múltiples raíces posibles, puede crear una raíz única sintética, con todas las raíces como niños.

Answer 3

Cuando vi la pregunta, esencialmente tenía la misma idea que @example. Escribí una función que proporciona una etiqueta de gráfico tal que la etiqueta coincide con dos gráficos isomórficos.

Esta etiqueta consiste en la secuencia de grados en orden ascendente. Puede hash esta etiqueta con la función hash de cadena de su elección para obtener un hash del gráfico.

Editar: expresé mi propuesta en el contexto de la pregunta original de @NeilG. La única modificación a su código es redefinir la función hashkey como:

def hashkey(self):
return tuple(sorted(map(len,self.lt.values())))

Answer 4

Describiré un algoritmo para hash un gráfico dirigido arbitrario, sin tener en cuenta que el gráfico es acíclico. De hecho, incluso contar los gráficos acíclicos de un orden dado es una tarea muy complicada y creo que esto solo hará que el hash sea significativamente más complicado y, por lo tanto, más lento.

Una representación única del gráfico puede ser dada por la lista de vecinos. Para cada vértice crea una lista con todos sus vecinos. Escriba todas las listas una detrás de otra agregando la cantidad de vecinos para cada lista al frente. También mantenga los vecinos ordenados en orden ascendente para que la representación sea única para cada gráfico. Entonces, por ejemplo, supongamos que tiene el gráfico:

1->2, 1->5
2->1, 2->4
3->4
5->3

Lo que propongo es que ({2,2,5}, {2,1,4}, {1,4}, {0}, {1,3}) esto a ({2,2,5}, {2,1,4}, {1,4}, {0}, {1,3}) , aquí las llaves solo son para visualizar la representación, no parte de la sintaxis de la pitón. Entonces la lista es de hecho: (2,2,5, 2,1,4, 1,4, 0, 1,3) .

Ahora, para calcular el hash único, necesita ordenar estas representaciones de alguna manera y asignarles un número único. Sugiero que hagas algo así como un tipo lexicográfico para hacer eso. Supongamos que tiene dos secuencias (a1, b1_1, b_1_2,...b_1_a1,a2, b_2_1, b_2_2,...b_2_a2,...an, b_n_1, b_n_2,...b_n_an) y (c1, d1_1, d_1_2,...d_1_c1,c2, d_2_1, d_2_2,...d_2_c2,...cn, d_n_1, d_n_2,...d_n_cn) , Aquí c y a son el número de vecinos para cada vértice y b_i_j y d_k_l son los vecinos correspondientes Para el orden primero compara los sequnces (a1,a2,...an) y (c1,c2, ...,cn) y si son diferentes usa esto para comparar las secuencias. Si estas secuencias son diferentes, compare las listas de izquierda a derecha primero comparando lexicográficamente (b_1_1, b_1_2...b_1_a1) a (d_1_1, d_1_2...d_1_c1) y así sucesivamente hasta la primera coincidencia.

De hecho, lo que propongo utilizar como hash es el número lexicográfico de una palabra de tamaño N sobre el alfabeto que está formada por todas las selecciones posibles de subconjuntos de elementos de {1,2,3,...N} . La lista de vecindarios para un vértice dado es una letra sobre este alfabeto, por ejemplo, {2,2,5} es el subconjunto que consiste en dos elementos del conjunto, concretamente 2 y 5 .

El alfabeto (conjunto de letras posibles) para el conjunto {1,2,3} sería (ordenado lexicográficamente ):

{0}, {1,1}, {1,2}, {1,3}, {2, 1, 2}, {2, 1, 3}, {2, 2, 3}, {3, 1, 2, 3}

El primer número como el anterior es la cantidad de elementos en el subconjunto dado y los números restantes: el subconjunto mismo. Así que forma todas las 3 letras de este alfabeto y obtendrás todos los posibles gráficos dirigidos con 3 vértices.

Ahora el número de subconjuntos del conjunto {1,2,3,....N} es 2^N y, por lo tanto, el número de letras de este alfabeto es 2^N Ahora codificamos cada gráfico dirigido de N nodos con una palabra con exactamente N letras de este alfabeto y, por lo tanto, el número de códigos hash posibles es precisamente: (2^N)^N Esto es para mostrar que el código hash crece realmente rápido con el aumento de N También esta es la cantidad de posibles gráficos dirigidos diferentes con N nodos, por lo que lo que sugiero es un hashing óptimo en el sentido de que es bijection y ningún hash más pequeño puede ser único.

Existe un algoritmo lineal para obtener un número de subconjunto dado en el orden lexicográfico de todos los subconjuntos de un conjunto dado, en este caso {1,2,....N} . Aquí está el código que he escrito para codificar / decodificar un subconjunto en número y viceversa. Está escrito en C++ pero es bastante fácil de entender, espero. Para el hash solo necesitará la función de código, pero como el hash que propongo es reversible, agrego la función de decodificación; podrá reconstruir el gráfico a partir del hash, que es bastante genial, creo:

typedef long long ll;
// Returns the number in the lexicographical order of all combinations of n numbers
// of the provided combination.
ll code(vector<int> a,int n)
{
sort(a.begin(),a.end()); // not needed if the set you pass is already sorted.
int cur = 0;
int m = a.size();
ll res =0;
for(int i=0;i<a.size();i++)
{
if(a[i] == cur+1)
{
res++;
cur = a[i];
continue;
}
else
{
res++;
int number_of_greater_nums = n - a[i];
for(int j = a[i]-1,increment=1;j>cur;j--,increment++)
res += 1LL << (number_of_greater_nums+increment);
cur = a[i];
}
}
return res;
}
// Takes the lexicographical code of a combination of n numbers and returns the
// combination
vector<int> decode(ll kod, int n)
{
vector<int> res;
int cur = 0;
int left = n; // Out of how many numbers are we left to choose.
while(kod)
{
ll all = 1LL << left;// how many are the total combinations
for(int i=n;i>=0;i--)
{
if(all - (1LL << (n-i+1)) +1 <= kod)
{
res.push_back(i);
left = n-i;
kod -= all - (1LL << (n-i+1)) +1;
break;
}
}
}
return res;
}

Además, este código almacena el resultado en long long variable de long long , que solo es suficiente para gráficos con menos de 64 elementos. Todos los hash de gráficos posibles con 64 nodos serán (2^64)^64 . Este número tiene aproximadamente 1280 dígitos, por lo que tal vez sea un número grande. Aun así, el algoritmo que describo funcionará muy rápido y creo que deberías poder hacer hash y ''deshacer'' los gráficos con muchos vértices.

También eche un vistazo a esta pregunta .

Answer 5

Hace años, creé un algoritmo simple y flexible para exactamente este problema (encontrar estructuras duplicadas en una base de datos de estructuras químicas al mezclarlas).

Lo llamé "Powerhash", y para crear el algoritmo requirió dos ideas. El primero es el algoritmo de gráfico de iteración de potencia, también utilizado en PageRank. El segundo es la capacidad de reemplazar la función de paso interior de la iteración de potencia con cualquier cosa que queramos. Lo reemplacé con una función que hace lo siguiente en cada paso, y para cada nodo:

• Ordenar los valores hash de los vecinos del nodo
• Hash los hash ordenados concatenados

En el primer paso, el hash de un nodo se ve afectado por sus vecinos directos. En el segundo paso, el hash de un nodo se ve afectado por el vecindario a 2 saltos de él. En el N-ésimo paso, el hash de un nodo se verá afectado por los N-hop vecinos que lo rodean. Por lo tanto, solo tiene que seguir ejecutando Powerhash para N = steps graph_radius. Al final, el hash del nodo del centro del gráfico se habrá visto afectado por el gráfico completo.

Para producir el hash final, clasifique los hashes de nodo del paso final y concatenarlos juntos. Después de eso, puedes comparar los hashes finales para encontrar si dos gráficos son isomórficos. Si tiene etiquetas, agréguelas a los valores hash internos que calcule para cada nodo (y en cada paso).

Para obtener más información sobre esto, puede consultar mi publicación aquí:

https://plus.google.com/114866592715069940152/posts/fmBFhjhQcZF

El algoritmo anterior se implementó dentro de la base de datos relacional funcional "madIS". Puede encontrar el código fuente del algoritmo aquí:

https://github.com/madgik/madis/blob/master/src/functions/aggregate/graph.py

Answer 6

Imho, si el gráfico se puede clasificar topológicamente, existe una solución muy directa.

1. Para cada vértice con índice i, puede construir un hash único (por ejemplo, usando la técnica de hashing para cadenas) de sus vecinos directos (ordenados) (pe si el vértice 1 tiene vecinos directos {43, 23, 2,7,12, 19,334} las funciones hash deben hash la matriz de {2,7,12,19,23,43,334})
2. Para todo el DAG, podría crear un hash, como un hash de una cadena de hashes para cada nodo: Hash (DAG) = Hash (vertex_1) U Hash (vertex_2) U ..... Hash (vertex_N); Creo que la complejidad de este procedimiento está alrededor (N * N) en el peor de los casos. Si el gráfico no pudo ser ordenado topológicamente, el enfoque propuesto sigue siendo aplicable, pero necesita ordenar vértices de una manera única (y esta es la parte difícil)

Answer 7

No estoy seguro de que funcione al 100%, pero aquí hay una idea:

Vamos a codificar un gráfico en una cadena y luego tomar su hash.

1. hash de un gráfico vacío es ""
2. hash de un vértice sin bordes salientes es "."
3. hash de un vértice con bordes salientes es la concatenación de cada hash hijo con algún delimitador (por ejemplo, ",")

Para producir el mismo hash para los gráficos isomorfos antes de la concatenación en el paso 3, simplemente ordena los hash (por ejemplo, en orden lexicográfico).

Para el hash de un gráfico simplemente tome el hash de su raíz (o la concatenación clasificada, si hay varias raíces).

Mientras esperaba que la cadena resultante describiera el gráfico sin colisiones, hynekcer descubrió que, a veces, los gráficos no isomórficos obtendrían el mismo hash. Eso sucede cuando un vértice tiene varios padres: luego se "duplica" para cada padre. Por ejemplo, el algoritmo no diferencia un "diamante" {A-> B-> C, A-> D-> C} del caso {A-> B-> C, A-> D-> E}.

No estoy familiarizado con Python y es difícil para mí entender cómo se almacena el gráfico en el ejemplo, pero aquí hay un código en C ++ que probablemente sea fácilmente convertible a Python:

THash GetHash(const TGraph &graph)
{
return ComputeHash(GetVertexStringCode(graph,FindRoot(graph)));
}
std::string GetVertexStringCode(const TGraph &graph,TVertexIndex vertex)
{
std::vector<std::string> childHashes;
for(auto c:graph.GetChildren(vertex))
childHashes.push_back(GetVertexStringCode(graph,*c));
std::sort(childHashes.begin(),childHashes.end());
std::string result=".";
for(auto h:childHashes)
result+=*h+",";
return result;
}

Answer 8

Para probar efectivamente el isomorfismo gráfico, querrá usar nauty . Específicamente para Python existe la envoltura pynauty , pero no puedo atestiguar su calidad (para compilarla correctamente tuve que hacer algunos parches simples en su setup.py ). Si este envoltorio está haciendo todo correctamente, entonces simplifica mucho el uso de nauty para los usos que le interesan y solo se trata de hashing pynauty.certificate(somegraph) , que tendrá el mismo valor para los gráficos isomórficos.

Algunas pruebas rápidas mostraron que pynauty está dando el mismo certificado para cada gráfico (con la misma cantidad de vértices). Pero eso solo se debe a un problema menor en el contenedor al convertir el gráfico al formato nauty. Después de arreglar esto, me funciona (también utilicé los gráficos en http://funkybee.narod.ru/graphs.htm para comparar). Aquí está el parche corto que también considera las modificaciones necesarias en setup.py :

diff -ur pynauty-0.5-orig/setup.py pynauty-0.5/setup.py
--- pynauty-0.5-orig/setup.py 2011-06-18 20:53:17.000000000 -0300
+++ pynauty-0.5/setup.py 2013-01-28 22:09:07.000000000 -0200
@@ -31,7 +31,9 @@
ext_pynauty = Extension(
name = MODULE + ''._pynauty'',
- sources = [ pynauty_dir + ''/'' + ''pynauty.c'', ],
+ sources = [ pynauty_dir + ''/'' + ''pynauty.c'',
+ os.path.join(nauty_dir, ''schreier.c''),
+ os.path.join(nauty_dir, ''naurng.c'')],
depends = [ pynauty_dir + ''/'' + ''pynauty.h'', ],
extra_compile_args = [ ''-O4'' ],
extra_objects = [ nauty_dir + ''/'' + ''nauty.o'',
diff -ur pynauty-0.5-orig/src/pynauty.c pynauty-0.5/src/pynauty.c
--- pynauty-0.5-orig/src/pynauty.c 2011-03-03 23:34:15.000000000 -0300
+++ pynauty-0.5/src/pynauty.c 2013-01-29 00:38:36.000000000 -0200
@@ -320,7 +320,7 @@
PyObject *adjlist;
PyObject *p;
- int i,j;
+ Py_ssize_t i, j;
int adjlist_length;
int x, y;

Answer 9

Supongo que no hay etiquetas comunes en vértices o bordes, porque entonces podrías poner el gráfico en una forma canónica, que a su vez sería un hash perfecto. Esta propuesta, por lo tanto, se basa solo en el isomorfismo.

Para esto, combine hashes para tantas características agregadas simples de un DAG como pueda imaginar, escogiendo aquellas que son rápidas de calcular. Aquí hay una lista de inicio:

1. 2d histograma de grados de entrada y salida de nodos.
2. 4d histograma de los bordes a-> b donde a y b se caracterizan ambos por grado de entrada / salida.

Adición Déjame ser más explícito. Para 1, calcularíamos un conjunto de triples <I,O;N> (donde no hay dos tripletas que tengan los mismos valores I , O ), lo que significa que hay N nodos con grado I y O fuera de grado. Haría hash este conjunto de triples o, mejor aún, usaría todo el conjunto organizado en algún orden canónico, por ejemplo ordenado lexicográficamente. Para 2, calculamos un conjunto de quíntuples <aI,aO,bI,bO;N> que significa que hay N bordes de nodos con en grado aI y fuera de grado aO , a nodos con bI y bO respectivamente. Nuevamente hash estos quintuples o bien utilízalos en orden canónico como está para otra parte del hash final.

Comenzar con esto y luego observar las colisiones que aún ocurren probablemente proporcionará información sobre cómo mejorar.

Answer 10

El isomorfismo gráfico para gráficos acíclicos dirigidos sigue siendo GI-completo. Por lo tanto, actualmente no existe una solución conocida (peor caso sub-exponencial) para garantizar que dos gráficos acíclicos isomórficos dirigidos producirán el mismo hash. Solo si se conoce el mapeo entre diferentes gráficos, por ejemplo, si todos los vértices tienen etiquetas únicas, se podría garantizar eficientemente que coincidan los hashes.

De acuerdo, vamos a forzar esto por una pequeña cantidad de vértices. Tenemos que encontrar una representación de la gráfica que sea independiente del orden de los vértices en la entrada y por lo tanto garantiza que los gráficos isomórficos produzcan la misma representación. Además, esta representación debe garantizar que no haya dos gráficos no isomórficos que produzcan la misma representación.

La solución más simple es construir la matriz de adyacencia para todos los n! permutaciones de los vértices e interpretar la matriz de adyacencia como n entero de ² bits. Entonces podemos elegir el más pequeño o el más grande de estos números como representación canónica. Este número codifica por completo el gráfico y, por lo tanto, garantiza que no hay dos gráficos no isomórficos que produzcan el mismo número; se podría considerar que esta función es una función hash perfecta . Y debido a que elegimos el número más pequeño o más grande que codifica el gráfico bajo todas las permutaciones posibles de los vértices, aseguramos que los gráficos isomórficos produzcan la misma representación.

¿Qué tan bueno o malo es esto en el caso de 11 vértices? Bueno, la representación tendrá 121 bits. Podemos reducir esto en 11 bits porque los bucles diagonales que representan serán todos ceros en un gráfico acíclico y quedan con 110 bits. En teoría, este número podría reducirse aún más; no todos los 2 ¹¹⁰ gráficos restantes son acíclicos y para cada gráfico puede haber hasta 11! - aproximadamente 2 ²⁵ representaciones isomórficas, pero en la práctica esto puede ser bastante difícil de hacer. ¿Alguien sabe cómo calcular el número de gráficos acíclicos dirigidos distintos con n vértices?

¿Cuánto tiempo llevará encontrar esta representación? Naively 11! o 39,916,800 iteraciones. Esto no es nada y probablemente ya no sea práctico, pero no lo implementé y lo probé. Pero probablemente podamos acelerar esto un poco. Si interpretamos la matriz de adyacencia como un número entero al concatenar las filas de arriba a abajo, de izquierda a derecha, queremos muchos unos (ceros) a la izquierda de la primera fila para obtener un número grande (pequeño). Por lo tanto, escogemos como primer vértice el uno (o uno de los vértices) con el mayor (menor) grado (grado o grado según la representación) y los vértices conectados (no conectados) a este vértice en posiciones posteriores para traer los unos (ceros) ) a la izquierda.

Es probable que haya más posibilidades de podar el espacio de búsqueda, pero no estoy seguro de si hay suficientes para hacer de esto una solución práctica. Tal vez haya o tal vez alguien más al menos pueda construir algo sobre esta idea.