diff --git a/Examples/BellmanFordShortestPath/bellmanFord.js b/Examples/BellmanFordShortestPath/bellmanFord.js new file mode 100644 index 00000000..4b2e7254 --- /dev/null +++ b/Examples/BellmanFordShortestPath/bellmanFord.js @@ -0,0 +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.graph b/Examples/BreadthFirstSearch/bfs.graph deleted file mode 100644 index adaed83f..00000000 --- a/Examples/BreadthFirstSearch/bfs.graph +++ /dev/null @@ -1,119 +0,0 @@ -[Document Properties] -top : -227.062 -bottom : 256.844 -left : -495 -right : 572.5 -DataStructurePlugin : Graph - -[DataType 0] -Name : Innocent Fish -IconName : rocs_wanda -Color : #000000 -Properties : name= - -[DataType 1] -Name : Mine -IconName : rocs_mines -Color : #000000 -Properties : name= - -[PointerType 0] -Name : Connection -Color : #808080 -LineStyle : 1 -Direction : bidirectional -Properties : - -[DataStructure 0] -X-plugin-type : 0 -name : lake - -[Data 1] -type : 0 -x : 58 -y : 27 -width : 0.3 -id : 1 -color : #00aa00 -name : B - -[Data 2] -type : 0 -x : 59 -y : 134 -width : 0.3 -id : 2 -color : #00aa00 -name : E - -[Data 4] -type : 0 -x : 163 -y : 136 -width : 0.3 -id : 4 -color : #00aa00 -name : F - -[Data 5] -type : 0 -x : -31 -y : -28 -width : 0.3 -id : 5 -color : #00aa00 -name : A - -[Data 6] -type : 0 -x : 162 -y : 29 -width : 0.3 -id : 6 -color : #00aa00 -name : C - -[Data 3] -type : 1 -x : 253 -y : 75 -width : 0.3 -id : 3 -color : #cc0000 -name : D - -[Pointer 5->1] -type : 0 -color : #808080 -width : 1 - -[Pointer 1->6] -type : 0 -color : #808080 -width : 1 - -[Pointer 6->4] -type : 0 -color : #808080 -width : 1 - -[Pointer 4->2] -type : 0 -color : #808080 -width : 1 - -[Pointer 2->1] -type : 0 -color : #808080 -width : 1 - -[Pointer 3->6] -type : 0 -color : #808080 -width : 1 - -[Pointer 3->4] -type : 0 -color : #808080 -width : 1 - diff --git a/Examples/BreadthFirstSearch/bfs.js b/Examples/BreadthFirstSearch/bfs.js index 7ed986b4..26fd0ebd 100644 --- a/Examples/BreadthFirstSearch/bfs.js +++ b/Examples/BreadthFirstSearch/bfs.js @@ -1,65 +1,55 @@ -/** - * Breadth-first search +/* + * 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. * - * __(')< written by lambda fairy - * \___) */ -function reset_graph(g) { - function reset(thing) { - thing.set_type(0) - thing.color = '#999' - } - g.nodes().forEach(reset) - g.edges().forEach(reset) -} +function reset(G) { + G.nodes().forEach(unmark) + G.edges().forEach(unmark) -function add_mine(g) { - var mine = g.nodes()[2] // Completely arbitrary - mine.set_type(1) + G.nodes().forEach(function(node) { + node.seen = false + }) } -function bfs(start, mark, is_match) { - var queue = [start] - start.seen = true; mark(start); interrupt() - var cursor - while (queue.length > 0) { - cursor = queue.shift() - if (is_match(cursor)) { - interrupt() - return true - } - cursor.neighbors().forEach(function(node) { - if (!node.seen) { - node.seen = true; mark(node) - queue.push(node) - } - }); interrupt() - } - return false +function mark(node) { + node.color = '#c00' } -function set_type_to(value) { - return function(thing) { thing.set_type(value) } +function unmark(node) { + node.color = '#fff' } -reset_graph(lake) -add_mine(lake) +function bfs(G, start) { + + var queue = [start] + start.seen = true -bfs(lake.nodes()[0], - function(node) { - Console.log('Found ' + node.name) - node.color = '#f90' - }, - function(node) { - var match = false - if (node.type() == 1) { - Console.log('-- Deactivated mine at ' + node.name) - node.color = '#c00' - return true - } else { - Console.log('-- Cleared ' + node.name) - node.color = '#0a0' - return false - } - }) + 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/BreadthFirstSearch/bfs.rocs b/Examples/BreadthFirstSearch/bfs.rocs deleted file mode 100644 index ee7723c9..00000000 Binary files a/Examples/BreadthFirstSearch/bfs.rocs and /dev/null differ diff --git a/Examples/BreadthFirstSearch/journal.html b/Examples/BreadthFirstSearch/journal.html deleted file mode 100644 index fd2ffe41..00000000 --- a/Examples/BreadthFirstSearch/journal.html +++ /dev/null @@ -1,23 +0,0 @@ - - -

