Valeur de hachage pour le graphe acyclique dirigé

L'isomorphisme des graphes acycliques dirigés est encore complet. par conséquent, il n'existe actuellement aucune solution connue (sous-exponentielle dans le pire des cas) pour garantir que deux graphes acycliques dirigés isomorphiques donneront le même hachage. Ce n'est que si le mappage entre différents graphes est connu - par exemple si tous les sommets ont des étiquettes uniques - que l'on peut garantir efficacement des hachures correspondantes.

OK, forçons ça pour un petit nombre de vertex. Nous devons trouver une représentation du graphe qui est indépendante de l'ordre des sommets dans l'entrée et donc des garanties que les graphes isomorphiques donnent la même représentation. De plus, cette représentation doit s'assurer qu'aucun graphique non isomorphe ne donne la même représentation.

la solution la plus simple est de construire la matrice de contiguïté pour tout n! les permutations des sommets et il suffit d'interpréter la matrice de contiguïté comme n ² bit entier. Ensuite, nous pouvons choisir le plus petit ou le plus grand de ces nombres comme représentation canonique. Ce nombre code complètement le graphe et garantit donc qu'aucun graphique non-isomorphe ne produit le même nombre - on pourrait considérer cette fonction une fonction de hachage parfait . Et parce que nous choisissons le plus petit ou le plus grand nombre encodant le graphe sous toutes les permutations possibles des sommets, nous nous assurons en outre que les graphes isomorphiques produisent le même représentation.

à quel point est-ce bon ou mauvais dans le cas de 11 sommets? La représentation aura 121 bits. Nous pouvons réduire cela de 11 bits parce que la diagonale représentant les boucles sera tous les zéros dans un graphique acyclique et sont laissés avec 110 bits. Ce nombre pourrait en théorie être diminué davantage; pas tous 2 ¹¹⁰ graphes restants sont acycliques et pour chaque graphe il peut y avoir jusqu'à 11! - environ 2 ²⁵ - isomorphique les représentations, mais dans la pratique, cela peut être assez difficile à faire. Quelqu'un sait-il calculer le nombre de graphes acycliques dirigés distincts avec n sommets?

combien de temps faut-il pour trouver cette représentation? Naïvement 11! ou 39,916,800 itérations. Ce n'est pas rien et probablement déjà impraticable, mais je ne l'ai pas mis en œuvre et testé. Mais on peut probablement accélérer un peu. Si nous interprétons la matrice de contiguïté comme un nombre entier en concaténant les lignes de haut en en bas de gauche à droite, nous voulons beaucoup (zéros) à la gauche de la première rangée pour obtenir un grand (petit) nombre. C'est pourquoi nous choisissons comme premier sommet celui (ou l'un des sommets) avec le plus grand (le plus petit) degré (indegree ou outdegree selon la représentation) et que les sommets connectés (non connectés) à ce sommet dans les positions suivantes pour amener les uns (zéros) à gauche.

il y a probablement plus de possibilités de tailler l'espace de recherche, mais je ne suis pas sûr si il y en a assez pour en faire une solution pratique. Il existe peut-être ou peut-être quelqu'un d'autre peut au moins construire quelque chose sur cette idée.

Comment doit être le hash? Je suppose que vous faites pas voulez une sérialisation complète du graphe. Un hachage garantit rarement qu'il n'y a pas de deuxième (mais différent) élément (graphe) qui évalue au même hachage. S'il est très important pour vous, que les graphiques isomorphiques (dans des représentations différentes) aient le même hachage, alors n'utilisez que des valeurs qui sont invariantes sous un changement de représentation. Par exemple:

• le total nombre de nœuds
• le nombre total de connexions
• le nombre total de noeuds avec (indegree, outdegree) = (i,j) pour tout tuple (i,j) jusqu'à (max(indegree), max(outdegree)) (ou limité pour tuples jusqu'à une certaine valeur fixe (m,n) )

