This project demonstrates **Prim's algorithm**, a method of finding the minimum spanning tree of a graph.
-## Story
-Maurice runs an online radio station. His original idea was to stream the audio from a single web server. This was easy to set up and initially worked very well.
-Unfortunately, as his channel grew, so did the bill from his telco. His rickety server didn't fare much better, as not a week went by before it crashed during peak hour. A flash flood of traffic from Reddit was the last straw. Something had to be done.
-The problem was his server sent an individual copy of the podcast to every listener, a strategy that worked with two or three listeners but did not scale to 100. He could have easily upgraded his bandwidth or his computer, but he was already scraping a living and did not want to spend more. So the only viable solution was to share the burden using a peer-to-peer system.
-Here's where the **minimum spanning tree** comes in. Given a graph of all the connections, we can help Maurice figure out a way of distributing the load, so that everyone is connected as efficiently as possible. To calculate this, we use – you guessed it – Prim's algorithm.
-## Algorithm
-Not all connections are created equal – some have a higher latency (delay or lag) than others, which is indicated by a number next to each edge. This algorithm takes this into account and chooses the path with minimal cost.
-1. Add Maurice's server to the tree. This is our starting point.
-2. Find the edge with the minimum cost that connects a node *inside* the tree to a node *outside*, and add it to the tree.
-3. If all nodes are part of the tree, we're done! Otherwise, repeat from step 2.
\ No newline at end of file diff --git a/Examples/PrimSpanningTree/prim.js b/Examples/PrimSpanningTree/prim.js new file mode 100644 index 00000000..7253753b --- /dev/null +++ b/Examples/PrimSpanningTree/prim.js @@ -0,0 +1,138 @@ +/* + * Prim's Minimum Spanning Tree + * + * Written by ctonetti + * + * (Remember, this algorithm only works correctly in connected graphs.) + * + */ + +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 +} + +function PriorityQueue() { + + this.items = [] + + 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); + } + } + + this.dequeue = function() { + if (this.isEmpty()) + return "Underflow"; + return this.items.shift(); + } + + 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 + } + + this.isEmpty = function() { + return this.items.length == 0; + } + + 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/PrimSpanningTree/prims.graph b/Examples/PrimSpanningTree/prims.graph deleted file mode 100644 index f9c8a0ac..00000000 --- a/Examples/PrimSpanningTree/prims.graph +++ /dev/null @@ -1,173 +0,0 @@ -[Document Properties] -top : -207 -bottom : 278.5 -left : -621 -right : 310.5 -DataStructurePlugin : Graph - -[DataType 0] -Name : Client -IconName : rocs_computer -Color : #000000 -Properties : name=,visited=false - -[DataType 1] -Name : Server -IconName : rocs_server2 -Color : #000000 -Properties : name= - -[PointerType 0] -Name : Connection -Color : #808080 -LineStyle : 3 -Direction : bidirectional -Properties : weight=0 - -[PointerType 1] -Name : Used -Color : #808080 -LineStyle : 1 -Direction : bidirectional -Properties : weight=0 - -[DataStructure 0] -X-plugin-type : 0 -name : network - -[Data 1] -type : 0 -x : 14 -y : 78 -width : 0.3 -id : 1 -color : #00aa00 -name : E -visited : true - -[Data 2] -type : 0 -x : -90 -y : 158 -width : 0.3 -id : 2 -color : #00aa00 -name : F -visited : true - -[Data 3] -type : 0 -x : 87 -y : 169 -width : 0.3 -id : 3 -color : #00aa00 -name : G -visited : true - -[Data 4] -type : 0 -x : -222 -y : -50 -width : 0.3 -id : 4 -color : #00aa00 -name : A -visited : true - -[Data 5] -type : 0 -x : -89 -y : -2 -width : 0.3 -id : 5 -color : #00aa00 -name : B -visited : true - -[Data 6] -type : 0 -x : 32 -y : -50 -width : 0.3 -id : 6 -color : #00aa00 -name : C -visited : true - -[Data 7] -type : 1 -x : -192 -y : 76 -width : 0.3 -id : 7 -color : #0000ff -name : D -visited : true - -[Pointer 1->5] -type : 0 -color : #808080 -width : 1 -weight : 0 - -[Pointer 1->2] -type : 0 -color : #808080 -width : 1 -weight : 0 - -[Pointer 7->2] -type : 0 -color : #808080 -width : 1 -weight : 0 - -[Pointer 5->6] -type : 0 -color : #808080 -width : 1 -weight : 0 - -[Pointer 7->4] -type : 0 -color : #808080 -width : 1 -weight : 0 - -[Pointer 7->1] -type : 1 -color : #808080 -width : 2 -weight : 0 - -[Pointer 6->1] -type : 1 -color : #808080 -width : 2 -weight : 0 - -[Pointer 5->7] -type : 1 -color : #808080 -width : 2 -weight : 0 - -[Pointer 4->5] -type : 1 -color : #808080 -width : 2 -weight : 0 - -[Pointer 3->1] -type : 1 -color : #808080 -width : 2 -weight : 0 - -[Pointer 2->3] -type : 1 -color : #808080 -width : 2 -weight : 0 - diff --git a/Examples/PrimSpanningTree/prims.js b/Examples/PrimSpanningTree/prims.js deleted file mode 100644 index 777c6fa6..00000000 --- a/Examples/PrimSpanningTree/prims.js +++ /dev/null @@ -1,102 +0,0 @@ -/** - * Prim's algorithm - * - * __(')< written by lambda fairy - * \___) - */ - -function reset_graph(g) { - function reset(thing) { - thing.set_type(0) - thing.color = '#000' - } - function reset_node(node) { - reset(node) - node.width = 0.3 - } - function reset_edge(edge) { - reset(edge) - edge.width = 1 - } - g.nodes().forEach(reset_node) - g.edges().forEach(reset_edge) -} - -function add_weights(g) { - g.edges().forEach(function(edge) { - edge.weight = randint(1, 10) - }) -} - -function randint(min, max) { - return Math.floor(Math.random() * (max - min + 1)) + min -} - -function reset_visited(nodes) { - nodes.forEach(function(node) { - node.visited = false - }) -} - -function get_unvisited(edge) { - var s = edge.from.visited, e = edge.to.visited - if (s && !e) { - return edge.to - } else if (!s && e) { - return edge.from - } else { - return null - } -} - -function prim(g, start, mark_node, mark_edge) { - // Mark the starting point - reset_visited(g.nodes()) - start.visited = true - var tree = [start] - mark_node(start); interrupt() - // Loop until all nodes are included in the tree - while (tree.length < g.nodes().length) { - // Go through all the edges connected to the tree ... - var best_weight = Infinity, best_target = null, best_edge = null - tree.forEach(function(node) { - // ... and choose the one with the lowest weight - node.adj_edges().forEach(function(edge) { - var outside = get_unvisited(edge) - if (outside != null && edge.weight < best_weight) { - best_weight = edge.weight - best_target = outside - best_edge = edge - } - }) - }) - // Mark the closest node, and add it to the tree - tree.push(best_target) - best_target.visited = true - mark_node(best_target); mark_edge(best_edge); interrupt() - } -} - -reset_graph(network) -add_weights(network) -var server = network.nodes()[0] -server.set_type(1) -prim(network, server, - function(node) { - if (node.type() == 1) { - Console.log('Starting server ' + node.name) - node.color = '#00f' - node.width = 0.6 - } else { - Console.log('Connecting ' + node.name) - node.color = '#0a0' - } - }, - function(edge) { - edge.set_type(1) - edge.color = '#0a0' - edge.width = 2 - Console.log(' -- latency: ' + edge.weight) - }) - -Console.log('== All clients connected ==') diff --git a/Examples/PrimSpanningTree/prims.rocs b/Examples/PrimSpanningTree/prims.rocs deleted file mode 100644 index ee359dde..00000000 --- a/Examples/PrimSpanningTree/prims.rocs +++ /dev/null @@ -1,14 +0,0 @@ -[CodeFile1] -file=./prims.js -identifier=1 - -[GraphFile1] -file=./prims.graph -identifier=1 - -[Journal] -JournalHtml=journal.html - -[Project] -CodeFiles=1 -GraphFiles=1