This project demonstrates **breadth-first search**, a simple algorithm for searching through a graph.

-


-


-

## Story

-


-

A few days ago, someone accidentally dropped a mine in the middle of a lake (hey, The Matrix makes less sense than this and it earned millions). This poses a serious threat to the inhabitants of the surrounding area – especially the ducks – so the local council has tasked us with locating and deactivating the charge. To help with the search, we have a fancy object detector that can scan the whole lake at once. Unfortunately, it can't tell the difference between a mine and an innocent fish, so we have to check each point ourselves.

-


-


-

## How it works

-


-

In breadth-first search, we keep track of which nodes to examine next using a queue. Then we proceed as follows:

-


-

1. Choose one node from the graph, and add it to the queue. This will be our starting point.

-

2. Pop a node from the queue and examine it.

-

* If it's a mine, we're done!

-

* Otherwise, take the nodes next to it. If we haven't checked that node before, add it to the queue – we'll check it later.

-

3. If the queue is empty, then we've searched the whole lake without getting a match. There's probably nothing to worry about.

-

4. If the queue is not empty, repeat from step 2.

-


\ No newline at end of file diff --git a/Examples/DepthFirstsSearch/dfs.js b/Examples/DepthFirstsSearch/dfs.js new file mode 100644 index 00000000..281f722d --- /dev/null +++ b/Examples/DepthFirstsSearch/dfs.js @@ -0,0 +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 new file mode 100644 index 00000000..8b52392f --- /dev/null +++ b/Examples/DijkstraShortestPath/dijkstra.js @@ -0,0 +1,164 @@ +/* + * Dijkstra Single Source Shortest Path Algorithm + * + * Written by ctonetti + * + * (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 new file mode 100644 index 00000000..112fbac9 --- /dev/null +++ b/Examples/FloydWarshallMultipleSourcesShortestPath/floydWarshall.js @@ -0,0 +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/HopcraftKarpBipartiteMatching/hopcroftKarp.js b/Examples/HopcraftKarpBipartiteMatching/hopcroftKarp.js new file mode 100644 index 00000000..fe525281 --- /dev/null +++ b/Examples/HopcraftKarpBipartiteMatching/hopcroftKarp.js @@ -0,0 +1,203 @@ +/* + * Hopcroft-Karp Maximum Bipartite Matching + * + * Written by ctonetti + * + * Time Complexity: O(|E|sqrt(|V|)) + * + * A matching is a set of edges chosen in such a way that no + * two edges share an endpoint. A matching is of maximum size + * when it has the maximum number of edges possible. + * + * This algorithm starts with an empty matching and builds a + * maximum matching by finding augmenting paths iteratively. + * The algorithm ends when there is no augmenting paths left. + * + */ + +var L = [] // Left side of the bipartite graph +var R = [] // Right side of the bipartite graph + +var M = {} // Matching +var D = {} // Distances + +var INF = 10000000 +var NIL = -1 + +function reset(G) { + G.nodes().forEach(unmark) + G.edges().forEach(unmark) + + G.nodes().forEach(function(node) { + node.seen = false + node.bip = 0 + }) +} + +function mark(node) { + node.color = '#c00' +} + +function unmark(node) { + node.color = '#fff' +} + +function printMatchings() { + + Console.log("Matchings:") + + L.forEach(function(node) { + if (M[node.id] != NIL) { + Console.log(" " + node.id + " --- " + M[node.id].id) + } + }) +} + +// Modified BFS to divide the graph in two +// disjoint sets of nodes. This function also +// checks if the graph is really bipartite +function divideBipartite(G) { + + if (G.nodes().length == 0) { + Console.log("Empty Graph!") + return false + } + + var N = G.nodes() + var Q = [N[0]] + + N[0].bip = 1 + + while (Q.length > 0) { + + var top = Q.shift() + + top.seen = true + mark(top) + + neigh = top.neighbors() + + // Color the neighbors of top + for (var i = 0; i < neigh.length; i++) { + if (neigh[i].bip == 0) { // Not assigned a set yet + neigh[i].bip = (top.bip == 1 ? 2 : 1) + } else { // Assigned, check if correct + if (neigh[i].bip == top.bip && neigh[i].id != top.id) { + return false + } + } + + if (!neigh[i].seen) { + Q.push(neigh[i]) + } + } + } + + G.nodes().forEach(function(node) { + if (node.bip == 1) { + L.push(node) + } + + if (node.bip == 2) { + R.push(node) + } + + if (node.bip == 0) { + Console.log("Unconnected nodes!") + } + }) + + return true +} + +// Modified BFS to check if an augmenting path exist +// BFS treat the graph as layers, helping in identifying +// alternating paths. Only consider one side of the +// bipartite graph. +function hasAugmentingPath(G) { + + Q = [] // Queue + + for (var i = 0; i < L.length; i++) { + if (M[L[i].id] == NIL) { + D[L[i].id] = 0 + Q.push(L[i]) // Add free vertex to queue + } else { + D[L[i].id] = INF + } + } + + D[NIL] = INF + + while (Q.length > 0) { + + var t = Q.pop() + + if (t != NIL) { + t.neighbors().forEach(function(neigh) { + if (D[M[neigh.id]] == INF) { + D[M[neigh.id]] = D[t.id] + 1 + Q.push(M[neigh.id]) + } + }) + } + } + + return (D[NIL] != INF) +} + +// Get the augmenting path that begins in node +// "node" and apply to the matching. If no such +// path exist, the function returns false, true +// otherwise. +function applyAugmentingPath(G, node) { + + if (node != NIL) { + + var neighs = node.neighbors() + + for (var i = 0; i < neighs.length; i++) { + + var neigh = neighs[i] + + if (D[M[neigh.id]] == D[node.id] + 1) { + M[neigh.id] = node + M[node.id] = neigh + return true; + } + } + + D[node.id] = INF + return false + } + + return true +} + +// Main function +function hopcroftKarp(G) { + + // Initialize all nodes as not matched + G.nodes().forEach(function(node) { + M[node.id] = NIL + }) + + var matches = 0 + + // While a augmenting path exist, + // update matching + while(hasAugmentingPath(G)) { + for (var i = 0; i < L.length; i++) { + if (M[L[i].id] == NIL && applyAugmentingPath(G, L[i])) { + matches++ // Count number of matches + } + } + } + + return matches +} + +reset(Document) +divideBipartite(Document) +Console.log("Total Matchings: " + hopcroftKarp(Document)) +printMatchings() diff --git a/Examples/KruskalSpanningTree/kruskal.js b/Examples/KruskalSpanningTree/kruskal.js new file mode 100644 index 00000000..fcfc1e16 --- /dev/null +++ b/Examples/KruskalSpanningTree/kruskal.js @@ -0,0 +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/journal.html b/Examples/PrimSpanningTree/journal.html deleted file mode 100644 index 98cb0669..00000000 --- a/Examples/PrimSpanningTree/journal.html +++ /dev/null @@ -1,25 +0,0 @@ - - -

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..e115b468 --- /dev/null +++ b/Examples/PrimSpanningTree/prim.js @@ -0,0 +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/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 diff --git a/Examples/TopologicalSort/topologicalSort.js b/Examples/TopologicalSort/topologicalSort.js new file mode 100644 index 00000000..9a5cc7f9 --- /dev/null +++ b/Examples/TopologicalSort/topologicalSort.js @@ -0,0 +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() diff --git a/libgraphtheory/editorplugins/generategraph/generategraphwidget.cpp b/libgraphtheory/editorplugins/generategraph/generategraphwidget.cpp index 3c2e2e5e..834b1319 100644 --- a/libgraphtheory/editorplugins/generategraph/generategraphwidget.cpp +++ b/libgraphtheory/editorplugins/generategraph/generategraphwidget.cpp @@ -1,706 +1,708 @@ /* * Copyright 2011-2014 Andreas Cord-Landwehr * Copyright 2019 Caio Henrique Segawa Tonetti * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or (at your option) version 3, or any * later version accepted by the membership of KDE e.V. (or its * successor approved by the membership of KDE e.V.), which shall * act as a proxy defined in Section 6 of version 3 of the license. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library. If not, see . */ #include "generategraphwidget.h" #include "typenames.h" #include "graphdocument.h" #include "edge.h" #include "modifiers/topology.h" #include "logging_p.h" #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace GraphTheory; // typedefs used for the boost graph library typedef boost::adjacency_list < boost::listS, boost::vecS, boost::undirectedS, boost::property > Graph; typedef boost::rectangle_topology<> topology_type; typedef topology_type::point_type point_type; typedef std::vector PositionVec; typedef boost::iterator_property_map < PositionVec::iterator, boost::property_map::type > PositionMap; // handle boost exceptions namespace boost { void throw_exception(std::exception const &e) { qCCritical(GRAPHTHEORY_GENERAL) << "Exception:" << e.what(); } } GenerateGraphWidget::GenerateGraphWidget(GraphDocumentPtr document, QWidget *parent) : QDialog(parent) , m_document(document) , m_seed(1) { // setup default identifiers for the created graphs m_defaultIdentifiers.insert(MeshGraph, "MeshGraph"); m_defaultIdentifiers.insert(StarGraph, "StarGraph"); m_defaultIdentifiers.insert(CircleGraph, "CircleGraph"); m_defaultIdentifiers.insert(ErdosRenyiRandomGraph, "RandomGraph"); m_defaultIdentifiers.insert(RandomTree, "RandomTree"); m_defaultIdentifiers.insert(RandomDag, "RandomDag"); m_defaultIdentifiers.insert(PathGraph, "PathGraph"); m_defaultIdentifiers.insert(CompleteGraph, "CompleteGraph"); m_defaultIdentifiers.insert(CompleteBipartiteGraph, "CompleteBipartite"); // set default graph m_graphGenerator = MeshGraph; setWindowTitle(i18nc("@title:window", "Generate Graph")); QVBoxLayout *mainLayout = new QVBoxLayout(this); setLayout(mainLayout); QWidget *widget = new QWidget(this); ui = new Ui::GenerateGraphWidget; ui->setupUi(widget); mainLayout->addWidget(widget); ui->buttonShowAdvanced->setIcon(QIcon::fromTheme("rocsadvancedsetup")); connect(ui->buttons, &QDialogButtonBox::accepted, this, &QDialog::accept); connect(ui->buttons, &QDialogButtonBox::rejected, this, &QDialog::reject); connect(this, &QDialog::accepted, this, &GenerateGraphWidget::generateGraph); connect(ui->comboGraphGenerator, static_cast(&QComboBox::currentIndexChanged), this, &GenerateGraphWidget::setGraphGenerator); connect(ui->nodeTypeSelector, static_cast(&QComboBox::currentIndexChanged), this, &GenerateGraphWidget::setNodeType); connect(ui->edgeTypeSelector, static_cast(&QComboBox::currentIndexChanged), this, &GenerateGraphWidget::setEdgeType); // set random seeds qint64 currentTime = QDateTime::currentMSecsSinceEpoch(); uint badRandomSeed = qHash(currentTime) % 99999; badRandomSeed = (badRandomSeed == 0) ? 1 : badRandomSeed; ui->randomGeneratorSeed->setValue(badRandomSeed); ui->GNPGeneratorSeed->setValue(badRandomSeed); ui->randomTreeGeneratorSeed->setValue(badRandomSeed); // set visibility for advanced options // TODO move to containers for easier handling ui->label_randomGeneratorSeed->setVisible(false); ui->randomGeneratorSeed->setVisible(false); ui->label_GNPGeneratorSeed->setVisible(false); ui->GNPGeneratorSeed->setVisible(false); ui->label_randomTreeGeneratorSeed->setVisible(false); ui->randomTreeGeneratorSeed->setVisible(false); + ui->label_dagGeneratorSeed->setVisible(false); + ui->dagGeneratorSeed->setVisible(false); for (int i = 0; i < document->edgeTypes().length(); ++i) { EdgeTypePtr type = document->edgeTypes().at(i); QString item = i18nc( "@item:inlistbox", "%1 (ID %2)", type->name(), i); ui->edgeTypeSelector->addItem(item, QVariant(i)); } ui->edgeTypeSelector->setCurrentIndex(0); for (int i = 0; i < document->nodeTypes().length(); ++i) { NodeTypePtr type = document->nodeTypes().at(i); QString item = i18nc( "@item:inlistbox", "%1 (ID %2)", type->name(), i); ui->nodeTypeSelector->addItem(item, QVariant(i)); } ui->nodeTypeSelector->setCurrentIndex(0); } void GenerateGraphWidget::setGraphGenerator(int index) { m_graphGenerator = GraphGenerator(index); if (m_defaultIdentifiers.contains(m_graphGenerator)) { ui->identifier->setText(m_defaultIdentifiers[m_graphGenerator]); } else { ui->identifier->setText("Graph"); } } void GenerateGraphWidget::setGraphIdentifier(const QString &identifier) { m_identifier = identifier; } void GenerateGraphWidget::setNodeType(int type) { if (type >= m_document->nodeTypes().length()) { qCWarning(GRAPHTHEORY_GENERAL) << "Node type " << type << " does not exist: aborting"; return; } m_nodeType = m_document->nodeTypes().at(type); } void GenerateGraphWidget::setEdgeType(int type) { if (type >= m_document->edgeTypes().length()) { qCWarning(GRAPHTHEORY_GENERAL) << "Edge type " << type << " does not exist: aborting"; return; } m_edgeType = m_document->edgeTypes().at(type); } void GenerateGraphWidget::setSeed(int seed) { m_seed = seed; } void GenerateGraphWidget::generateGraph() { setGraphIdentifier(ui->identifier->text()); switch (m_graphGenerator) { case MeshGraph: generateMesh(ui->meshRows->value(), ui->meshColumns->value()); break; case CircleGraph: generateCircle(ui->circleNodes->value()); break; case StarGraph: generateStar(ui->starSatelliteNodes->value()); break; case RandomEdgeGraph: setSeed(ui->randomGeneratorSeed->value()); generateRandomGraph( ui->randomNodes->value(), ui->randomEdges->value(), ui->randomAllowSelfedges->isTristate() ); break; case ErdosRenyiRandomGraph: - setSeed(ui->randomGeneratorSeed->value()); + setSeed(ui->GNPGeneratorSeed->value()); generateErdosRenyiRandomGraph( ui->GNPNodes->value(), ui->GNPEdgeProbability->value(), ui->GNPAllowSelfedges->isTristate() ); break; case RandomTree: setSeed(ui->randomTreeGeneratorSeed->value()); generateRandomTreeGraph( ui->randomTreeNodes->value() ); break; case RandomDag: - setSeed(ui->randomGeneratorSeed->value()); + setSeed(ui->dagGeneratorSeed->value()); generateRandomDagGraph( ui->randomDagNumberOfNodes->value(), ui->randomDagEdgeProbability->value() ); break; case PathGraph: generatePathGraph( ui->pathNodes->value() ); break; case CompleteGraph: generateCompleteGraph( ui->completeNodes->value() ); break; case CompleteBipartiteGraph: generateCompleteBipartiteGraph( ui->completeBipartiteNodesLeft->value(), ui->completeBipartiteNodesRight->value() ); default: break; } close(); deleteLater(); } GenerateGraphWidget::~GenerateGraphWidget() { delete ui; } QPointF GenerateGraphWidget::documentCenter() const { QPointF center = QPointF(0, 0); qreal xSum = 0; qreal ySum = 0; int number = m_document->nodes().length(); foreach (NodePtr node, m_document->nodes()) { xSum += node->x(); ySum += node->y(); } if (number > 0) { center.setX(xSum / number); center.setY(ySum / number); } return center; } /** @brief make sure all @p nodes are on the canvas * * Given a collection of @p nodes, make sure they are all visible * on the canvas (e.g. have a non-negative X and Y coordinate) * by finding the smallest X and Y and then uniformly translating * all of the @p nodes by that amount if either are negative. */ template void adjustNodesToCanvas(T& nodes) { qreal minX = 0; qreal minY = 0; for(auto& n : nodes) { if (n->x() < minX) { minX = n->x(); } if (n->y() < minY) { minY = n->y(); } } if ((minX < 0) || (minY < 0)) { // If either is non-negative, make it zero to not translate on that axis minX = qMin(minX, qreal(0)); minY = qMin(minY, qreal(0)); // min* is negative or zero, so subtracting it means **adding** to the coordinate for(auto& n : nodes) { n->setX(n->x() - minX); n->setY(n->y() - minY); } } } void GenerateGraphWidget::generateMesh(int rows, int columns) { QPointF center = documentCenter(); if (rows < 1) { rows = 1; } if (columns < 1) { columns = 1; } // create mesh of NxN points QMap, NodePtr > meshNodes; // create mesh nodes, store them in map for (int i = 0; i < columns; ++i) { for (int j = 0; j < rows; ++j) { NodePtr node = Node::create(m_document); node->setX(i * 50 - (int)25 * columns + center.x()); node->setY(j * 50 - (int)25 * rows + center.y()); node->setType(m_nodeType); meshNodes[qMakePair(i, j)] = node; } } adjustNodesToCanvas(meshNodes); // connect mesh nodes for (int i = 0; i < columns; ++i) { for (int j = 0; j < rows; ++j) { if (j < columns - 1) { // horizontal edges EdgePtr edge = Edge::create(meshNodes[qMakePair(i, j)], meshNodes[qMakePair(i, j + 1)]); edge->setType(m_edgeType); if (m_edgeType->direction() == EdgeType::Direction::Unidirectional) { EdgePtr edge = Edge::create(meshNodes[qMakePair(i, j + 1)], meshNodes[qMakePair(i, j)]); edge->setType(m_edgeType); } } if (i < rows - 1) { // vertical edges EdgePtr edge = Edge::create(meshNodes[qMakePair(i, j)], meshNodes[qMakePair(i + 1, j)]); edge->setType(m_edgeType); if (m_edgeType->direction() == EdgeType::Direction::Unidirectional) { EdgePtr edge = Edge::create(meshNodes[qMakePair(i + 1, j)], meshNodes[qMakePair(i, j)]); edge->setType(m_edgeType); } } } } } void GenerateGraphWidget::generateStar(int satelliteNodes) { QPointF center = documentCenter(); // compute radius such that nodes have space ~50 between each other // circle that border-length of 2*PI*radius int radius = 50 * satelliteNodes / (2 * boost::math::constants::pi()); NodeList nodes; for (int i = 1; i <= satelliteNodes; i++) { NodePtr node = Node::create(m_document); node->setX(sin(i * 2 * boost::math::constants::pi() / satelliteNodes)*radius + center.x()); node->setY(cos(i * 2 * boost::math::constants::pi() / satelliteNodes)*radius + center.y()); node->setType(m_nodeType); nodes.append(node); } // center NodePtr node = Node::create(m_document); node->setX(center.x()); node->setY(center.y()); node->setType(m_nodeType); nodes.prepend(node); adjustNodesToCanvas(nodes); // connect circle nodes for (int i = 1; i <= satelliteNodes; ++i) { EdgePtr edge = Edge::create(nodes.at(0), nodes.at(i)); edge->setType(m_edgeType); } } void GenerateGraphWidget::generateCircle(int number) { QPointF center = documentCenter(); // compute radius such that nodes have space ~50 between each other // circle that border-length of 2*PI*radius int radius = 50 * number / (2 * boost::math::constants::pi()); QList< QPair > circleNodes; // create mesh nodes, store them in map NodeList nodes; for (int i = 1; i <= number; i++) { NodePtr node = Node::create(m_document); node->setX(sin(i * 2 * boost::math::constants::pi() / number)*radius + center.x()); node->setY(cos(i * 2 * boost::math::constants::pi() / number)*radius + center.y()); node->setType(m_nodeType); nodes.append(node); } adjustNodesToCanvas(nodes); // connect circle nodes for (int i = 0; i < number - 1; i++) { EdgePtr edge = Edge::create(nodes.at(i), nodes.at(i + 1)); edge->setType(m_edgeType); } EdgePtr edge = Edge::create(nodes.at(number - 1), nodes.at(0)); edge->setType(m_edgeType); } void GenerateGraphWidget::generateRandomGraph(int nodes, int edges, bool selfEdges) { QPointF center = documentCenter(); Graph randomGraph; std::mt19937 gen; gen.seed(static_cast(m_seed)); // generate graph boost::generate_random_graph( randomGraph, nodes, edges, gen, selfEdges ); // generate distribution topology and apply boost::rectangle_topology< std::mt19937 > topology(gen, center.x() - 20 * nodes, center.y() - 20 * nodes, center.x() + 20 * nodes, center.y() + 20 * nodes); PositionVec position_vec(boost::num_vertices(randomGraph)); PositionMap positionMap(position_vec.begin(), get(boost::vertex_index, randomGraph)); boost::random_graph_layout(randomGraph, positionMap, topology); // minimize cuts by Fruchtman-Reingold layout algorithm boost::fruchterman_reingold_force_directed_layout< boost::rectangle_topology< std::mt19937 >, Graph, PositionMap > (randomGraph, positionMap, topology, boost::cooling(boost::linear_cooling(100)) ); // put nodes at whiteboard as generated QMap mapNodes; boost::graph_traits::vertex_iterator vi, vi_end; for (boost::tie(vi, vi_end) = boost::vertices(randomGraph); vi != vi_end; ++vi) { mapNodes[*vi] = Node::create(m_document); mapNodes[*vi]->setX(positionMap[*vi][0]); mapNodes[*vi]->setY(positionMap[*vi][1]); mapNodes[*vi]->setType(m_nodeType); } adjustNodesToCanvas(mapNodes); boost::graph_traits::edge_iterator ei, ei_end; for (boost::tie(ei, ei_end) = boost::edges(randomGraph); ei != ei_end; ++ei) { EdgePtr edge = Edge::create(mapNodes[boost::source(*ei, randomGraph)], mapNodes[boost::target(*ei, randomGraph)]); edge->setType(m_edgeType); } } void GenerateGraphWidget::generateErdosRenyiRandomGraph(int nodes, double edgeProbability, bool selfEdges) { QPointF center = documentCenter(); std::mt19937 gen; gen.seed(static_cast(m_seed)); // generate graph typedef boost::erdos_renyi_iterator ergen; Graph randomGraph(ergen(gen, nodes, edgeProbability, selfEdges), ergen(), nodes); // generate distribution topology and apply boost::rectangle_topology< std::mt19937 > topology(gen, center.x() - 20 * nodes, center.y() - 20 * nodes, center.x() + 20 * nodes, center.y() + 20 * nodes); PositionVec position_vec(boost::num_vertices(randomGraph)); PositionMap positionMap(position_vec.begin(), get(boost::vertex_index, randomGraph)); boost::random_graph_layout(randomGraph, positionMap, topology); // minimize cuts by Fruchtman-Reingold layout algorithm boost::fruchterman_reingold_force_directed_layout< boost::rectangle_topology< std::mt19937 >, Graph, PositionMap > (randomGraph, positionMap, topology, boost::cooling(boost::linear_cooling(100)) ); // put nodes at whiteboard as generated QMap mapNodes; boost::graph_traits::vertex_iterator vi, vi_end; for (boost::tie(vi, vi_end) = boost::vertices(randomGraph); vi != vi_end; ++vi) { mapNodes[*vi] = Node::create(m_document); mapNodes[*vi]->setX(positionMap[*vi][0]); mapNodes[*vi]->setY(positionMap[*vi][1]); mapNodes[*vi]->setType(m_nodeType); } adjustNodesToCanvas(mapNodes); boost::graph_traits::edge_iterator ei, ei_end; for (boost::tie(ei, ei_end) = boost::edges(randomGraph); ei != ei_end; ++ei) { EdgePtr edge = Edge::create(mapNodes[boost::source(*ei, randomGraph)], mapNodes[boost::target(*ei, randomGraph)]); edge->setType(m_edgeType); } } void GenerateGraphWidget::generateRandomTreeGraph(int number) { if (EdgeType::Unidirectional == m_edgeType->direction()){ QMessageBox::critical(this, "Incorrect Edge Direction", "Edges in a Tree must be bidirectional."); return; } std::mt19937 gen; gen.seed(static_cast(m_seed)); NodeList nodes; QVector notAdded; QVector added; for (int i = 0; i < number; i++) { NodePtr node = Node::create(m_document); node->setType(m_nodeType); nodes.append(node); notAdded.push_back(i); } // shuffle std::shuffle(notAdded.begin(), notAdded.end(), gen); // add root added.push_back(notAdded.front()); notAdded.pop_front(); while (!notAdded.empty()) { boost::random::uniform_int_distribution<> dist(0, added.size()-1); int randomIdx = dist(gen); int next = notAdded.front(); notAdded.pop_front(); added.push_back(next); EdgePtr edge = Edge::create(nodes.at(added[randomIdx]), nodes.at(next)); edge->setType(m_edgeType); } Topology::applyCircleAlignment(nodes, 300); Topology::applyMinCutTreeAlignment(nodes); adjustNodesToCanvas(nodes); } void GenerateGraphWidget::generateRandomDagGraph(int nodes, double edgeProbability) { if (EdgeType::Bidirectional == m_edgeType->direction()){ QMessageBox::critical(this, i18n("Incorrect Edge Direction"), i18n("Edges in a Directed Acyclical Graph must be directional.")); return; } std::mt19937 gen; gen.seed(static_cast(m_seed)); boost::random::uniform_real_distribution dist(0, 1); NodeList nodes_list; for (int j=0; j < nodes; j++) { NodePtr node = Node::create(m_document); node->setType(m_nodeType); nodes_list.append(node); } // Create random edges for (int i=0; i < nodes - 1; i++) { for (int j=i+1; j < nodes; j++) { if (dist(gen)< edgeProbability) { EdgePtr edge = Edge::create(nodes_list.at(i), nodes_list.at(j)); edge->setType(m_edgeType); } } } Topology::applyCircleAlignment(nodes_list, 300); Topology::applyMinCutTreeAlignment(nodes_list); adjustNodesToCanvas(nodes_list); } void GenerateGraphWidget::generatePathGraph(int pathSize) { QPointF center = documentCenter(); QList< QPair > pathNodes; NodeList nodes_list; for (int i = 1; i <= pathSize; i++) { NodePtr node = Node::create(m_document); node->setX(i * 50 + center.x()); node->setY(center.y()); node->setType(m_nodeType); nodes_list.append(node); } adjustNodesToCanvas(nodes_list); for (int i = 0; i < pathSize - 1; i++) { EdgePtr edge = Edge::create(nodes_list.at(i), nodes_list.at(i + 1)); edge->setType(m_edgeType); } } void GenerateGraphWidget::generateCompleteGraph(int nodes) { QPointF center = documentCenter(); // compute radius such that nodes have space ~100 between each other // circle that border-length of 2*PI*radius int radius = 100 * nodes / (2 * boost::math::constants::pi()); QList< QPair > circleNodes; NodeList node_list; for (int i = 1; i <= nodes; i++) { NodePtr node = Node::create(m_document); node->setX(sin(i * 2 * boost::math::constants::pi() / nodes)*radius + center.x()); node->setY(cos(i * 2 * boost::math::constants::pi() / nodes)*radius + center.y()); node->setType(m_nodeType); node_list.append(node); } adjustNodesToCanvas(node_list); for (int i = 0; i < nodes - 1; i++) { for (int j = i + 1; j < nodes; j++) { EdgePtr edge_lr = Edge::create(node_list.at(i), node_list.at(j)); edge_lr->setType(m_edgeType); if (m_edgeType->direction() == EdgeType::Direction::Unidirectional) { EdgePtr edge_rl = Edge::create(node_list.at(j), node_list.at(i)); edge_rl->setType(m_edgeType); } } } } void GenerateGraphWidget::generateCompleteBipartiteGraph(int nodes_left, int nodes_right) { QPointF center = documentCenter(); int separator = 100; NodeList node_list; for (int i = 0; i < nodes_left; i++) { NodePtr node = Node::create(m_document); node->setX(center.x()); node->setY(center.y() + i * 50); node->setType(m_nodeType); node_list.append(node); } for (int i = 0; i < nodes_right; i++) { NodePtr node = Node::create(m_document); node->setX(center.x() + separator); node->setY(center.y() + i * 50); node->setType(m_nodeType); node_list.append(node); } adjustNodesToCanvas(node_list); for (int i = 0; i < nodes_left; i++) { for (int j = 0; j < nodes_right; j++){ EdgePtr edge_lr = Edge::create(node_list.at(i), node_list.at(j + nodes_left)); edge_lr->setType(m_edgeType); if (m_edgeType->direction() == EdgeType::Direction::Unidirectional) { EdgePtr edge_rl = Edge::create(node_list.at(j + nodes_left), node_list.at(i)); edge_rl->setType(m_edgeType); } } } } diff --git a/libgraphtheory/editorplugins/generategraph/generategraphwidget.ui b/libgraphtheory/editorplugins/generategraph/generategraphwidget.ui index 462ed17a..7e08548a 100644 --- a/libgraphtheory/editorplugins/generategraph/generategraphwidget.ui +++ b/libgraphtheory/editorplugins/generategraph/generategraphwidget.ui @@ -1,735 +1,781 @@ GenerateGraphWidget 0 0 354 423 Generate Graph Select the graph generator. Mesh Graph Star Graph Circle Graph Random Graph Erdös-Renyi Graph Random Tree Graph Random Dag Graph Path Graph Complete Graph Complete Bipartite 0 0 24 24 Show advanced settings. true Set the unique identifier of the generated graph. Graph The node type to create the nodes of the graph with Node type The identifier of the created graph (used for scripting) Identifier - 0 + 3 QFormLayout::ExpandingFieldsGrow Number of Columns: meshColumns 1 5 Number of Rows: meshRows 1 5 Satellite Nodes: 1 999 10 Number of Nodes: 1 999 10 Nodes: 1 999 10 Edges: 20 Allow self-edges: Generator Seed: 1 999999 Nodes (n): Allow self-edges: 1 10 Edge Probability (p): Generator Seed: 1 999999 3 0.001000000000000 1.000000000000000 0.250000000000000 Nodes: 1 10 Generator Seed: 1 999999 Number of Nodes - 10 + 1 999 Edge Probability 1.000000000000000 0.100000000000000 0.500000000000000 + + + + Generator Seed + + + + + + + true + + + Number of Nodes: 4 Number of Nodes: 5 Left Set Nodes: 4 Right Set Nodes: 4 QDialogButtonBox::Cancel|QDialogButtonBox::Ok Select the edge type for connections of the generated graph. Qt::Horizontal The edge type to create the edges of the graph with Edge type Graph Generator Select the node type for node elements of the generated graph. KComboBox QComboBox
kcombobox.h
 buttonShowAdvanced toggled(bool) label_randomGeneratorSeed setVisible(bool) 242 21 46 158 buttonShowAdvanced toggled(bool) randomGeneratorSeed setVisible(bool) 242 21 98 158 buttonShowAdvanced toggled(bool) label_GNPGeneratorSeed setVisible(bool) 242 21 18 158 buttonShowAdvanced toggled(bool) GNPGeneratorSeed setVisible(bool) 242 21 83 158 buttonShowAdvanced toggled(bool) label_randomTreeGeneratorSeed setVisible(bool) 242 21 46 159 buttonShowAdvanced toggled(bool) randomTreeGeneratorSeed setVisible(bool) 242 21 98 159 comboGraphGenerator currentIndexChanged(int) stackedWidget setCurrentIndex(int) 169 16 146 194 + + buttonShowAdvanced + toggled(bool) + label_dagGeneratorSeed + setVisible(bool) + + + 331 + 23 + + + 70 + 249 + + + + + buttonShowAdvanced + toggled(bool) + dagGeneratorSeed + setVisible(bool) + + + 331 + 23 + + + 238 + 249 + + +