pyalgs

pyalgs

Package pyalgs implements algorithms in the "Algorithms" book (http://algs4.cs.princeton.edu/home/) and Robert Sedgwick's Algorithms course using Python (Part I and Part II)

.. image:: https://travis-ci.org/chen0040/pyalgs.svg?branch=master :target: https://travis-ci.org/chen0040/pyalgs

.. image:: https://coveralls.io/repos/github/chen0040/pyalgs/badge.svg?branch=master :target: https://coveralls.io/github/chen0040/pyalgs?branch=master

.. image:: https://readthedocs.org/projects/pyalgs/badge/?version=latest :target: http://pyalgs.readthedocs.org/en/latest/?badge=latest

.. image:: https://scrutinizer-ci.com/g/chen0040/pyalgs/badges/quality-score.png?b=master :target: https://scrutinizer-ci.com/g/chen0040/pyalgs/?branch=master

More details are provided in the docs_ for implementation, complexities and further info.

Install pyalgs

Run the following command to install pyalgs using pip

.. code-block:: bash

$ pip install pyalgs

Features:

• Data Structure

  • Stack

    • Linked List
    • Array

  • Queue

    • Linked List
    • Array

  • Bag

  • HashSet

  • HashMap

    • Separate Chaining
    • Linear Probing

  • Binary Search Tree

  • Red Black Tree

  • Priority Queue

    • MinPQ
    • MaxPQ
    • IndexMinPQ

  • Graph

    • Simple graph
    • Edge weighted graph
    • Directed graph (digraph)
    • Directed edge weight graph

  • Search Tries (Symbol table with string-based keys)

    • R-way search tries
    • Ternary search tries

• Algorithms

  • Sorting

    • Selection Sort
    • Insertion Sort
    • Shell Sort
    • Merge Sort
    • Quick Sort
    • 3-Ways Quick Sort
    • Heap Sort

  • Selection

    • Binary Search

  • Shuffling

    • Knuth

  • Union Find

    • Quick Find
    • Weighted Quick Union with path compression

• Graph Algorithms

  • Search

    • Depth First Search
    • Breadth First Search

  • Connectivity

    • Connected Components
    • Strongly Connected Components

  • Topological Sorting

    • Depth First Reverse Post Order

  • Directed Cycle Detection

  • Minimum Spanning Tree

    • Kruskal
    • Prim (Lazy)
    • Prim (Eager)

  • Shortest Path

    • Dijkstra
    • Topological Sort (for directed acyclic graph, namely dag)
    • Bellman-Ford (for graph with negative weight as well)

  • MaxFlow MinCut

    • Ford-Fulkerson

• Strings

  • Longest Repeated Substring

  • String Sorting

    • LSD (Least Significant Digit first radix sorting)
    • MSD (Most Significant Digit first radix sorting)
    • 3-Ways String Quick Sort

  • String Search

    • Brute force
    • Rabin Karp
    • Boyer Moore
    • Knuth Morris Pratt

Usage:

Data Structure

Stack

.. code-block:: python

from pyalgs.data_structures.commons.stack import Stack

stack = Stack.create()
stack.push(10)
stack.push(1)

print [i for i in stack.iterate()]

print stack.is_empty()
print stack.size()

popped_item = stack.pop()
print popped_item

Queue

.. code-block:: python

from pyalgs.data_structures.commons.queue import Queue

queue = Queue.create()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)

print [i for i in queue.iterate()]

print queue.size()
print queue.is_empty()

deleted_item = queue.dequeue())
print deleted_item

Bag

.. code-block:: python

from pyalgs.data_structures.commons.bag import Bag

bag = Bag.create()

bag.add(10)
bag.add(20)
bag.add(30)

print [i for i in bag.iterate()]

print bag.size()
print bag.is_empty()

Minimum Priority Queue

.. code-block:: python

from pyalgs.data_structures.commons.priority_queue import MinPQ

pq = MinPQ.create()
pq.enqueue(10)
pq.enqueue(5)
pq.enqueue(12)
pq.enqueue(14)
pq.enqueue(2)

print pq.is_empty()
print pq.size()

print [i for i in pq.iterate()]

deleted = pq.del_min()
print(deleted)

