Data Structures

Implementing Data Structures purely in Python.

Quick Start Guide

# import the required data structure
from pygorithm.data_structures import stack

# create a stack with default stack size 10
myStack = stack.Stack()
myStack.push(2)

# print the contents of stack
print(myStack)

Features

  • Data Structures implementations available:
    • Stack
      • Stack (data_structures.stack.Stack)
      • Infix to Postfix conversion (data_structures.stack.InfixToPostfix)
    • Queue
      • Queue (data_structures.queue.Queue)
      • Deque (data_structures.queue.Deque)
    • Linked List
      • Singly Linked List (data_structures.linked_list.SinglyLinkedList)
      • Doubly Linked List (data_structures.linked_list.DoublyLinkedList)
    • Tree
      • Binary Tree (data_structures.tree.BinaryTree)
      • Binary Seach Tree (data_structures.tree.BinarySearchTree)
    • Graph
      • Graph (data_structures.graph.Graph)
      • Topological Sort (data_structures.graph.TopologicalSort)
      • Check cycle in Directed Graph (data_structures.graph.CheckCycleDirectedGraph)
      • Check cycle in Undirected Graph (data_structures.graph.CheckCycleUndirectedGraph)
    • Heap
      • Heap (data_structures.heap.Heap)
    • QuadTree
      • QuadTree (data_structures.quadtree.QuadTree)
  • Get the code used for any of the implementation
from pygorithm.data_structures.stack import Stack

myStack = Stack()
print(myStack.get_code())
  • To see all the available functions in a module, you can just type help() with the module name as argument. For example,
>>> from pygorithm import data_structures
>>> help(data_structures)
        Help on package pygorithm.data_structures in pygorithm:

        NAME
        pygorithm.data_structures

        PACKAGE CONTENTS
        graph
        heap
        linked_list
        modules
        queue
        stack
        tree

Stack

Author: OMKAR PATHAK Created On: 3rd August 2017

Stack

class pygorithm.data_structures.stack.Stack(limit=10)[source]

Stack object

push(data)[source]

pushes an item into the stack returns -1 if the stack is empty

pop()[source]

pops the topmost item from the stack returns -1 if the stack is empty

peek()[source]

returns the topmost element of the stack returns -1 if the stack is empty

is_empty()[source]

checks if the stack is empty returns boolean value, True or False

size()[source]

returns the current size of the stack

static get_code()[source]

returns the code for current class

Infix to Postfix

class pygorithm.data_structures.stack.InfixToPostfix(expression=None, stack=None)[source]

get the postfix of the given infix expression

infix_to_postfix()[source]

function to generate postfix expression from infix expression

static get_code()[source]

returns the code of the current class

Queue

Author: OMKAR PATHAK Created On: 3rd August 2017

Queue

class pygorithm.data_structures.queue.Queue(limit=10)[source]

Queue implementation

size()[source]

returns the current size of the queue

is_empty()[source]

checks if the queue is empty

enqueue(data)[source]

inserts an item into the queue

dequeue()[source]

pops an item from the queue which was first inserted

get_code()[source]

Return source code for Queue class :return:

Deque

class pygorithm.data_structures.queue.Deque(limit=10)[source]

Deque implementation

is_empty()[source]

checks whether the deque is empty

is_full()[source]

checks whether the deque is full

insert_rear(data)[source]

inserts an element at the rear end of the deque

insert_front(data)[source]

inserts an element at the front end of the deque

delete_rear()[source]

deletes an element from the rear end of the deque

delete_front()[source]

deletes an element from the front end of the deque

static get_code()[source]

returns the code of the current class

Linked Lists

Author: OMKAR PATHAK Created On: 5th August 2017

Linked l_list and Node can be accommodated in separate classes for convenience

Node

class pygorithm.data_structures.linked_list.Node(data, next_node=None)[source]

Node class for creating a node for linked list. Each node has its data and a pointer that points to next node in the Linked l_list