toutes ces informations peuvent être rassemblées en O(#Noeuds) [en supposant que le graphe est stocké correctement]. Concaténez - les et vous aurez du hash. Si vous préférez, vous pouvez utiliser certaines bien connues de hachage algorithme comme sha sur ces informations concaténées. Sans hachage supplémentaire, il s'agit d'un hachage continu (il permet de trouver des graphiques similaires), avec hachage supplémentaire, il est uniforme et fixe dans la taille si l'algorithme de hachage choisi a ces propriétés.

comme il est, il est déjà assez bon d'enregistrer toute connexion ajoutée ou retirée. Il pourrait manquer des connexions qui ont été changées cependant ( a -> c à la place de a -> b ).

cette approche est modulaire et peut être étendue autant que vous le souhaitez. Toute propriété supplémentaire qui est incluse réduira le nombre de collisions mais augmentera l'effort nécessaire pour obtenir la valeur de hachage. D'autres idées:

• même que ci - dessus, mais avec un second ordre en-et en-degrés. IE. le nombre de noeuds pouvant être atteints par une chaîne node->child->child (=deuxième ordre) ou respectivement le nombre de nœuds qui mènent au nœud donné en deux étapes.
• ou plus général n-e ordre en-et en-degree (peut être calculé en O ((moyenne-nombre-de-connexions) ^ (n-1) * #noeuds))
• nombre de noeuds avec excentricité = x (de nouveau pour tout x)
• si les noeuds stockent des informations (autres que leurs voisins) utiliser un xor de toute sorte de hachage de tout le contenu des noeuds. Raison au xor l'ordre spécifique dans lequel les noeuds ont été ajoutés au hachage n'a pas d'importance.

vous avez demandé "une valeur unique de hachage" et clairement Je ne peux pas vous en offrir une. Mais je vois les Termes "hachage" et "unique à chaque graphe" comme s'excluant mutuellement (pas entièrement vrai bien sûr) et j'ai décidé de répondre à la partie "hachage" et non à la partie "unique". Un" hachage unique "( hachage parfait ) doit fondamentalement être un la sérialisation complète du graphique (parce que la quantité d'information stockée dans le hachage doit refléter la quantité totale d'information dans le graphique). Si c'est vraiment ce que vous voulez juste définir un ordre unique de noeuds (par exemple. trié par propre outdegree, puis indegree, puis outdegree of children et ainsi de suite jusqu'à ce que l'ordre soit non ambigu) et sérialiser le graphe de n'importe quelle façon (en utilisant la position dans l'ordre mentionné ci-dessus comme index aux noeuds).

bien sûr, c'est beaucoup plus complexe.

Imho, si le graphique pouvait être topologiquement trié, la solution très simple existe.

1. pour chaque vertex avec index i, vous pouvez construire un hachage unique (par exemple, en utilisant la technique de hachage pour les cordes) de ses voisins directs (triés) (p. E. if vertex 1 has direct neighbours {43, 23, 2,7,12,19,334} the hash functions should hash the array of {2,7,12,19,23,43,334})
2. pour tout le DAG vous pouvez créer un hachage, comme hachage d'une chaîne de hachages pour chaque noeud: hachage(DAG) = hachage(vertex_1) U hachage (vertex_2) U..... Hash(vertex_N); Je pense que la complexité de cette procédure est d'environ (N*N) dans le pire des cas. Si le graphique ne peut pas être topologiquement trié, l'approche proposée est toujours applicable, mais vous devez Ordonner vertices d'une manière unique (et c'est la partie difficile)

je vais décrire un algorithme pour hachurer un graphe dirigé arbitraire, ne tenant pas compte du fait que le graphe est acyclique. En fait, même en comptant les graphes acycliques d'un ordre donné est une tâche très compliquée et je crois que cela ne fera que rendre le hachage beaucoup plus compliqué et donc plus lent.

une représentation unique du graphique peut être donnée par la liste des quartiers. Pour chaque sommet créer une liste avec tous ses voisins. Ecrire toutes les listes l'un après l'autre, en ajoutant le nombre de voisins pour chaque liste au front. Gardez également les voisins triés dans l'ordre croissant pour rendre la représentation unique pour chaque graphe. Ainsi, par exemple, supposons que vous avez le graphique:

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

ce que je propose c'est que vous transformiez ceci en ({2,2,5}, {2,1,4}, {1,4}, {0}, {1,3}) , ici les crochets bouclés étant seulement pour visualiser la représentation, pas une partie de la syntaxe de python. Donc, la liste est en fait: (2,2,5, 2,1,4, 1,4, 0, 1,3) .

Maintenant pour calculer le hachage unique, vous avez besoin de commander ces représentations d'une certaine manière et d'attribuer un numéro unique. Je vous suggère de faire quelque chose comme une sorte de lexicographie pour faire ça. Supposons que vous avez deux séquences (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) et (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) , ici c et a sont le nombre de voisins pour chaque vertex et b_i_j et d_k_l sont les voisins correspondants. Pour la commande comparer d'abord les suites (a1,a2,...an) et (c1,c2, ...,cn) et si elles sont différentes utiliser ceci pour comparer les séquence. Si ces séquences sont différentes, comparez les listes de gauche à droite en comparant lexicographiquement (b_1_1, b_1_2...b_1_a1) à (d_1_1, d_1_2...d_1_c1) et ainsi de suite jusqu'à la première erreur.

en fait, ce que je propose d'utiliser comme hachage le numéro lexicographique d'un mot de taille N sur l'alphabet qui est formé par toutes les sélections possibles de sous-ensembles d'éléments de {1,2,3,...N} . La liste de voisinage pour un vertex donné est une lettre au-dessus de cet alphabet Par exemple {2,2,5} est le sous-ensemble constitué de deux éléments de l'ensemble, à savoir 2 et 5 .

le alphabet (ensemble de possibles lettres ) pour l'ensemble {1,2,3} serait(commandé lexicographiquement ):

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

Premier nombre, comme ci-dessus est le nombre d'éléments dans le sous-ensemble et les autres numéros - la sous-ensemble de lui-même. Alors formez tous les 3 mots lettres de cet alphabet et vous obtiendrez tous les graphes dirigés possibles avec 3 sommets.

Maintenant, le nombre de sous-ensembles de l'ensemble {1,2,3,....N} est 2^N et donc le nombre de lettres de cet alphabet est 2^N . Maintenant nous codons chaque graphique dirigé des noeuds N avec un mot avec exactement N lettres de ce alphabet et donc le nombre de codes de hachage possibles est précisément: (2^N)^N . C'est pour montrer que le code de hachage croît vraiment rapide avec l'augmentation de N . C'est aussi le nombre de différents graphes dirigés possibles avec des noeuds N donc ce que je suggère est un hachage optimal dans le sens où il est bijection et aucun hachage plus petit ne peut être unique.

il y a un linéaire algorithme pour obtenir un numéro de sous-ensemble donné dans l'ordre lexicographique de tous les sous-ensembles d'un ensemble donné, dans ce cas {1,2,....N} . Voici le code que j'ai écrit pour coder/décoder un sous-ensemble en nombre et vice versa. Il est écrit dans C++ mais assez facile à comprendre j'espère. Pour le hachage vous n'aurez besoin que de la fonction de code mais comme le hachage que je propose est réversible j'ajoute la fonction de décodage - vous serez en mesure de reconstruire le graphique à partir du hachage qui est assez cool je pense:

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;
}

ce code stocke également le résultat dans la variable long long , qui est seulement suffisant pour les graphiques avec moins de 64 éléments. Tous les hachages possibles de graphiques avec 64 noeuds seront (2^64)^64 . Ce nombre a environ 1280 chiffres donc peut-être est un grand nombre. Encore l'algorithme que je décris travailler très vite et je crois que vous devriez être en mesure de hachage et " unhash graphiques avec beaucoup de sommets.

ont également un coup d'oeil à cette question .

Je ne suis pas sûr que cela fonctionne à 100% , mais voici une idée:

codons un graphe dans une chaîne et puis prenez son hachage.

1. le hachage d'un graphique vide est "
2. hachage d'un vertex sans bords sortants est "."
3. hachage d'un vertex avec des bords sortants est la concaténation de chaque enfant hachage avec un certain délimiteur (par exemple ",")

pour produire le même hachage les graphiques isomorphiques avant la concaténation à l'étape 3 trient juste les hachures (par exemple dans l'ordre lexicographique).

pour le hachage d'un graphe il suffit de prendre le hachage de sa racine (ou la concaténation triée, s'il y a plusieurs racines).

edit alors que j'espérais que la chaîne résultante décrirait graph sans collisions, hynekcer a trouvé que parfois les graphiques non-isomorphiques obtiendront le même hachage. Ce qui se passe quand un vertex a plusieurs parents - puis il "dupliqué" pour chaque parent. Par exemple, l'algorithme ne permet pas de différencier un "diamant" {A->B->C->D->C} à partir des cas {A->B->C->D->E}.

Je ne suis pas familier avec Python et il m'est difficile de comprendre comment graph stocké dans l'exemple, Mais voici un peu de code en C++ qui est probablement convertible en Python facilement:

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;
}

je suppose qu'il n'y a pas d'étiquettes communes sur les sommets ou les bords, car alors vous pourriez mettre le graphe dans une forme canonique, qui lui-même serait un hachage parfait. Cette proposition se fonde donc sur isomorphisme.

pour cela, combinez des hachures pour autant de caractéristiques agrégées simples d'un DAG que vous pouvez imaginer, en choisissant celles qui sont rapides à calculer. Voici une liste de départ:

1. 2d histogramme de nœuds" degré.
2. histogramme 4d des arêtes a - >b où a et b sont tous deux caractérisés par un degré d'entrée/sortie.

Plus Permettez-moi d'être plus explicite. Pour 1, on calcule un ensemble de triples <I,O;N> (où il n'y a pas deux triples ayant les mêmes valeurs I , O ), ce qui signifie qu'il y a N noeuds avec In-degree I et out-degree O . Tu te la taperais bien cette paire de triples ou mieux encore utilisez l'ensemble organisé dans un ordre canonique, par exemple, trié lexicographiquement. Pour 2 , nous calculons un ensemble de quintuples <aI,aO,bI,bO;N> signifiant qu'il y a des arêtes N à partir des noeuds avec le degré aI et le degré aO , vers les noeuds avec bI et bO respectivement. Encore une fois hachez ces quintuples ou bien utilisez-les dans l'ordre canonique comme-est pour une autre partie du hachage final.

