Valeur de hachage pour le graphe acyclique dirigé

comment transformer un graphe acyclique dirigé en une valeur de hachage telle que deux graphes isomorphes donnent la même valeur? Il est acceptable, mais indésirable pour deux graphiques isomorphiques de hachage à des valeurs différentes, qui est ce que j'ai fait dans le code ci-dessous. Nous pouvons supposer que le nombre de sommets dans le graphique est au plus 11.

je suis particulièrement intéressé par le code Python.

voilà ce que j'ai fait. Si self.lt est un mapping de noeud aux descendants (pas aux enfants!), puis je réétiquette les noeuds selon un tri topologique modifié (qui préfère ordonner les éléments avec plus de descendants d'abord si elle le peut). Ensuite, je hacherai le dictionnaire trié. Certains isomorphe graphiques de hachage à des valeurs différentes, d'autant que le nombre de nœuds augmente.

j'ai compris tout le code pour motiver mon cas d'utilisation. Je calcule le nombre de comparaisons nécessaires pour trouver la médiane de 7 nombres. Le plus que les graphes isomorphiques hachent à la même valeur le moins de travail qui doit être refait. J'ai envisagé de placer les plus gros composants connectés en premier, mais je n'ai pas vu comment le faire rapidement.

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))
23
demandé sur Neil G 2013-01-26 03:52:01

10 réponses

pour tester efficacement l'isomorphisme de graphe, vous voudrez utiliser nauty . Spécifiquement pour Python il y a le wrapper pynauty , mais je ne peux pas en attester la qualité (pour le compiler correctement j'ai dû faire quelques corrections simples sur son setup.py ). Si ce wrapper fait tout correctement, alors il simplifie beaucoup nauty pour les utilisations que vous êtes intéressés et il ne s'agit que d'une question de hashing pynauty.certificate(somegraph) - qui sera la même valeur pour isomorphe graphiques.

quelques tests rapides ont montré que pynauty donne le même certificat pour chaque graphe (avec la même quantité de Sommets). Mais c'est seulement en raison d'un problème mineur dans l'emballage lors de la conversion du graphe au format de nauty. Après avoir fixé cela, il fonctionne pour moi (j'ai également utilisé les graphiques à http://funkybee.narod.ru/graphs.htm pour comparaison). Voici le court patch qui considère également les modifications nécessaires dans 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;
10
répondu mmgp 2013-01-29 02:49:45

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 2 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 110 graphes restants sont acycliques et pour chaque graphe il peut y avoir jusqu'à 11! - environ 2 25 - 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.

8
répondu Daniel Brückner 2013-01-28 21:17:53

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.

3
répondu example 2013-01-28 17:44:58

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)
1
répondu distantTransformer 2013-01-28 10:33:23

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 .

1
répondu Ivaylo Strandjev 2017-05-23 12:17:17

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;
}
1
répondu maxim1000 2013-01-30 06:58:31

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.

1
répondu Gene 2013-01-30 23:25:47

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())))
1
répondu naitoon 2013-02-04 14:29:46

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

1
répondu estama 2017-03-20 10:45:47

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.

0
répondu Vatine 2017-05-23 12:00:29