openanalysis.base_data_structures module

class openanalysis.base_data_structures.UnionFind

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.

union(*objects)

Find the sets containing the objects and merge them all.

class openanalysis.base_data_structures.PriorityQueue

A simple Priority Queue Implementation for usage in algorithms. Internally uses heapq to maintain min-heap and tasks are added as tuples (priority,task) to queue. To make the order of tasks with same priority clear, count of element insertion is added to the tuple, making it as (priority,count,task), which means that tasks are first ordered by priority then by count

add_task(task, priority)

Add a task to priority queue

Parameters:

• task – task to be added to queue
• priority – priority of the task, must be orderable

remove(task)

Removes the tasks from Queue Currently it takes O(n) time to find , and O(log n) to remove, making it O(n) further improvements can be done

Parameters:task – task to removed from the Queue

remove_min()

Removes the minimum element of heap

Returns:task with less priority

update_task(task, new_priority)

Updates the priority of exsisting task in Queue Updation is implemented as deletion and insertion, takes O(n) time further improvements can be done

Parameters:

• task – task to be updated
• new_priority – new value of priority