diff --git a/Examples/BellmanFordShortestPath/bellmanFord.js b/Examples/BellmanFordShortestPath/bellmanFord.js index dd4878df..4b2e7254 100644 --- a/Examples/BellmanFordShortestPath/bellmanFord.js +++ b/Examples/BellmanFordShortestPath/bellmanFord.js @@ -1,80 +1,86 @@ /* * Bellman-Ford Single Source Shortest Path Algorithm * * Written by ctonetti * * (Can detect negative cycles in graph) * + * Time Complexity: O(|E||V|) + * + * This algorithm finds the shortest path between + * a source node to all other nodes in a graph by + * relaxing each edge |V| times. + * */ var INF = 1000000 var dist = {} function reset(G) { G.nodes().forEach(unmark) G.edges().forEach(unmark) } function printDistances(G, start) { G.nodes().forEach(function(node) { if (node.id != start.id) { if (dist[node.id] != INF) { Console.log("Distance: " + start.id + " -> " + node.id + ": " + dist[node.id]) } else { Console.log("Distance: " + start.id + " -> " + node.id + ": INF") } } }) } // It is possible to create a custom function to generate weights function createEdgeWeight(G) { G.edges().forEach(function(edges) { edges.weight = 1 }) } function mark(node) { node.color = '#c00' } function unmark(node) { node.color = '#fff' } function bellmanFord(G, start) { // Initialize node values with infinity G.nodes().forEach(function(node) { dist[node.id] = INF }) dist[start.id] = 0 mark(start) for (var i = 0; i < G.nodes().length; i++) { G.edges().forEach(function(edge) { if (dist[edge.from().id] + edge.weight < dist[edge.to().id]) { dist[edge.to().id] = dist[edge.from().id] + edge.weight } }) } // Check for negative cycles var negative_cycle = false G.edges().forEach(function(edge) { if (dist[edge.from().id] + edge.weight < dist[edge.to().id]) { Console.log("Graph contains negative cycle!") negative_cycle = true } }) // print the results in the output window if (!negative_cycle) { printDistances(G, start) } } reset(Document) createEdgeWeight(Document) bellmanFord(Document, Document.nodes()[0]) diff --git a/Examples/BreadthFirstSearch/bfs.js b/Examples/BreadthFirstSearch/bfs.js index 80129bfc..26fd0ebd 100644 --- a/Examples/BreadthFirstSearch/bfs.js +++ b/Examples/BreadthFirstSearch/bfs.js @@ -1,48 +1,55 @@ /* * Breadth-First Search * * Written by ctonetti * + * Time Complexity: O(|E| + |V|) + * + * This algorithm is used to traverse an graph in an + * tree-like structure by exploring the nodes in + * "layers", prioritizing the exploration of the + * nearest neighbor of a node. + * */ function reset(G) { G.nodes().forEach(unmark) G.edges().forEach(unmark) G.nodes().forEach(function(node) { node.seen = false }) } function mark(node) { node.color = '#c00' } function unmark(node) { node.color = '#fff' } function bfs(G, start) { var queue = [start] start.seen = true while (queue.length > 0) { var top = queue.shift(); top.seen = true mark(top) top.neighbors() .filter(function(x) { return !(x.seen) }) .forEach(function(x) { queue.push(x) }) } } reset(Document) bfs(Document, Document.nodes()[0]) diff --git a/Examples/DepthFirstsSearch/dfs.js b/Examples/DepthFirstsSearch/dfs.js index ee52c1bb..281f722d 100644 --- a/Examples/DepthFirstsSearch/dfs.js +++ b/Examples/DepthFirstsSearch/dfs.js @@ -1,51 +1,63 @@ /* * Depth-First Search * * Written by ctonetti * + * Time Complexity: O(|E| + |V|) + * + * This algorithm is used to traverse an graph in an + * tree-like structure by exploring the first branches + * it encounter in each node before backtracking when + * this is not possible anymore. This process continues + * until there is no more graph to be explored. + * + * This is an useful algorithm, as it can be used to + * detect loops, separate connected components, detect + * bridges and articulation vertexes, etc. + * */ function reset(G) { G.nodes().forEach(unmark) G.edges().forEach(unmark) G.nodes().forEach(function(node) { node.seen = false }) } function mark(node) { node.color = '#c00' } function unmark(node) { node.color = '#fff' } function dfs(G, start) { var stk = [start] start.seen = true while (stk.length > 0) { // Get next node var top = stk.pop() top.seen = true // Mark the node mark(top) // Process top.neighbors() .filter(function(x) { // Only get the unseen neighbors return !(x.seen) }) .forEach(function(x) { // Push the unseen nodes stk.push(x) }) } } reset(Document) dfs(Document, Document.nodes()[0]) diff --git a/Examples/DijkstraShortestPath/dijkstra.js b/Examples/DijkstraShortestPath/dijkstra.js index dc7a2649..8b52392f 100644 --- a/Examples/DijkstraShortestPath/dijkstra.js +++ b/Examples/DijkstraShortestPath/dijkstra.js @@ -1,146 +1,164 @@ /* * Dijkstra Single Source Shortest Path Algorithm * * Written by ctonetti * - * (Don't accept negative edges in the graph) + * (Won't accept negative edges in the graph) + * + * Time Complexity: + * (Depends on the data structure used) + * - Our Priority Queue: O(V^2) + * - Binary Heap: O(|E|log|V|) + * - Fibonacci Heap: O(|E|+|V|log|V|) + * + * This algorithm finds the shortest path between + * a source node to all other nodes in a graph. + * It iteratively updates the distances to the nodes + * and always take the least cost node to build + * paths. * */ var INF = 1000000 var dist = {} function reset(G) { G.nodes().forEach(unmark) G.edges().forEach(unmark) } function getIndex(node, array) { for (var i = 0; i < array.length; i++) { if (array[i].element.id == node.id) { return i } } return -1 } function printDistances(G, start) { G.nodes().forEach(function(node) { if (node.id != start.id) { if (dist[node.id] != INF) { Console.log("Distance: " + start.id + " -> " + node.id + ": " + dist[node.id]) } else { Console.log("Distance: " + start.id + " -> " + node.id + ": INF") } } }) } // It is possible to create a custom function to generate weights function createEdgeWeight(G) { G.edges().forEach(function(edges) { edges.weight = 1 }) } function mark(node) { node.color = '#c00' } function unmark(node) { node.color = '#fff' } function Element(e, p) { this.element = e this.priority = p } +// Unoptimized data structure function PriorityQueue() { this.items = [] + // Time Complexity: O(N) this.enqueue = function(node, weight) { var e = new Element(node, weight); var contain = false; for (var i = 0; i < this.items.length; i++) { if (this.items[i].priority > e.priority) { this.items.splice(i, 0, e); contain = true; break; } } if (!contain) { this.items.push(e); } } + // Time Complexity: O(1) this.dequeue = function() { if (this.isEmpty()) return "Underflow"; return this.items.shift(); } + // Time Complexity: O(N) this.update = function(node, weight) { var idx = getIndex(node, this.items) // In this case, we only update the PQ if the new priority // is lower if (idx != -1 && weight < this.items[idx].priority) { this.items.splice(idx, 1) this.enqueue(node, weight) return true } return false } + // Time Complexity: O(1) this.isEmpty = function() { return this.items.length == 0; } + // Time Complexity: O(N) this.print = function() { this.items.forEach(function(item) { Console.log(item.element.from().id + " - " + item.element.to().id) Console.log(item.priority) Console.log("----") }) } } function dijkstra(G, start) { var pq = new PriorityQueue() // Initialize node values with infinity G.nodes().forEach(function(node) { pq.enqueue(node, INF) }) pq.update(start, 0) mark(start) // Initial is marked while (!pq.isEmpty()) { var e = pq.dequeue() // Update distances dist[e.element.id] = e.priority // Relax each neighbor e.element.outEdges().forEach(function(edge) { pq.update(edge.to(), edge.weight + e.priority) }) } // print the results in the output window printDistances(G, start) } reset(Document) createEdgeWeight(Document) dijkstra(Document, Document.nodes()[0]) diff --git a/Examples/FloydWarshallMultipleSourcesShortestPath/floydWarshall.js b/Examples/FloydWarshallMultipleSourcesShortestPath/floydWarshall.js index 649b4281..112fbac9 100644 --- a/Examples/FloydWarshallMultipleSourcesShortestPath/floydWarshall.js +++ b/Examples/FloydWarshallMultipleSourcesShortestPath/floydWarshall.js @@ -1,98 +1,104 @@ /* * Floyd-Warshall Multiple Sources Shortest Paths Algorithm * * Written by ctonetti * + * Time Complexity: O(V^3) + * + * This algorithm finds the shortest paths between + * every pair of nodes in a graph by iteratively + * "allowing" a number of nodes to be used in each + * path, constructing a matrix of distances. * */ var INF = 1000000 var dist = {} function reset(G) { G.nodes().forEach(unmark) G.edges().forEach(unmark) var V = G.nodes().length var N = G.nodes() // Create raw weight matrix for (var i = 0; i < V; i++) { dist[N[i].id] = {} for (var j = 0; j < V; j++) { if (N[i].id == N[j].id) { dist[N[i].id][N[j].id] = 0 } else { dist[N[i].id][N[j].id] = INF } } } createEdgeWeight(Document) G.edges().forEach(function(edge) { dist[edge.from().id][edge.to().id] = edge.weight dist[edge.to().id][edge.from().id] = edge.weight }) } function printDistances(G) { var V = G.nodes().length var N = G.nodes() Console.log("Distance Matrix:") line = "id " for (var i = 0; i < V; i++) { line += N[i].id + " " } Console.log(line) for (var i = 0; i < V; i++) { var line = N[i].id + " " for (var j = 0; j < V; j++) { if (dist[N[i].id][N[j].id] == INF) { line += "INF " } else { line += dist[N[i].id][N[j].id] + " " } } Console.log(line) } } // It is possible to create a custom function to generate weights function createEdgeWeight(G) { G.edges().forEach(function(edges) { edges.weight = 1 }) } function mark(node) { node.color = '#c00' } function unmark(node) { node.color = '#fff' } function floydWarshall(G) { var V = G.nodes().length var N = G.nodes() for (var k = 0; k < V; k++) { for (var i = 0; i < V; i++) { for (var j = 0; j < V; j++) { if (dist[N[i].id][N[j].id] > dist[N[i].id][N[k].id] + dist[N[k].id][N[j].id]) { dist[N[i].id][N[j].id] = dist[N[i].id][N[k].id] + dist[N[k].id][N[j].id] } } } } printDistances(G) } reset(Document) floydWarshall(Document) diff --git a/Examples/KruskalSpanningTree/kruskal.js b/Examples/KruskalSpanningTree/kruskal.js index 4a6158aa..fcfc1e16 100644 --- a/Examples/KruskalSpanningTree/kruskal.js +++ b/Examples/KruskalSpanningTree/kruskal.js @@ -1,186 +1,208 @@ /* * Kruskal`s Minimum Spanning Tree * * Written by ctonetti * * (Remember, this algorithm only works correctly in connected graphs.) * + * Time Complexity: O(V^2) + * (Depends on the data structure used and the type of + * sorting algorithm. Optimally is O(E*ack(V), where + * ack() is the ackermann function, if there is guarantee + * that the edges can be sorted in linear time (counting + * sort or radix sort)) + * + * This algorithm finds a minimum spanning tree of + * a graph. A spanning tree of a graph is a tree + * that connects all the nodes of an original graph + * by selecting edges. + * + * A spanning tree is minimal when the sum of the + * weights of it's edges is the least among all the + * possible spanning tree's of a graph. + * */ function reset(G, weight) { G.nodes().forEach(unmark) G.edges().forEach(unmark) } function mark(node) { node.color = '#c00' } function unmark(node) { node.color = '#fff' } function getIndex(node, array) { for (var i = 0; i < array.length; i++) { if (array[i].element.id == node.id) { return i } } return -1 } // It is possible to create a custom function to generate weights function createEdgeWeight(G) { G.edges().forEach(function(edges) { edges.weight = 1 }) } function Element(e, p) { this.element = e this.priority = p } - + +// Unoptimized data structure function PriorityQueue() { this.items = [] + // Time Complexity: O(N) this.enqueue = function(node, weight) { var e = new Element(node, weight); var contain = false; for (var i = 0; i < this.items.length; i++) { if (this.items[i].priority > e.priority) { this.items.splice(i, 0, e); contain = true; break; } } if (!contain) { this.items.push(e); } } + // Time Complexity: O(1) this.dequeue = function() { if (this.isEmpty()) return "Underflow"; return this.items.shift(); } + // Time Complexity: O(N) this.update = function(node, weight) { var idx = getIndex(node, this.items) // In this case, we only update the PQ if the new priority // is lower if (idx != -1 && weight < this.items[idx].priority) { this.items.splice(idx, 1) this.enqueue(node, weight) return true } return false } + // Time Complexity: O(1) this.isEmpty = function() { return this.items.length == 0; } + // Time Complexity: O(N) this.print = function() { this.items.forEach(function(item) { Console.log(item.element.from().id + " - " + item.element.to().id) Console.log(item.priority) Console.log("----") }) } } function UnionFind() { this.parents = {} this.count = 0 this.init = function(items) { // Construct forest of disjoint elements // Each element is a node in the original // graph for (var i=0; i < items.length; i++) { this.parents[items[i].id] = items[i] } this.count = items.length } // Unite two disjoint sets this.union = function(a, b) { var root_a = this.find(a) var root_b = this.find(b) // Check if the two are already in the same tree if (root_a.id == root_b.id) { return } if (root_a.id < root_b.id) { if (this.parents[b.id] != b) { this.union(this.parents[b.id], a) } this.parents[b.id] = this.parents[a.id] } else { if (this.parents[a.id] != a) { this.union(this.parents[a.id], b) } this.parents[a.id] = this.parents[b.id] } } this.find = function(a) { while (this.parents[a.id] != a) { a = this.parents[a.id] } return a } this.connected = function(a, b) { return this.find(a).id == this.find(b).id } } function kruskal(G) { var pq = new PriorityQueue() var uf = new UnionFind() var tree = [] uf.init(G.nodes()) G.edges().forEach(function(e) { pq.enqueue(e, e.weight) }) while (!pq.isEmpty()) { var edge = pq.dequeue().element if (uf.connected(edge.from(), edge.to())) { continue } Console.log("Edge: " + edge.from().id + " - " + edge.to().id + " Added!") uf.union(edge.from(), edge.to()) tree.push(edge) } return tree } reset(Document) createEdgeWeight(Document) Console.log(kruskal(Document).length) diff --git a/Examples/PrimSpanningTree/prim.js b/Examples/PrimSpanningTree/prim.js index 7253753b..e115b468 100644 --- a/Examples/PrimSpanningTree/prim.js +++ b/Examples/PrimSpanningTree/prim.js @@ -1,138 +1,159 @@ /* * Prim's Minimum Spanning Tree * * Written by ctonetti * * (Remember, this algorithm only works correctly in connected graphs.) * + * Time Complexity: + * (Depends on the data structure used) + * - Our Priority Queue: O(V^2) + * - Binary Heap: O(|E|log|V|) + * - Fibonacci Heap: O(|E|+|V|log|V|) + * + * This algorithm finds a minimum spanning tree of + * a graph. A spanning tree of a graph is a tree + * that connects all the nodes of an original graph + * by selecting edges. + * + * A spanning tree is minimal when the sum of the + * weights of it's edges is the least among all the + * possible spanning tree's of a graph. + * */ function reset(G, weight) { G.nodes().forEach(unmark) G.edges().forEach(unmark) } function mark(node) { node.color = '#c00' } function unmark(node) { node.color = '#fff' } function getIndex(node, array) { for (var i = 0; i < array.length; i++) { if (array[i].element.id == node.id) { return i } } return -1 } // It is possible to create a custom function to generate weights function createEdgeWeight(G) { G.edges().forEach(function(edges) { edges.weight = 1 }) } function Element(e, p) { this.element = e this.priority = p } +// Unoptimized data structure function PriorityQueue() { this.items = [] - + + // Time Complexity: O(N) this.enqueue = function(node, weight) { var e = new Element(node, weight); var contain = false; for (var i = 0; i < this.items.length; i++) { if (this.items[i].priority > e.priority) { this.items.splice(i, 0, e); contain = true; break; } } if (!contain) { this.items.push(e); } } + // Time Complexity: O(1) this.dequeue = function() { if (this.isEmpty()) return "Underflow"; return this.items.shift(); } + // Time Complexity: O(N) this.update = function(node, weight) { var idx = getIndex(node, this.items) // In this case, we only update the PQ if the new priority // is lower if (idx != -1 && weight < this.items[idx].priority) { this.items.splice(idx, 1) this.enqueue(node, weight) return true } return false } + // Time Complexity: O(1) this.isEmpty = function() { return this.items.length == 0; } + // Time Complexity: O(N) this.print = function() { this.items.forEach(function(item) { Console.log(item.element.id) Console.log(item.priority) Console.log("----") }) } } function prim(G, start) { var tree = [] var pq = new PriorityQueue() var total_weight = 0 // Initialize Weights G.nodes().forEach(function(node) { if (node.id == start.id) { pq.enqueue(node, 0) // The starting node begin with priority 0 } else { pq.enqueue(node, 1000000) // All other nodes begin with priority "Infinity" } }) while (!pq.isEmpty()) { // Get next element from the priority key var val = pq.dequeue() var next = val.element tree.push(next) total_weight += val.priority // Mark the visisted node mark(next) next.edges().forEach(function(edge) { pq.update(edge.to(), edge.weight) pq.update(edge.from(), edge.weight) }) } Console.log("Weight of the MST: " + total_weight) } reset(Document) createEdgeWeight(Document) prim(Document, Document.nodes()[0]) diff --git a/Examples/TopologicalSort/topologicalSort.js b/Examples/TopologicalSort/topologicalSort.js index 1235628b..9a5cc7f9 100644 --- a/Examples/TopologicalSort/topologicalSort.js +++ b/Examples/TopologicalSort/topologicalSort.js @@ -1,54 +1,61 @@ /* * Topological Sort * * Written by ctonetti * * (A topological order is only valid for Directed Acyclical Graphs) * + * Time Complexity: O(|E| + |V|) + * + * This algorithm finds a topological order of a given graph. + * A topological order is an order in which each node appear + * before any of the nodes that can be reached by it's out + * edges. + * */ var order = [] function reset(G) { G.nodes().forEach(unmark) G.edges().forEach(unmark) G.nodes().forEach(function(node) { node.seen = false }) } function mark(node) { node.color = '#c00' } function unmark(node) { node.color = '#fff' } function printOrder() { order.reverse() Console.log("Topological Order:") order.forEach(function(node) { Console.log(node.id) }) } // Recursive version of the DFS, modified function topologicalSort(G, node) { node.seen = true mark(node) node.successors().forEach(function(succ) { if (!succ.seen) { topologicalSort(G, succ) } }) order.push(node) } reset(Document) topologicalSort(Document, Document.nodes()[0]) printOrder()