Skip to content

Commit 306f229

Browse files
64json64json
committed
Merge branch 'gh-pages' of https://github.com/parkjs814/AlgorithmVisualizer into gh-pages
2 parents 290183f + 3b2c34d commit 306f229

File tree

17 files changed

+291
-3
lines changed

17 files changed

+291
-3
lines changed

‎algorithm/category.json

Lines changed: 14 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,14 @@
66
"bfs": "BFS",
77
"dijkstra": "Dijkstra",
88
"bellman_ford": "Bellman-Ford",
9-
"floyd_warshall": "Floyd-Warshall"
9+
"floyd_warshall": "Floyd-Warshall",
10+
"topological_sort": "Topological-Sort"
11+
}
12+
},
13+
"mst": {
14+
"name": "Minimum Spanning Tree",
15+
"list": {
16+
"prim": "Prim's Algorithm"
1017
}
1118
},
1219
"search": {
@@ -26,6 +33,12 @@
2633
"heap" : "Heap Sort"
2734
}
2835
},
36+
"string": {
37+
"name": "String",
38+
"list": {
39+
"edit_distance": "Edit Distance"
40+
}
41+
},
2942
"etc": {
3043
"name": "Uncategorized",
3144
"list": {

‎algorithm/etc/dp/desc.json

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -10,6 +10,7 @@
1010
"files": {
1111
"fibonacci": "Fibonacci Sequence",
1212
"sliding_window": "Finding the largest sum of three contiguous number",
13-
"max_sum_path": "Finding the maximum sum in a path from (0, 0) to (N-1, M-1) when can only move to right or down"
13+
"max_sum_path": "Finding the maximum sum in a path from (0, 0) to (N-1, M-1) when can only move to right or down",
14+
"longest_increasing_subsequence": "Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order"
1415
}
1516
}

‎algorithm/etc/dp/longest_increasing_subsequence/code.js

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
tracer._pace(500);
2+
3+
// Initialize LIS values for all indexes
4+
for( var i = 0; i < 20; i++) {
5+
LIS[i] = 1;
6+
}
7+
8+
tracer._print( 'Calculating Longest Increasing Subsequence values in bottom up manner ');
9+
// Compute optimized LIS values in bottom up manner
10+
for( var i = 1; i < 10; i++) {
11+
tracer._select(i) ;
12+
tracer._print( ' LIS['+i+'] = ' + LIS[i]);
13+
for( var j =0; j < i; j++) {
14+
tracer._notify(j);
15+
if( A[i] > A[j] && LIS[i] < LIS[j] + 1) {
16+
LIS[i] = LIS[j] + 1;
17+
tracer._print( ' LIS['+i+'] = ' + LIS[i]);
18+
}
19+
}
20+
tracer._deselect(i);
21+
}
22+
23+
// Pick maximum of all LIS values
24+
tracer._print( 'Now calculate maximum of all LIS values ');
25+
var max = LIS[0];
26+
for( var i = 1; i < 10; i++) {
27+
if(max < LIS[i]) {
28+
max = LIS[i];
29+
}
30+
}
31+
tracer._print('Longest Increasing Subsequence = max of all LIS = ' + max);

‎algorithm/etc/dp/longest_increasing_subsequence/data.js

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
var tracer = new Array1DTracer();
2+
var A = Array1D.random(10, 0, 10);
3+
var LIS = new Array(10);
4+
tracer._setData(A);

‎algorithm/graph_search/topological_sort/desc.json

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
{
2+
"Topological-Sort": "Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG. NOTE: when the graph is represented as an Adjacency Matrix, the Calculation of in-degree Array becomes O(|V|<sup>2</sup>)",
3+
"Applications": [
4+
"Job Scheduling",
5+
"Instruction Scheduling",
6+
"Logic Synthesis",
7+
"Determining the order of compilation tasks to perform in makefiles",
8+
"Data serialization"
9+
],
10+
"Complexity": {
11+
"time": "worst O(|V|+|E|)",
12+
"space": "worst O(|V|)"
13+
},
14+
"References": [
15+
"<a href='http://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/'>GeeksForGeeks</a>",
16+
"<a href='http://www.geeksforgeeks.org/topological-sorting/'>GeeksForGeeks</a>"
17+
],
18+
"files": {
19+
"kahn_algorithm": "Performing Topological Sort using Queue Data Structure & an array of In-degrees"
20+
}
21+
}

‎algorithm/graph_search/topological_sort/kahn_algorithm/code.js

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
tracer._pace(100);
2+
tracer._sleep(1000);
3+
4+
(function topologicalSort () {
5+
var inDegrees = Array.apply (null, Array (G.length)).map (Number.prototype.valueOf, 0); //create an Array of G.length number of 0s
6+
var Q = [], iter = 0, i;
7+
8+
tracer._print ('Calculating in-degrees for each Node...');
9+
for (var currNode = 0; currNode < G.length; currNode++) {
10+
for (var currNodeNeighbor = 0; currNodeNeighbor < G.length; currNodeNeighbor++) {
11+
if (G [currNode] [currNodeNeighbor]) {
12+
tracer._print (currNodeNeighbor + ' has an incoming edge from ' + currNode);
13+
tracer._visit (currNodeNeighbor, currNode);
14+
inDegrees [currNodeNeighbor]++;
15+
tracer._leave (currNodeNeighbor, currNode);
16+
}
17+
}
18+
}
19+
tracer._print ('Done. In-Degrees are: [ ' + String (inDegrees) + ' ]');
20+
tracer._print ('');
21+
22+
tracer._print ('Initializing queue with all the sources (nodes with no incoming edges)');
23+
inDegrees.map (function (indegrees, node) {
24+
tracer._visit (node);
25+
if (!indegrees) {
26+
tracer._print (node + ' is a source');
27+
Q.push (node);
28+
}
29+
tracer._leave (node);
30+
});
31+
tracer._print ('Done. Initial State of Queue: [ ' + String (Q) + ' ]');
32+
tracer._print ('');
33+
34+
//begin topological sort (kahn)
35+
while (Q.length > 0) {
36+
tracer._print ('Iteration #' + iter + '. Queue state: [ ' + String (Q) + ' ]');
37+
currNode = Q.shift (1);
38+
tracer._visit (currNode);
39+
40+
for (i = 0; i < G.length; i++) {
41+
if (G [currNode] [i]) {
42+
tracer._print (i + ' has an incoming edge from ' + currNode + '. Decrementing ' + i + '\'s in-degree by 1.');
43+
tracer._visit (i, currNode);
44+
inDegrees [i]--;
45+
tracer._leave (i, currNode);
46+
47+
if (!inDegrees [i]) {
48+
tracer._print (i + '\'s in-degree is now 0. Enqueuing ' + i);
49+
Q.push (i);
50+
}
51+
}
52+
}
53+
tracer._leave (currNode);
54+
tracer._print ('In-degrees are: [' + String (inDegrees) + ' ]');
55+
tracer._print ('-------------------------------------------------------------------');
56+
57+
iter++;
58+
}
59+
}) ();

‎algorithm/graph_search/topological_sort/kahn_algorithm/data.js

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
var tracer = new DirectedGraphTracer ();
2+
// G[i][j] indicates whether the path from the i-th node to the j-th node exists or not. NOTE: The graph must be Directed-Acyclic
3+
var G = [
4+
[0, 0, 0, 0, 0, 0],
5+
[0, 0, 1, 0, 0, 0],
6+
[0, 0, 0, 1, 0, 0],
7+
[0, 0, 0, 0, 0, 0],
8+
[1, 0, 0, 1, 0, 0],
9+
[1, 1, 0, 0, 0, 0]
10+
];
11+
12+
tracer._setData (G);

‎algorithm/mst/prim/desc.json

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
{
2+
"Prim's Algorithm": "Greedy algorithm that finds a minimum spanning tree for a weighted undirected graph.",
3+
"Applications": [
4+
],
5+
"Complexity": {
6+
"time": "worst O(|V|<sup>2</sup>)"
7+
},
8+
"References": [
9+
"<a href='https://en.wikipedia.org/wiki/Prim%27s_algorithm'>Wikipedia</a>"
10+
],
11+
"files": {
12+
"normal": "Finds minimum spanning tree of a given graph."
13+
}
14+
}

‎algorithm/mst/prim/normal/code.js

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
function prim(){
2+
// Finds a tree so that there exists a path between
3+
// every two nodes while keeping the cost minimal
4+
var minD, minI, minJ, sum=0, D=[];
5+
for(var i = 0; i < G.length; i++) D.push(0);
6+
D[0] = 1; // First node is visited
7+
for(var k = 0; k < G.length-1; k++){ // Searching for k edges
8+
minD = Infinity;
9+
for(i = 0; i< G.length; i++)
10+
if(D[i]) // First node in an edge must be visited
11+
for(var j = 0; j < G.length; j++)
12+
if(!D[j] && G[i][j]){
13+
tracer._visit(i, j);
14+
// Second node must not be visited and must be connected to first node
15+
if(G[i][j] < minD){
16+
// Searching for cheapest edge which satisfies requirements
17+
minD = G[i][j];
18+
minI = i;
19+
minJ = j;
20+
}
21+
tracer._leave(i, j);
22+
}
23+
tracer._visit(minI, minJ);
24+
D[minJ] = 1; // Visit second node and insert it into or tree
25+
sum += G[minI][minJ];
26+
}
27+
tracer._print("The sum of all edges is: " + sum);
28+
}
29+
30+
tracer._pace(500);
31+
tracer._print("nodes that belong to minimum spanning tree are: ");
32+
prim();

‎algorithm/mst/prim/normal/data.js

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
var tracer = new WeightedUndirectedGraphTracer();
2+
/*var G = [ // G[i][j] indicates the weight of the path from the i-th node to the j-th node
3+
[0, 3, 0, 1, 0],
4+
[5, 0, 1, 2, 4],
5+
[1, 0, 0, 2, 0],
6+
[0, 2, 0, 0, 1],
7+
[0, 1, 3, 0, 0]
8+
];*/
9+
var G = WeightedUndirectedGraph.random(10, .4, 1, 9);
10+
tracer._setData(G);

‎algorithm/string/edit_distance/desc.json

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
{
2+
"Edit-Distance": "Given two strings str1 (length M) and str2 (length N) and below operations that can performed on str1. Find minimum number of edits (operations) required to convert str1 into str2.<br />Insert<br />Remove<br />Replace<br />All of the above operations are of equal cost",
3+
"Applications": [
4+
"Displaing Near-Proximity Words",
5+
"Information Retrieval (eg- Lucene API)",
6+
"Natural Language Processing"
7+
],
8+
"Complexity": {
9+
"time": "worst O(|M|.|N|)",
10+
"space": "worst O(|M|.|N|)"
11+
},
12+
"References": [
13+
"<a href='https://en.wikipedia.org/wiki/Edit_distance'>Wikipedia</a>"
14+
],
15+
"files": {
16+
"dynamic_programming": "Distance from str1 to str2 using Dynamic Programming (2D Array method)"
17+
}
18+
}

‎algorithm/string/edit_distance/dynamic_programming/code.js

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
tracer._pace (200);
2+
tracer._print ('Initialized DP Table');
3+
tracer._print ('Y-Axis (Top to Bottom): ' + str1);
4+
tracer._print ('X-Axis (Left to Right): ' + str2);
5+
6+
var dist = (function editDistance (str1, str2, table) {
7+
//display grid with words
8+
tracer._print ('*** ' + str2.split ('').join (' '));
9+
table.forEach (function (item, index) {
10+
var character = (index === 0) ? '*' : str1 [index-1];
11+
tracer._print (character + '\t' + item);
12+
});
13+
14+
//begin ED execution
15+
for (var i = 1; i < str1.length+1; i++) {
16+
for (var j = 1; j < str2.length+1; j++) {
17+
if (str1 [i-1] === str2 [j-1]) {
18+
tracer._select (i-1, j-1);
19+
table [i] [j] = table [i-1] [j-1];
20+
tracer._notify (i, j);
21+
tracer._deselect (i-1, j-1);
22+
}
23+
else {
24+
tracer._select (i-1, j);
25+
tracer._select (i, j-1);
26+
tracer._select (i-1, j-1);
27+
table [i] [j] = Math.min (table [i-1] [j], table [i] [j-1], table [i-1] [j-1]) + 1;
28+
tracer._notify (i, j);
29+
tracer._deselect (i-1, j);
30+
tracer._deselect (i, j-1);
31+
tracer._deselect (i-1, j-1);
32+
}
33+
}
34+
}
35+
36+
tracer._select (str1.length, str2.length);
37+
return table [str1.length] [str2.length];
38+
}) (str1, str2, table);
39+
40+
tracer._print ('Minimum Edit Distance: ' + dist);

‎algorithm/string/edit_distance/dynamic_programming/data.js

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
var tracer = new Array2DTracer ();
2+
var str1 = 'stack', str2 = 'racket', table = new Array (str1.length + 1);
3+
4+
table [0] = Array.apply (null, {length: str2.length + 1}).map (Number.call, Number);
5+
for (var i = 1; i < str1.length+1; i++) {
6+
table [i] = Array.apply (null, Array (str2.length+1)).map (Number.prototype.valueOf, -1);
7+
table [i] [0] = i
8+
}
9+
10+
tracer._setData (table);

‎css/stylesheet.css

Lines changed: 19 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -10,6 +10,23 @@ body {
1010
color: rgb(187, 187, 187);
1111
}
1212

13+
*::-webkit-scrollbar {
14+
width: 15px;
15+
}
16+
*::-webkit-scrollbar-track {
17+
background-color: #3C3F41;
18+
}
19+
20+
*::-webkit-scrollbar-thumb {
21+
background-color: rgba(0, 0, 0, 0.2);
22+
}
23+
*::-webkit-scrollbar-button {
24+
background-color: #7c2929;
25+
}
26+
*::-webkit-scrollbar-corner {
27+
background-color: #3C3F41;
28+
}
29+
1330
a {
1431
text-decoration: none;
1532
}
@@ -214,6 +231,7 @@ section {
214231
padding: 0 8px;
215232
line-height: 30px;
216233
font-size: 12px;
234+
overflow-y: auto;
217235
}
218236

219237
.data_container {
@@ -304,4 +322,4 @@ pre {
304322

305323
.mtbl-cell.notifying {
306324
background: #f00;
307-
}
325+
}

‎img/favicon.ico

1.12 KB
Binary file not shown.

‎img/image.png

25.8 KB
Loading

‎index.html

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,11 @@
22
<html lang="en">
33
<head>
44
<meta charset="UTF-8">
5+
<meta name="description" content="Tool for visualizing algorithms." />
6+
<meta property="og:title" content="Algorithm Visualizer" />
7+
<meta property="og:description" content="Tool for visualizing algorithms." />
8+
<meta property="og:image" content="img/image.png" />
9+
<link rel="shortcut icon" href="img/favicon.ico" type="image/x-icon" />
510
<title>Algorithm Visualizer</title>
611
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Roboto">
712
<link rel="stylesheet" href="css/font-awesome.min.css">

0 commit comments

Comments
 (0)