Help the Python Software Foundation raise \$60,000 USD by December 31st!

Python implementation of Robert Sedgwick's Algorithm (Part I and Part II) Coursera course

## 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)

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

## Install pyalgs

Run the following command to install pyalgs using pip

```\$ pip install pyalgs
```

## Features:

• Data Structure
• Stack
• Array
• Queue
• 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
• 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
• Connectivity
• Connected Components
• Strongly Connected Components
• Topological Sorting
• Depth First Reverse Post Order
• Minimum Spanning Tree
• Kruskal
• Prim (Lazy)
• Prim (Eager)
• Shortest Path
• Dijkstra

## Usage:

### Data Structure

Stack

```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

```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

```from pyalgs.data_structures.commons.bag import Bag

bag = Bag.create()

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

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

Minimum Priority Queue

```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

```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

```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

```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

```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

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

print set.contains("two")

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

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

set.delete("one")
```

Undirected Graph

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

print(G.vertex_count())
return G
```

Directed Graph

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

print(G.vertex_count())
return G
```

Edge Weighted Graph

```from pyalgs.data_structures.graphs.graph import EdgeWeightGraph
def create_edge_weighted_graph():
g = EdgeWeightedGraph(8)

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

Directed Edge Weighted Graph

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

return g
```

### Algorithms

Union Find

```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

```from pyalgs.algorithms.commons.sorting import SelectionSort

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

Insertion Sort

```from pyalgs.algorithms.commons.sorting import InsertionSort

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

Shell Sort

```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

```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

```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

```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

```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

```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

```from pyalgs.algorithms.commons.shuffling import KnuthShuffle

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

### Graph

Depth First Search

```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)]))
```

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

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

```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

```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

```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)

```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)

```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)
```

Shortest Path (Dijkstra)

```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)))
```