Skip to main content
Join the official 2019 Python Developers SurveyStart the survey!

UFx is a pure python library that implements the disjoint-set data structure which allows the union-find operations.

Project description

UFx is a pure python library that implements the disjoint-set data structure which allows the union-find operations.

Two implementations are proposed.

  • uf_hash using python dictionary
  • uf_tree using nodes linked each to its ansestror

Those implementations are design for hashable types. However it is possible to use the UFNode class present in the uf_tree implementation with non-hashable types (see the API documentation part below).

UFx was only tested with python 2.7, python 3.5 and pypy but may work with other versions python virtual machines.

Performances

The uf_hash implementation is the recommanded one. It performs well with the classic python virtual machine. The uf_tree implementation is really slow due to the poor performances of python with pointer like based data structures. The use of another python virtual machine like pypy its recommanded when using the uf_tree implementation.

TODO: Table of computation speed and memory consumption

API documentation

Import

You can import one of the implementation of the disjoint-set data structure

from ufx import uf_tree as ufx

or

from ufx import uf_hash as ufx

Quick Example

import sys
import random
uf = ufx.UnionFind()
az = "abcdefghijklmnopqrstuvwxyz"
az += az.upper()
for e in az:
    uf.make_set(e)
i = 0
while i < 26:
    i += 1
    uf.union(random.choice(az), random.choice(az))
print(uf)
print(uf.get_size('a'))
uf.clear()
print(uf)

Hashable types

TODO

Non-hashable types

Look on the class UFNode

Project details


Release history Release notifications

This version

1.0

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for UFx, version 1.0
Filename, size File type Python version Upload date Hashes
Filename, size UFx-1.0.0.tar.gz (4.6 kB) File type Source Python version None Upload date Hashes View hashes

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN SignalFx SignalFx Supporter DigiCert DigiCert EV certificate StatusPage StatusPage Status page