Maximum Priority Queue

.. code-block:: python

from pyalgs.data_structures.commons.priority_queue import MaxPQ

pq = MaxPQ.create()
pq.enqueue(10)
pq.enqueue(5)
pq.enqueue(12)
pq.enqueue(14)
pq.enqueue(2)

print pq.is_empty()
print pq.size()

print [i for i in pq.iterate()]

deleted = pq.del_max()
print deleted

Symbol Table using Binary Search Tree

.. code-block:: python

from pyalgs.data_structures.commons.binary_search_tree import BinarySearchTree
bst = BinarySearchTree.create()

bst.put("one", 1)
bst.put("two", 2)
bst.put("three", 3)
bst.put("six", 6)
bst.put("ten", 10)

for key in bst.keys():
    print(key)

print bst.get("one"))
print bst.contains_key("two")

print bst.size()
print bst.is_empty()

bst.delete("one")

Symbol Table using Left Leaning Red Black Tree

.. code-block:: python

from pyalgs.data_structures.commons.binary_search_tree import BinarySearchTree
bst = BinarySearchTree.create_red_black_tree()

bst.put("one", 1)
bst.put("two", 2)
bst.put("three", 3)
bst.put("six", 6)
bst.put("ten", 10)

print bst.get("one"))
print bst.contains_key("two")

for key in bst.keys():
    print(key)

print bst.size()
print bst.is_empty()

bst.delete("one")

Symbol Table using Hashed Map

.. code-block:: python

from pyalgs.data_structures.commons.hashed_map import HashedMap
map = HashedMap.create()

map.put("one", 1)
map.put("two", 2)
map.put("three", 3)
map.put("six", 6)
map.put("ten", 10)

print map.get("one"))
print map.contains_key("two")

for key in map.keys():
    print(key)

print map.size()
print map.is_empty()

map.delete("one")

Symbol Table using Hashed Set

.. code-block:: python

from pyalgs.data_structures.commons.hashed_set import HashedSet
set = HashedSet.create()

set.add("one")
set.add("two")
set.add("three")
set.add("six")
set.add("ten")

print set.contains("two")

for key in set.iterate():
    print(key)

print set.size()
print set.is_empty()

set.delete("one")

Undirected Graph

.. code-block:: python

from pyalgs.data_structures.graphs.graph import Graph
def create_graph():
    G = Graph(100)

    G.add_edge(1, 2)
    G.add_edge(1, 3)

    print([i for i in G.adj(1)])
    print([i for i in G.adj(2)])
    print([i for i in G.adj(3)])

    print(G.vertex_count())
    return G

Directed Graph

.. code-block:: python

from pyalgs.data_structures.graphs.graph import Digraph
def create_digraph():
    G = Digraph(100)

    G.add_edge(1, 2)
    G.add_edge(1, 3)

    print([i for i in G.adj(1)])
    print([i for i in G.adj(2)])
    print([i for i in G.adj(3)])

    print(G.vertex_count())
    return G

Edge Weighted Graph

.. code-block:: python

from pyalgs.data_structures.graphs.graph import EdgeWeightGraph, Edge
def create_edge_weighted_graph():
    g = EdgeWeightedGraph(8)
    g.add_edge(Edge(0, 7, 0.16))
    g.add_edge(Edge(2, 3, 0.17))
    g.add_edge(Edge(1, 7, 0.19))
    g.add_edge(Edge(0, 2, 0.26))
    g.add_edge(Edge(5, 7, 0.28))

    print([edge for edge in G.adj(3)])

    print(G.vertex_count())
    print(', '.join([edge for edge in G.edges()]))
    return g

Directed Edge Weighted Graph

.. code-block:: python

from pyalgs.data_structures.graphs.graph import DirectedEdgeWeightedGraph, Edge
def create_edge_weighted_digraph():
    g = DirectedEdgeWeightedGraph(8)

    g.add_edge(Edge(0, 1, 5.0))
    g.add_edge(Edge(0, 4, 9.0))
    g.add_edge(Edge(0, 7, 8.0))
    g.add_edge(Edge(1, 2, 12.0))
    return g

Flow Network ( for max-flow min-cut problem)

.. code-block:: python