static get_code()[source]

return the code for the current class

Singly Linked List

class pygorithm.data_structures.linked_list.SinglyLinkedList[source]

Defining the head of the linked list

get_data()[source]

prints the elements in the linked list

insert_at_start(data)[source]

insert an item at the beginning of the linked list

insert_after(next_node_data, data)[source]

insert an item after an element in the linked list

insert_at_end(data)[source]

insert an item at the end of the linked list

delete(data)[source]

to delete specified element from the linked list

static get_code()[source]

return the code for the current class

Doubly Linked List

class pygorithm.data_structures.linked_list.DoublyLinkedList[source]

DoublyLinkedList Class

get_data()[source]

prints the elements in the linked list

insert_at_start(data)[source]

insert an element at the beginning of the linked list

insert_at_end(data)[source]

insert an element at the end of the linked list

delete(data)[source]

to delete specified element from the linked list

static get_code()[source]

returns the code of the current class

Tree

Author: OMKAR PATHAK Created On: 9th August 2017

Node class to create a node for binary tree

Node

class pygorithm.data_structures.tree.Node(data=None)[source]

Node class for creating a node for tree. Each node has its data and a pointer that points to next node in the Linked List

set_left(node)[source]

for setting the left child of the node

set_right(node)[source]

for setting the right child of the node

get_left()[source]

for getting the left child of the node

get_right()[source]

for getting the right child of the node

set_data(data)[source]

for setting the data of the node

get_data()[source]

for getting the data of the node

static get_code()[source]

returns the code of the current class

Binary Tree

class pygorithm.data_structures.tree.BinaryTree[source]

BinaryTree class to create a binary tree

inorder(root)[source]

in this we traverse first to the leftmost node, then print its data and then traverse for rightmost node :param root: Node object

preorder(root)[source]

in this we first print the root node and then traverse towards leftmost node and then to the rightmost node :param root: Node object

postorder(root)[source]

in this we first traverse to the leftmost node and then to the rightmost node and then print the data :param root: Node object

static get_code()[source]

returns the code of the current class

Binary Search Tree Node

class pygorithm.data_structures.tree.BSTNode(data)[source]

class for creating a node for binary Search tree

set_left(node)[source]

for setting the left child of the node

set_right(node)[source]

for setting the right child of the node

get_left()[source]

returns the left child of the current node

get_right()[source]

returns the right child of the current node

set_data(data)[source]

for setting the data of a node

get_data()[source]

returns the data of the current node

insert(data)[source]

For inserting the data in the Tree

static min_val_bst_node(bst_node)[source]

for returning the node with the lowest value

delete(data)[source]

For deleting the bst_node

find(data)[source]

This function checks whether the specified data is in tree or not

inorder(root)[source]

in this we first traverse to the leftmost node and then print the data and then move to the rightmost child :param root: Node object

preorder(root)[source]

in this we first print the root node and then traverse towards leftmost node and then to the rightmost node :param root: Node object

postorder(root)[source]

in this we first traverse to the leftmost node and then to the rightmost node and then print the data :param root: Node object

static get_code()[source]

returns the code of current class

Binary Search Tree

class pygorithm.data_structures.tree.BinarySearchTree[source]
insert(data)[source]

inserts a node in the tree

delete(data)[source]

deletes the node with the specified data from the tree

preorder()[source]

finding the preorder of the tree

inorder()[source]

finding the inorder of the tree

postorder()[source]

finding the postorder of the tree

static get_code()[source]

returns the code of the current class

Graph

Author: OMKAR PATHAK Created On: 12th August 2017

Graph

class pygorithm.data_structures.graph.Graph[source]

Graph object Creates the graph

print_graph()[source]

Prints the contents of the graph

add_edge(from_vertex, to_vertex)[source]

Adds an edge in the graph

get_code()[source]

returns the code for the current class

Weighted Graph

class pygorithm.data_structures.graph.WeightedGraph[source]

