La Mise En Œuvre Disjoints Ensemble Du Système En Python

Ce que j'ai à ce jour est en grande partie basée sur la page 571 de "Introduction Aux Algorithmes" par Cormen et coll.

J'ai une classe de Nœud en python qui représente un ensemble:

class Node:
    def __init__(self, parent, rank = 0):
        self.parent = parent
        self.rank = rank

Cette mise en œuvre va utiliser un List de Nœuds comme la forêt (je suis ouvert à de meilleures façons de stocker les ensembles).

Initialize() renvoie une liste de Nœuds, que je stocke dans la variable set et passer dans les autres fonctions.

Find recherches à travers la forêt pour la valeur et le rendement de l'ensemble qu'il paraît. J'ai choisi d'utiliser for s in range(len(set)): de sorte que, dans la récursivité j'ai pu réduire la liste des ensembles étant passé par set[s:].

def Find(set, value):
    for s in range(len(set)):
        if value != set[s].parent:
            set[s].parent = Find(set[s:], set[s].parent)
        return set[s]

Merge fusionne jeux dans la forêt par les trouver et de les promouvoir au rang plus élevé ensemble.

def Merge(set, value1, value2):
    set_val_1 = Find(set, value1)
    set_val_2 = Find(set, value2)
    if set_val_1.rank > set_val_2.rank:
        set_val_2.parent = set_val_1
    else:
        set_val_1.parent = set_val_2
        if set_val_1.rank == set_val_2.rank:
            set_val_2.rank += 1

J'obtiens des erreurs quand j'en fais Finds et Merges, à savoir Find ne retourne pas le bon jeu, et donc je ne sais pas si Merge fonctionne correctement. J'apprécierais un peu d'aide pour s'assurer les fonctions sont mises en œuvre correctement.