from pyalgs.data_structures.graphs.graph import FlowNetwork, FlowEdge
def create_flow_network():
g = FlowNetwork(8)
g.add_edge(FlowEdge(0, 1, 10))
g.add_edge(FlowEdge(0, 2, 5))
g.add_edge(FlowEdge(0, 3, 15))
g.add_edge(FlowEdge(1, 4, 9))
g.add_edge(FlowEdge(1, 5, 15))
g.add_edge(FlowEdge(1, 2, 4))
g.add_edge(FlowEdge(2, 5, 8))
g.add_edge(FlowEdge(2, 3, 4))
g.add_edge(FlowEdge(3, 6, 16))
g.add_edge(FlowEdge(4, 5, 15))
g.add_edge(FlowEdge(4, 7, 10))
g.add_edge(FlowEdge(5, 7, 10))
g.add_edge(FlowEdge(5, 6, 15))
g.add_edge(FlowEdge(6, 2, 6))
g.add_edge(FlowEdge(6, 7, 10))

return g

Symbol Table using R-ways Search Tries

.. code-block:: python

from pyalgs.data_structures.strings.search_tries import RWaySearchTries
st = RWaySearchTries()

st.put("one", 1)
st.put("two", 2)
st.put("three", 3)
st.put("six", 6)
st.put("ten", 10)

for key in st.keys():
    print(key)

print st.get("one"))
print st.contains_key("two")

print st.size()
print st.is_empty()

st.delete("one")

for key in st.keys_with_prefix('t'):
    print(key)

Symbol Table using Ternary Search Tries

.. code-block:: python

from pyalgs.data_structures.strings.search_tries import TernarySearchTries
st = TernarySearchTries()

st.put("one", 1)
st.put("two", 2)
st.put("three", 3)
st.put("six", 6)
st.put("ten", 10)

for key in st.keys():
    print(key)

print st.get("one"))
print st.contains_key("two")

print st.size()
print st.is_empty()

st.delete("one")

for key in st.keys_with_prefix('t'):
    print(key)

Algorithms

Union Find

.. code-block:: python

from pyalgs.algorithms.commons.union_find import UnionFind

uf = UnionFind.create(10)

uf.union(1, 3)
uf.union(2, 4)
uf.union(1, 5)

print(uf.connected(1, 3))
print(uf.connected(3, 5))
print(uf.connected(1, 2))
print(uf.connected(1, 4))

Sorting

The sorting algorithms sort an array in ascending order

Selection Sort

.. code-block:: python

from pyalgs.algorithms.commons.sorting import SelectionSort

a = [4, 2, 1]
SelectionSort.sort(a)
print(a)

Insertion Sort

.. code-block:: python

from pyalgs.algorithms.commons.sorting import InsertionSort

a = [4, 2, 1]
InsertionSort.sort(a)
print(a)

Shell Sort

.. code-block:: python

from pyalgs.algorithms.commons.sorting import ShellSort

a = [4, 2, 1, 23, 4, 5, 6, 7, 8, 9, 20, 11, 13, 34, 66]
ShellSort.sort(a)
print(a)

Merge Sort

.. code-block:: python

from pyalgs.algorithms.commons.sorting import MergeSort

a = [4, 2, 1, 23, 4, 5, 6, 7, 8, 9, 20, 11, 13, 34, 66]
MergeSort.sort(a)
print(a)

Quick Sort

.. code-block:: python

from pyalgs.algorithms.commons.sorting import QuickSort

a = [4, 2, 1, 23, 4, 5, 6, 7, 8, 9, 20, 11, 13, 34, 66]
QuickSort.sort(a)
print(a)

3-Ways Quick Sort

.. code-block:: python

from pyalgs.algorithms.commons.sorting import ThreeWayQuickSort

a = [4, 2, 1, 23, 4, 5, 6, 7, 8, 9, 20, 11, 13, 34, 66]
ThreeWayQuickSort.sort(a)
print(a)

Heap Sort

.. code-block:: python

from pyalgs.algorithms.commons.sorting import HeapSort

a = [4, 2, 1, 23, 4, 5, 6, 7, 8, 9, 20, 11, 13, 34, 66]
HeapSort.sort(a)
print(a)