WeightedGraph object A graph with a numerical value (weight) on edges

add_edge(u, v, weight)[source]
Parameters:
  • u – from vertex - type : integer
  • v – to vertex - type : integer
  • weight – weight of the edge - type : numeric
print_graph()[source]

Print the graph :return: None

kruskal_mst()[source]

Kruskal algorithm for finding the minimum spanning tree of a weighted graph. This version use a union-find data structure. More detailed info here: https://en.wikipedia.org/wiki/Kruskal%27s_algorithm Author: Michele De Vita <mik3dev@gmail.com>

static kruskal_time_complexity()[source]

Return time complexity of kruskal :return: string

classmethod kruskal_code()[source]

Returns the code for current class

Weighted Undirected Graph

class pygorithm.data_structures.graph.WeightedUndirectedGraph[source]

WeightedUndirectedGraph object A graph with a numerical value (weight) on edges, which is the same for both directions in an undirected graph.

add_edge(u, v, weight)[source]

Adds the specified edge to this graph. If the edge already exists, this will only modify the weight (not create duplicates). :param u: from vertex :param v: to vertex :param weight: weight of the edge - type : numeric

get_edge_weight(u, v)[source]

Gets the weight between u and v if such an edge exists, or None if it does not. :param u: one edge :param v: the other edge :return: numeric or None

remove_edge(edge, other_edge_or_none=None)[source]

Removes the specified edge from the grid entirely or, if specified, the connection with one other edge. Behavior is undefined if the connection does not exist. :param edge: the edge to remove :param other_edge_or_none: an edge connected to edge or none

gridify(size, weight)[source]

Constructs connections from a square grid starting at (0, 0) until (size-1, size-1) with connections between adjacent and diagonal nodes. Diagonal nodes have a weight of weight*sqrt(2) :param size: the size of the square grid to construct - type : integer :param weight: the weight between orthogonal nodes. - type: numeric :return: None

Topological Sort

class pygorithm.data_structures.graph.TopologicalSort[source]
topological_sort()[source]

function for sorting graph elements using topological sort

get_code()[source]

returns the code for the current class

Check Cycle in Directed Graph

class pygorithm.data_structures.graph.CheckCycleDirectedGraph[source]

Class to check cycle in directed graph

print_graph()[source]

for printing the contents of the graph

add_edge(from_vertex, to_vertex)[source]

function to add an edge in the graph

check_cycle()[source]

This function will return True if graph is cyclic else return False

static get_code()[source]

returns the code for the current class

Check Cycle in Undirected Graph

class pygorithm.data_structures.graph.CheckCycleUndirectedGraph[source]

Class to check cycle in undirected graph

print_graph()[source]

for printing the contents of the graph

add_edge(from_vertex, to_vertex)[source]

for adding the edge between two vertices

check_cycle()[source]

This function will return True if graph is cyclic else return False

static get_code()[source]

returns the code for the current class

Heap

Author: ALLSTON MICKEY Contributed: OMKAR PATHAK Created On: 11th August 2017

Heap

class pygorithm.data_structures.heap.Heap(limit=10)[source]

min-heap implementation as queue

static parent_idx(idx)[source]

retrieve the parent

static left_child_idx(idx)[source]

retrieve the left child

static right_child_idx(idx)[source]

retrieve the right child

insert(data)[source]

inserting an element in the heap

heapify_up()[source]

Start at the end of the tree (last enqueued item).

Compare the rear item to its parent, swap if the parent is larger than the child (min-heap property). Repeat until the min-heap property is met.

Best Case: O(1), item is inserted at correct position, no swaps needed Worst Case: O(log n), item needs to be swapped throughout all levels of tree

pop()[source]

Removes the lowest value element (highest priority, at root) from the heap

favorite(parent)[source]

Determines which child has the highest priority by 3 cases

heapify_down()[source]

Select the root and sift down until min-heap property is met.

While a favorite child exists, and that child is smaller than the parent, swap them (sift down).