en commençant par ceci et en regardant les collisions ce qui se produit encore fournira probablement des indications sur la façon de s'améliorer.

Quand j'ai vu la question, j'ai essentiellement la même idée que @exemple. J'ai écrit une fonction fournissant une étiquette de graphique telle que l'étiquette coïncide pour deux graphiques isomorphiques.

cette balise se compose de la séquence des degrés extrêmes dans l'ordre ascendant. Vous pouvez hachage de cette étiquette avec la chaîne de hachage fonction de votre choix pour obtenir un hachage du graphique.

Edit: j'ai exprimé ma proposition dans le contexte de l'original de @NeilG question. La seule modification à apporter à son code est de redéfinir la fonction hashkey comme suit:"

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

il y a des années, j'ai créé un algorithme simple et flexible pour exactement ce problème (trouver des structures dupliquées dans une base de données de structures chimiques en les hachant).

Je l'ai appelé "Powerhash", et pour créer l'algorithme il a fallu deux intuitions. Le premier est l'algorithme de graphique d'itération de puissance, également utilisé dans PageRank. La seconde est la possibilité de remplacer la fonction inside step de power itération par tout ce que nous voulons. Je l'ai remplacé par une fonction qui n' la suivante sur chaque pas, et pour chaque noeud:

• trier les hachures des voisins du noeud
• Hachage de la concaténation triés hachages

