arsenal.datastructures package

Submodules

arsenal.datastructures.orderedset module

OrderedSet – a set which remembers insertion order.

class arsenal.datastructures.orderedset.OrderedSet[source]

Bases: object

Set which remembers insertion ordering allowed iteration while changing size and determinism.

add(item)[source]
list
set

arsenal.datastructures.unionfind module

UnionFind.py

Union-find data structure. Based on Josiah Carlson’s code, http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912 with significant additional changes by D. Eppstein.

class arsenal.datastructures.unionfind.UnionFind(elements=None)[source]

Bases: object

Union-Find data structure.

Each UnionFind instance X maintains a family of disjoint sets of hashable objects, supporting the following two methods:

  • X[item] returns a name for the set containing the given item. Each set is named by an arbitrarily-chosen one of its members; as long as the set remains unchanged it will keep the same name. If the item is not yet part of a set in X, a new singleton set is created for it.
  • X.union(item1, item2, …) merges the sets containing each item into a single larger set. If any item is not yet part of a set in X, it is added to X as one of the members of the merged set.
add(x)[source]

Add element x as a singleton

class_of(x)[source]
classes()[source]
connected(x, y)[source]
elems
roots()[source]
union(*objects)[source]

Find the sets containing the objects and merge them all.

Module contents