Selection

Binary Selection

.. code-block:: python

from pyalgs.algorithms.commons.selecting import BinarySelection
from pyalgs.algorithms.commons.util import is_sorted


a = [1, 2, 13, 22, 123]
assert is_sorted(a)
print BinarySelection.index_of(a, 13)

Shuffle

Knuth Shuffle

.. code-block:: python

from pyalgs.algorithms.commons.shuffling import KnuthShuffle

a = [1, 2, 13, 22, 123]
KnuthShuffle.shuffle(a)
print(a)

Graph

Depth First Search

.. code-block:: python

from pyalgs.algorithms.graphs.search import DepthFirstSearch
g = create_graph()
s = 0
dfs = DepthFirstSearch(g, s)

for v in range(1, g.vertex_count()):
    if dfs.hasPathTo(v):
        print(str(s) + ' is connected to ' + str(v))
        print('path is ' + ' => '.join([str(i) for i in dfs.pathTo(v)]))

Breadth First Search

.. code-block:: python

from pyalgs.algorithms.graphs.search import BreadthFirstSearch
g = create_graph()
s = 0
dfs = BreadthFirstSearch(g, s)

for v in range(1, g.vertex_count()):
    if dfs.hasPathTo(v):
        print(str(s) + ' is connected to ' + str(v))
        print('path is ' + ' => '.join([str(i) for i in dfs.pathTo(v)]))

Connected Components

This is for undirected graph

.. code-block:: python

from pyalgs.algorithms.graphs.connectivity import ConnectedComponents
G = create_graph()

cc = ConnectedComponents(G)
print('connected component count: ' + str(cc.count()))


for v in range(G.vertex_count()):
    print('id[' + str(v) + ']: ' + str(cc.id(v)))
for v in range(G.vertex_count()):
    r = randint(0, G.vertex_count()-1)
    if cc.connected(v, r):
        print(str(v) + ' is connected to ' + str(r))

Strongly Connected Components

This is for directed graph

.. code-block:: python

from pyalgs.algorithms.graphs.connectivity import StronglyConnectedComponents
G = create_graph()

cc = StronglyConnectedComponents(G)
print('strongly connected component count: ' + str(cc.count()))


for v in range(G.vertex_count()):
    print('id[' + str(v) + ']: ' + str(cc.id(v)))
for v in range(G.vertex_count()):
    r = randint(0, G.vertex_count()-1)
    if cc.connected(v, r):
        print(str(v) + ' is connected to ' + str(r))

Topological Sort

.. code-block:: python

from pyalgs.algorithms.graphs.topological_sort import DepthFirstOrder
G = create_graph()
topological_sort = DepthFirstOrder(G)
print(' => '.join([str(i) for i in topological_sort.postOrder()]))

Minimum Spanning Tree (Kruskal)

.. code-block:: python

from pyalgs.algorithms.graphs.minimum_spanning_trees import KruskalMST
g = create_edge_weighted_graph()
mst = KruskalMST(g)

tree = mst.spanning_tree()

for e in tree:
    print(e)

Minimum Spanning Tree (Prim Lazy)

.. code-block:: python

from pyalgs.algorithms.graphs.minimum_spanning_trees import LazyPrimMST
g = create_edge_weighted_graph()
mst = LazyPrimMST(g)

tree = mst.spanning_tree()

for e in tree:
    print(e)

Minimum Spanning Tree (Prim Eager)

.. code-block:: python

from pyalgs.algorithms.graphs.minimum_spanning_trees import EagerPrimMST
g = create_edge_weighted_graph()
mst = EagerPrimMST(g)

tree = mst.spanning_tree()

for e in tree:
    print(e)

Directed Cycle Detection:

.. code-block:: python

from pyalgs.algorithms.graphs.directed_cycle import DirectedCycle
dag = create_dag()
    dc = DirectedCycle(dag)
    assertFalse(dc.hasCycle())

Shortest Path (Dijkstra)

.. code-block:: python

