Skip to content

Commit d4ae328

Browse files
committed
Added union-find; changed dir structure
1 parent 738ac02 commit d4ae328

File tree

18 files changed

+220
-10021
lines changed

18 files changed

+220
-10021
lines changed

README.md

Lines changed: 11 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,7 @@ Algos in Python
44
Implementation for the algorithms and datastructures taught in [CS161](http://openclassroom.stanford.edu/MainFolder/CoursePage.php?course=IntroToAlgorithms), in Python
55
Includes test code - doctests for few and full unittests for others
66

7-
Completed Algos and Data Structures
7+
Completed
88
---
99
- Karatsuba Multiplication
1010
- Basic Sorting
@@ -19,8 +19,18 @@ Completed Algos and Data Structures
1919
- Connected Components
2020
- Dijkstra's Shortest Path - O(mlogn)
2121
- Prim's Minimum Cost Spanning Tree - O(mlogn)
22+
- Kruskal's Minimum Spanning Tree - O(mlogn)
2223
- Heap datastructure
2324
- Max heaps
2425
- Min heaps (priority queue)
2526
- Heapsort
2627
- Job Scheduling
28+
- [UnionFind](http://en.wikipedia.org/wiki/Disjoint-set_data_structure) Data Structure
29+
30+
Tests
31+
---
32+
python -m tests.graph_test
33+
python -m tests.digraph_test
34+
python -m tests.graph_algorithms_test
35+
python -m tests.heap_test
36+
python -m tests.unionfind_test

graphs/__init__.py

Whitespace-only changes.

graphs/graph.py

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -159,10 +159,13 @@ def get_edge_weight(self, edge):
159159
def get_edge_weights(self):
160160
""" Returns a list of all edges with their weights """
161161
edge_list = []
162+
unique_edges = []
162163
for node in self.nodes():
163164
for each in self.neighbors(node):
164165
edge = (node, each)
165-
edge_list.append((self.get_edge_weight(edge), edge))
166+
if (each, node) not in unique_edges:
167+
edge_list.append((self.get_edge_weight(edge), edge))
168+
unique_edges.append(edge)
166169
return edge_list
167170

168171
def add_node_attribute(self, node, attr):

greedy/scheduling.py

Lines changed: 0 additions & 10 deletions
This file was deleted.

0 commit comments

Comments
 (0)