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
Infix to Postfix¶
Queue¶
Author: OMKAR PATHAK Created On: 3rd August 2017
Linked Lists¶
Author: OMKAR PATHAK Created On: 5th August 2017
Linked l_list and Node can be accommodated in separate classes for convenience
Node¶
Singly Linked List¶
Tree¶
Author: OMKAR PATHAK Created On: 9th August 2017
Node class to create a node for binary tree
Node¶
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

Binary Search Tree Node¶

class
pygorithm.data_structures.tree.
BSTNode
(data)[source]¶ class for creating a node for binary Search tree

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

Graph¶
Author: OMKAR PATHAK Created On: 12th August 2017
Graph¶
Weighted Graph¶

class
pygorithm.data_structures.graph.
WeightedGraph
[source]¶ WeightedGraph object A graph with a numerical value (weight) on edges

get_weight
(u, v)[source]¶ Returns the weight of an edge between vertexes u and v. If there isnt one: return None.

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

kruskal_mst
()[source]¶ Kruskal algorithm for finding the minimum spanning tree of a weighted graph. This version use a unionfind data structure. More detailed info here: https://en.wikipedia.org/wiki/Kruskal%27s_algorithm Author: Michele De Vita <mik3dev@gmail.com>

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 (size1, size1) 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¶
Check Cycle in Directed Graph¶
Heap¶
Author: ALLSTON MICKEY Contributed: OMKAR PATHAK Created On: 11th August 2017
Heap¶

class
pygorithm.data_structures.heap.
Heap
(limit=10)[source]¶ minheap implementation as queue

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 (minheap property). Repeat until the minheap 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

heapify_down
()[source]¶ Select the root and sift down until minheap 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

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 wordending 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_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.

QuadTree¶
Author: Timothy Moore Created On: 31th August 2017
Defines a twodimensional 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 axisaligned bounding box of this entity 
__init__
(aabb)[source]¶ Create a new quad tree entity with the specified aabb
Parameters: aabb ( pygorithm.geometry.rect2.Rect2
) – axisaligned 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 twodimensional space, most commonly used to reduce the number of required collision calculations in a twodimensional 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 rtree or kdtree) 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 appropriateSplit this quad tree if it has not split already and it has more entities than
bucket_size
anddepth
is less thanmax_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
ormax_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: Topleft
 1: Topright
 2: Bottomright
 3: Bottomleft
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 placeReturns: 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 ifmax_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
 entity (

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 rtree or kdtree) 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 humanreadable 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: humanreadable 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)
 bucket_size – maximum number objects per bucket (before