Best Case: O(1), item is inserted at correct position, no swaps needed Worst Case: O(logn), item needs to be swapped throughout all levels of tree

get_code()[source]

returns the code for the current class

Trie

Author: MrDupin

Trie

class pygorithm.data_structures.trie.Trie[source]
insert(word)[source]

Inserts a word in the trie. Starting from the root, move down the trie following the path of characters in the word. If the nodes for the word characters end, add them. When the last char is added, mark it as a word-ending node.

search(word)[source]

Searches for given word in trie. We want to find the last node for the word. If we can’t, then it means the word is not in the trie.

find_words(prefix)[source]

Find all words with the given prefix

find_final_node(word)[source]

Returns the last node in given word. The process goes like this: Start from the root. For every char in word, go down one level. If we can’t go down a level, then the word doesn’t exist. If we do, and the current char is the last char of the word and the node we are currently at is a word, then we have found the given word.

build_word_list(v, cWord)[source]
Recursively builds the list of words.
  • v: Node to check
  • cWord : The word built up to v

QuadTree

Author: Timothy Moore Created On: 31th August 2017

Defines a two-dimensional quadtree of arbitrary depth and bucket size.

QuadTreeEntity

class pygorithm.data_structures.quadtree.QuadTreeEntity(aabb)[source]

This is the minimum information required for an object to be usable in a quadtree as an entity. Entities are the things that you are trying to compare in a quadtree.

Variables:aabb – the axis-aligned bounding box of this entity
__init__(aabb)[source]

Create a new quad tree entity with the specified aabb

Parameters:aabb (pygorithm.geometry.rect2.Rect2) – axis-aligned bounding box
__repr__()[source]

Create an unambiguous representation of this entity.

Example:

from pygorithm.geometry import (vector2, rect2)
from pygorithm.data_structures import quadtree

_ent = quadtree.QuadTreeEntity(rect2.Rect2(5, 5))

# prints quadtreeentity(aabb=rect2(width=5, height=5, mincorner=vector2(x=0, y=0)))
print(repr(_ent))
Returns:unambiguous representation of this quad tree entity
Return type:string
__str__()[source]

Create a human readable representation of this entity

Example:

from pygorithm.geometry import (vector2, rect2)
from pygorithm.data_structures import quadtree

_ent = quadtree.QuadTreeEntity(rect2.Rect2(5, 5))

# prints entity(at rect(5x5 at <0, 0>))
print(str(_ent))
Returns:human readable representation of this entity
Return type:string
__weakref__

list of weak references to the object (if defined)

QuadTree

class pygorithm.data_structures.quadtree.QuadTree(bucket_size, max_depth, location, depth=0, entities=None)[source]

A quadtree is a sorting tool for two-dimensional space, most commonly used to reduce the number of required collision calculations in a two-dimensional scene. In this context, the scene is stepped without collision detection, then a quadtree is constructed from all of the boundaries

Caution

Just because a quad tree has split does not mean entities will be empty. Any entities which overlay any of the lines of the split will be included in the parent of the quadtree.

Tip

It is important to tweak bucket size and depth to the problem, but a common error is too small a bucket size. It is typically not reasonable to have a bucket size smaller than 16; A good starting point is 64, then modify as appropriate. Larger buckets reduce the overhead of the quad tree which could easily exceed the improvement from reduced collision checks. The max depth is typically just a sanity check since depth greater than 4 or 5 would either indicate a badly performing quadtree (too dense objects, use an r-tree or kd-tree) or a very large world (where an iterative quadtree implementation would be appropriate).

Variables:
  • bucket_size – maximum number objects per bucket (before max_depth)
  • max_depth – maximum depth of the quadtree
  • depth – the depth of this node (0 being the topmost)
  • location – where this quad tree node is situated
  • entities – the entities in this quad tree and in NO OTHER related quad tree
  • children – either None or the 4 QuadTree children of this node