from pyalgs.algorithms.graphs.shortest_path import DijkstraShortestPath
g = create_edge_weighted_digraph()
s = 0
dijkstra = DijkstraShortestPath(g, s)
for v in range(1, g.vertex_count()):
    if dijkstra.hasPathTo(v):
        print(str(s) + ' is connected to ' + str(v))
        print('shortest path is ' + ' .. '.join([str(i) for i in dijkstra.shortestPathTo(v)]))
        print('path length is ' + str(dijkstra.path_length_to(v)))

Shortest Path (Topological Sort)

.. code-block:: python

from pyalgs.algorithms.graphs.shortest_path import TopologicalSortShortestPath
from pyalgs.algorithms.graphs.directed_cycle import DirectedCycle
g = create_edge_weighted_digraph()
assert not DirectedCycle(g).hasCycle()
s = 0
dijkstra = TopologicalSortShortestPath(g, s)
for v in range(1, g.vertex_count()):
    if dijkstra.hasPathTo(v):
        print(str(s) + ' is connected to ' + str(v))
        print('shortest path is ' + ' .. '.join([str(i) for i in dijkstra.shortestPathTo(v)]))
        print('path length is ' + str(dijkstra.path_length_to(v)))

Shortest Path (Bellman-Ford for positive and negative edge graph)

.. code-block:: python

from pyalgs.algorithms.graphs.shortest_path import BellmanFordShortestPath
from pyalgs.algorithms.graphs.directed_cycle import DirectedCycle
g = create_edge_weighted_digraph()
s = 0
dijkstra = BellmanFordShortestPath(g, s)
for v in range(1, g.vertex_count()):
    if dijkstra.hasPathTo(v):
        print(str(s) + ' is connected to ' + str(v))
        print('shortest path is ' + ' .. '.join([str(i) for i in dijkstra.shortestPathTo(v)]))
        print('path length is ' + str(dijkstra.path_length_to(v)))

MaxFlow MinCut (Ford-Fulkerson)

.. code-block:: python

from pyalgs.algorithms.graphs.max_flow import FordFulkersonMaxFlow
network = create_flow_network()
ff = FordFulkersonMaxFlow(network, 0, 7)
print('max-flow: '+str(ff.max_flow_value()))

Strings

Longest Repeated Substring

.. code-block:: python

from pyalgs.algorithms.strings.longest_repeated_substring import LongestRepeatedSubstringSearch start, len = LongestRepeatedSubstringSearch.lrs('Hello World', 'World Record') print('Hello World'[start:(start+len+1)])

Sort (LSD)

.. code-block:: python

from pyalgs.algorithms.strings.sorting import LSD
LSD.sort(['good', 'cool', 'done', 'come'])

Sort (MSD)

.. code-block:: python

from pyalgs.algorithms.strings.sorting import MSD
words = 'more details are provided in the docs for implementation, complexities and further info'.split(' ')
print(words)
MSD.sort(words)
print(words)

Sort (3-Ways String Quick Sort)

.. code-block:: python

from pyalgs.algorithms.strings.sorting import String3WayQuickSort
words = 'more details are provided in the docs for implementation, complexities and further info'.split(' ')
print(words)
String3WayQuickSort.sort(words)
print(words)

Substring Search (Brute force)

.. code-block:: python

from pyalgs.algorithms.strings.substring_search import BruteForceSubstringSearch
ss = BruteForceSubstringSearch('find')
print(ss.search_in('I can find it here'))
print(ss.search_in('It is not here'))

Substring Search (Rabin Karp)

.. code-block:: python

from pyalgs.algorithms.strings.substring_search import RabinKarp
ss = RabinKarp('find')
print(ss.search_in('I can find it here'))
print(ss.search_in('It is not here'))

Substring Search (Boyer Moore)

.. code-block:: python

from pyalgs.algorithms.strings.substring_search import BoyerMoore
ss = BoyerMoore('find')
print(ss.search_in('I can find it here'))
print(ss.search_in('It is not here'))

Substring Search (Knuth Morris Pratt)

.. code-block:: python

from pyalgs.algorithms.strings.substring_search import KnuthMorrisPratt
ss = KnuthMorrisPratt('find')
print(ss.search_in('I can find it here'))
print(ss.search_in('It is not here'))

.. _docs: http://pyalgs.readthedocs.org/en/latest/ .. _documentation: http://pyalgs.readthedocs.org/en/latest/