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 union-find 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 (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¶
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]¶ min-heap 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 (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
-
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
-
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_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 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 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: 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 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 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)
- bucket_size – maximum number objects per bucket (before