sur la première étape, le hachage d'un noeud est affecté par ses voisins directs. Sur la deuxième étape, le hachage d'un noeud est affecté par le voisinage 2-sauts loin de lui. Sur la nième étape, le hachage d'un noeud sera affecté par le N-houblon du voisinage autour de lui. Donc, vous ne devez continuer à exécuter le Powerhash pour N = graph_radius steps. En fin de compte, le hachage du noeud central du graphe aura été affecté par l'ensemble du graphe.

pour produire le hachage final, trier les hachures de noeud de l'étape finale et les concaténer ensemble. Après cela, vous pouvez comparer les hachages de trouver si deux graphes sont isomorphe. Si vous avez des étiquettes, ajoutez-les dans les hachures internes que vous calculez pour chaque noeud (et à chaque étape).

pour en savoir plus sur vous pouvez consulter mon billet ici:

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

l'algorithme ci-dessus a été mis en œuvre à l'intérieur de la base de données relationnelles fonctionnelles" madIS". Vous pouvez trouver le code source de l'algorithme ici:

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

avec l'ordre approprié de vos descendants (et si vous avez un seul noeud racine, pas un donné, mais avec l'ordre approprié (peut-être en incluant un noeud racine virtuel)), la méthode pour Hasher un arbre devrait fonctionner avec une légère modification.

exemple de code dans cette réponse D'empilage , la modification serait de trier les enfants dans un ordre déterministe (augmentation du hash?) avant le hachage de la mère.

même si vous avez plusieurs racines possibles, vous pouvez créer une racine simple synthétique, avec toutes les racines comme enfants.