__init__(bucket_size, max_depth, location, depth=0, entities=None)[source]

Initialize a new quad tree.

Warning

Passing entities to this quadtree will NOT cause it to split automatically! You must call think() for that. This allows for more predictable performance per line.

Parameters:
  • bucket_size (int) – the number of entities in this quadtree
  • max_depth (int) – the maximum depth for automatic splitting
  • location (pygorithm.geometry.rect2.Rect2) – where this quadtree is located
  • depth (int) – the depth of this node
  • entities (list of QuadTreeEntity or None for empty list) – the entities to initialize this quadtree with
think(recursive=False)[source]

Call split() if appropriate

Split this quad tree if it has not split already and it has more entities than bucket_size and depth is less than max_depth.

If recursive is True, think is called on the children with recursive set to True after splitting.

Parameters:recursive (bool) – if think(True) should be called on children (if there are any)
split()[source]

Split this quadtree.

Caution

A call to split will always split the tree or raise an error. Use think() if you want to ensure the quadtree is operating efficiently.

Caution

This function will not respect bucket_size or max_depth.

Raises:ValueError – if children is not empty
get_quadrant(entity)[source]

Calculate the quadrant that the specified entity belongs to.

Touching a line is considered overlapping a line. Touching is determined using math.isclose()

Quadrants are:

  • -1: None (it overlaps 2 or more quadrants)
  • 0: Top-left
  • 1: Top-right
  • 2: Bottom-right
  • 3: Bottom-left

Caution

This function does not verify the entity is contained in this quadtree.

This operation takes O(1) time.

Parameters:entity (QuadTreeEntity) – the entity to place
Returns:quadrant
Return type:int
insert_and_think(entity)[source]

Insert the entity into this or the appropriate child.

This also acts as thinking (recursively). Using insert_and_think() iteratively is slightly less efficient but has more predictable performance than initializing with a large number of entities then thinking is slightly faster but may hang. Both may exceed recursion depth if max_depth is too large.

Parameters:entity (QuadTreeEntity) – the entity to insert
retrieve_collidables(entity, predicate=None)[source]

Find all entities that could collide with the specified entity.

Warning

If entity is, itself, in the quadtree, it will be returned. The predicate may be used to prevent this using your preferred equality method.

The predicate takes 1 positional argument (the entity being considered) and returns False if the entity should never be returned, even if it might collide with the entity. It should return True otherwise.

Parameters:
  • entity (QuadTreeEntity) – the entity to find collidables for
  • predicate (types.FunctionType or None) – the predicate
Returns:

potential collidables (never `None)

Return type:

list of QuadTreeEntity

find_entities_per_depth()[source]

Calculate the number of nodes and entities at each depth level in this quad tree. Only returns for depth levels at or equal to this node.

This is implemented iteratively. See __str__() for usage example.

Returns:dict of depth level to number of entities
Return type:dict int: int
find_nodes_per_depth()[source]

Calculate the number of nodes at each depth level.

This is implemented iteratively. See __str__() for usage example.

Returns:dict of depth level to number of nodes
Return type:dict int: int
sum_entities(entities_per_depth=None)[source]

Sum the number of entities in this quad tree and all lower quad trees.

If entities_per_depth is not None, that array is used to calculate the sum of entities rather than traversing the tree. Either way, this is implemented iteratively. See __str__() for usage example.

Parameters:entities_per_depth (dict int: (int, int) or None) – the result of find_entities_per_depth()
Returns:number of entities in this and child nodes
Return type:int
calculate_avg_ents_per_leaf()[source]

Calculate the average number of entities per leaf node on this and child quad trees.

In the ideal case, the average entities per leaf is equal to the bucket size, implying maximum efficiency. Note that, as always with averages, this might be misleading if this tree has reached its max depth.

This is implemented iteratively. See __str__() for usage example.

Returns:average number of entities at each leaf node
Return type:numbers.Number
calculate_weight_misplaced_ents(sum_entities=None)[source]

Calculate a rating for misplaced entities.

A misplaced entity is one that is not on a leaf node. That weight is multiplied by 4*remaining maximum depth of that node, to indicate approximately how many additional calculations are required.

The result is then divided by the total number of entities on this node (either calculated using sum_entities() or provided) to get the approximate cost of the misplaced nodes in comparison with the placed nodes. A value greater than 1 implies a different tree type (such as r-tree or kd-tree) should probably be used.

This is implemented iteratively. See __str__() for usage example.

Parameters:sum_entities (int or None) – the number of entities on this node
Returns:weight of misplaced entities
Return type:numbers.Number
__repr__()[source]

Create an unambiguous representation of this quad tree.

This is implemented iteratively.

Example:

from pygorithm.geometry import (vector2, rect2)
from pygorithm.data_structures import quadtree

# create a tree with a up to 2 entities in a bucket that 
# can have a depth of up to 5.
_tree = quadtree.QuadTree(1, 5, rect2.Rect2(100, 100))

# add a few entities to the tree
_tree.insert_and_think(quadtree.QuadTreeEntity(rect2.Rect2(2, 2, vector2.Vector2(5, 5))))
_tree.insert_and_think(quadtree.QuadTreeEntity(rect2.Rect2(2, 2, vector2.Vector2(95, 5))))

# prints quadtree(bucket_size=1, max_depth=5, location=rect2(width=100, height=100, mincorner=vector2(x=0, y=0)), depth=0, entities=[], children=[quadtree(bucket_size=1, max_depth=5, location=rect2(width=50.0, height=50.0, mincorner=vector2(x=0, y=0)), depth=1, entities=[quadtreeentity(aabb=rect2(width=2, height=2, mincorner=vector2(x=5, y=5)))], children=None), quadtree(bucket_size=1, max_depth=5, location=rect2(width=50.0, height=50.0, mincorner=vector2(x=50.0, y=0)), depth=1, entities=[quadtreeentity(aabb=rect2(width=2, height=2, mincorner=vector2(x=95, y=5)))], children=None), quadtree(bucket_size=1, max_depth=5, location=rect2(width=50.0, height=50.0, mincorner=vector2(x=50.0, y=50.0)), depth=1, entities=[], children=None), quadtree(bucket_size=1, max_depth=5, location=rect2(width=50.0, height=50.0, mincorner=vector2(x=0, y=50.0)), depth=1, entities=[], children=None)])
Returns:unambiguous, recursive representation of this quad tree
Return type:string
__str__()[source]

Create a human-readable representation of this quad tree

Caution

Because of the complexity of quadtrees it takes a fair amount of calculation to produce something somewhat legible. All returned statistics have paired functions. This uses only iterative algorithms to calculate statistics.

Example:

from pygorithm.geometry import (vector2, rect2)
from pygorithm.data_structures import quadtree

# create a tree with a up to 2 entities in a bucket that 
# can have a depth of up to 5.
_tree = quadtree.QuadTree(2, 5, rect2.Rect2(100, 100))

# add a few entities to the tree
_tree.insert_and_think(quadtree.QuadTreeEntity(rect2.Rect2(2, 2, vector2.Vector2(5, 5))))
_tree.insert_and_think(quadtree.QuadTreeEntity(rect2.Rect2(2, 2, vector2.Vector2(95, 5))))

# prints quadtree(at rect(100x100 at <0, 0>) with 0 entities here (2 in total); (nodes, entities) per depth: [ 0: (1, 0), 1: (4, 2) ] (allowed max depth: 5, actual: 1), avg ent/leaf: 0.5 (target 1), misplaced weight 0.0 (0 best, >1 bad)
print(_tree)
Returns:human-readable representation of this quad tree
Return type:string
static get_code()[source]

Get the code for the QuadTree class

Returns:code for QuadTree
Return type:string
__weakref__

list of weak references to the object (if defined)