OriginalL'auteur Jordan | 2011-02-23

  1. 2

    Je n'ai pas la dernière édition de ce livre, mais cela n'a pas l'air tout à fait comme un disjoints-ensemble de la forêt.

    Je pense que votre erreur est de penser que la forêt doit être conservé dans une collection et que vous avez à parcourir cette collection de faire les opérations sur les nœuds. Supprimer set de Merge() et Find() et de mettre en œuvre Find() comme

    def Find(n):
    if n != n.parent:
        n.parent = Find(n.parent)
    return n.parent

    exactement comme dans le livre. Ensuite, ajoutez un MakeSet() qui renvoie un seul correctement initialisé, nœud, et peut-être un SameSet() fonction:

    def SameSet(n1, n2):
    return Find(n1) == Find(n2)

    Vous avez maintenant un travail disjoints ensemble de la mise en œuvre.

    Dans un monde réel "travailler ensemble disjoint de mise en œuvre", il y en avait une facilité pour itérer sur tous les jeux, une facilité à retourner tous les membres de l'ensemble qui comprend un nœud donné, et le Nœud de la classe aurait une sorte de "charge utile" de l'attribut.
    Par "travail", je veux seulement dire que cela fonctionne. Brandon deux liens vers des implémentations, dont l'une à partir d'un Python cookbook. Aucune de ces magasin de charges utiles et de plus ils ne l'appui d'une itération sur les jeux ou la récupération de tous les membres d'un ensemble. Mais ils sont encore utiles pour le cas d'utilisation de garder la trace des composants raccordés.
    les nœuds tel que défini par les OP ont seulement un parent et un rang; les composants qu'est-ce à suivre??? "Un à partir d'un Python cookbook", met en œuvre la charge utile dans l'exemple de code (voir la section "label"), et la mention de itertools.groupby suggère qu'il pourrait être en train de faire quelque chose d'utile. Dans Eppstein du code, le "hashable objets" sont la "charge utile".
    Ma lecture de Brandon exemples a été un peu bâclé, désolé. Les nœuds transporter une charge utile, comme dans la Recette de démonstration, et le virus d'Epstein de mise en œuvre (ce qui n'est pas à partir d'un vrai livre, mon erreur!) t autoriser l'itération à travers toutes les clés. Mais le disjoints jeu est à propos de la connectivité, et non des valeurs. Stocker l'ensemble de la valeur, et non l'inverse. Ensuite, vous pouvez demander si deux valeurs sont connectés ou rejoindre des deux valeurs. C'est ce qui est gardé la trace de.
    Je l'ai regardé plus de mes de mise en œuvre et joué un peu avec un peu de choses, la question fondamentale, j'ai eu était que j'étais la comparaison des résultats des Find les opérations de retour Node objets. J'ai vraiment besoin de retourner Node.parent qui sont ints (dans mon cas) et effectivement un sens à comparer (par opposition à la mention de Node objets. Ligne de fond, vous obtenez l'accepter.

    OriginalL'auteur antonakos

  2. 4

    Avez-vous regardé toute autre existant implémentations?

    OriginalL'auteur Brandon

  3. 2

    En supposant que chaque nœud est initialisé à sa propre mère:

    def Find(node):
    while node is not node.parent:
        node = node.parent
    return node
    Machin: Comment pourrais-je parcourir toute ma collection de jeux pour trouver ce qui définir le nœud est dans?
    Si vous voulez dire que l'ensemble de leader: leader = Find(node). Si tu veux une liste de membre nœuds: leader = Find(node); return [x for x in list_of_nodes if Find(x) is leader]
    Attention que cela ne fait pas de chemin de compression.
    Machin: +1 pour être le plus utile à ce jour. Ce que je voulais dire par la collection de jeux, la liste qui contient tous les ensembles dans mon problème c'est à dire ce que Initialize retourne.
    Merci pour le +1. Je sais ce que tu veux dire par la collection de jeux, je l'ai appelée "list_of_nodes". Ma question était: quelle RÉPONSE avez-vous besoin pour votre "qui nœud est dans la requête"? La cible du jeu de représentant/chef de nœud, ou un conteneur de chargement de nœuds dans l'objectif fixé?

    OriginalL'auteur John Machin

  4. 1

    À l'aide de cette la mise en œuvre comme un point de départ, j'ai créé une nouvelle python classe permettant de gérer des ensembles disjoints, qui prend également en charge la persistance à l'aide d'un MongoDb.

    Avec ma classe, vous devriez être capable, par exemple, à:

    • Créer une instance de UnionFind(), qui utilise python construire-dans les dictionnaires par défaut, et décider plus tard de consolidate() vos résultats dans une collection MongoDb
    • Créer une instance de UnionFind à partir d'une collection de MongoDb et de l'utiliser directement.

    Vous pourriez vouloir vérifier le code sur github.

    Cheers,
    Simone

    OriginalL'auteur simonemainardi

  5. 0

    Le Wikipedia page fournit des pseudo-code de la base les opérations de sur disjoints-définir la structure de données. Voici un port direct à Python (emploie chemin de la compression et de l'union par rang):

    class Node:
    """Represents an element of a set."""
    def __init__(self, id):
        self.id = id
        self.parent = self
        self.rank = 0
        self.size = 1

    def __repr__(self):
        return 'Node({!r})'.format(self.id)


def Find(x):
    """Returns the representative object of the set containing x."""
    if x.parent is not x:
        x.parent = Find(x.parent)
    return x.parent


def Union(x, y):
    """Combines the sets x and y belong to."""
    xroot = Find(x)
    yroot = Find(y)

    # x and y are already in the same set
    if xroot is yroot:
        return

    # x and y are not in same set, so we merge them
    if xroot.rank < yroot.rank:
        xroot, yroot = yroot, xroot  # swap xroot and yroot

    # merge yroot into xroot
    yroot.parent = xroot
    xroot.size += yroot.size
    if xroot.rank == yroot.rank:
        xroot.rank = xroot.rank + 1

    Démo:

    >>> a, b, c = map(Node, 'abc')
>>> Find(a), Find(b), Find(c)
(Node('a'), Node('b'), Node('c'))
>>> Find(a).size
1
>>> Union(a, b)
>>> Union(b, c)
>>> Find(a), Find(b), Find(c)
(Node('a'), Node('a'), Node('a'))
>>> Find(a).size
3

    OriginalL'auteur Eugene Yarmash