class Graph
Attributes
graph[RW]
Public Class Methods
new(args)
click to toggle source
# File lib/graphify/graph.rb, line 6 def initialize(args) @graph = if args[:storage_type] == 'matrix' GraphMatrix.new(args) elsif args[:storage_type] == 'list' GraphList.new(args) end @type = args[:type] == 'directed' ? :digraph : :graph @name = args[:name] @storage_type = args[:storage_type] end
Public Instance Methods
dfs_tree(vertex)
click to toggle source
# File lib/graphify/graph.rb, line 24 def dfs_tree(vertex) g = initialize_g dfs_helper(vertex, [], g) g end
dfs_tree_picture(vertex)
click to toggle source
# File lib/graphify/graph.rb, line 34 def dfs_tree_picture(vertex) tree = dfs_tree(vertex) if @storage_type == 'matrix' produce_picture_from_matrix(tree, '_dfs_tree.png') elsif @storage_type == 'list' produce_picture_from_list(tree, '_dfs_tree.png') end end
edges()
click to toggle source
# File lib/graphify/graph.rb, line 30 def edges @graph.edges_with_weights end
mst_edges()
click to toggle source
# File lib/graphify/graph.rb, line 85 def mst_edges kruskals_edges end
mst_picture()
click to toggle source
# File lib/graphify/graph.rb, line 78 def mst_picture g = GraphViz.new(:G, type: @type) picture_vertices = add_vertices_to_picture(g) add_mst_edges(picture_vertices, g) g.output(png: @name + '_minimum_spanning_tree.png') end
picture()
click to toggle source
# File lib/graphify/graph.rb, line 17 def picture g = GraphViz.new(:G, type: @type) vertices = add_vertices_to_picture(g) add_edges_to_picture(vertices, g) g.output(png: @name + '.png') end
scc_edge_set()
click to toggle source
# File lib/graphify/graph.rb, line 63 def scc_edge_set construct_scc_edges(scc_vertex_sets) end
scc_picture()
click to toggle source
# File lib/graphify/graph.rb, line 67 def scc_picture g = GraphViz.new(:G, type: @type) picture_vertices = add_scc_vertices(scc_vertex_sets, g) add_scc_edges(picture_vertices, scc_edge_set, g) g.output(png: @name + '_strongly_connected_components.png') end
scc_vertex_sets()
click to toggle source
# File lib/graphify/graph.rb, line 59 def scc_vertex_sets scc_vertex_sets_helper end
shortest_path_tree(vertex)
click to toggle source
# File lib/graphify/graph.rb, line 43 def shortest_path_tree(vertex) g = initialize_g distances, predecessors = initialize_djikstras(vertex) djikstras_helper(vertex, [], distances, predecessors, g) g end
shortest_path_tree_picture(vertex)
click to toggle source
# File lib/graphify/graph.rb, line 50 def shortest_path_tree_picture(vertex) tree = shortest_path_tree(vertex) if @storage_type == 'matrix' produce_picture_from_matrix(tree, '_shortest_path_tree.png') elsif @storage_type == 'list' produce_picture_from_list(tree, '_shortest_path_tree.png') end end
topological_sort()
click to toggle source
# File lib/graphify/graph.rb, line 74 def topological_sort scc_total_ordering end
Private Instance Methods
add_edges_to_picture(vertices, g)
click to toggle source
# File lib/graphify/graph.rb, line 263 def add_edges_to_picture(vertices, g) @graph.edges_with_weights.each do |edge| picture_edge = g.add_edges(vertices[edge[0]], vertices[edge[1]]) picture_edge[label: edge[2].to_s] end end
add_matrix_edge_to_picture(from, to, edges, vertices, picture)
click to toggle source
# File lib/graphify/graph.rb, line 148 def add_matrix_edge_to_picture(from, to, edges, vertices, picture) return if edges[from][to] == nil picture_edge = picture.add_edges(vertices[from], vertices[to]) picture_edge[label: edges[from][to].to_s] end
add_mst_edges(vertices, g)
click to toggle source
# File lib/graphify/graph.rb, line 243 def add_mst_edges(vertices, g) kruskals_edges.each do |edge| picture_edge = g.add_edges(vertices[edge[0]], vertices[edge[1]]) picture_edge[label: edge[2].to_s] end end
add_predecessor(from, to, g)
click to toggle source
# File lib/graphify/graph.rb, line 143 def add_predecessor(from, to, g) return if to == from g[from][to] = @graph.get_edge_weight(from, to) end
add_scc_edges(scc_picture_vertices, scc_edge_set, g)
click to toggle source
# File lib/graphify/graph.rb, line 215 def add_scc_edges(scc_picture_vertices, scc_edge_set, g) (0..scc_edge_set.size - 1).each do |from| (0..scc_edge_set.size - 1).each do |to| g.add_edges(scc_picture_vertices[from], scc_picture_vertices[to]) unless scc_edge_set[from][to].nil? end end end
add_scc_vertices(scc_vertex_set, g)
click to toggle source
# File lib/graphify/graph.rb, line 207 def add_scc_vertices(scc_vertex_set, g) vertices = {} scc_vertex_set.each do |key, value| vertices[key] = g.add_nodes(value.reduce('') { |memo, vertex| memo + vertex.to_s + ', ' }) end vertices end
add_vertices_to_picture(g)
click to toggle source
Functions to draw the main picture
# File lib/graphify/graph.rb, line 255 def add_vertices_to_picture(g) vertices = {} @graph.vertices.each do |vertex| vertices[vertex] = g.add_nodes(vertex.to_s) end vertices end
construct_scc_edges(scc_vertex_set)
click to toggle source
# File lib/graphify/graph.rb, line 196 def construct_scc_edges(scc_vertex_set) edges = Array.new(scc_vertex_set.size) { Array.new(scc_vertex_set.size) } @graph.edges_with_weights.each do |edge| from = (scc_vertex_set.select { |k, value| value.include?(edge[0]) }).keys[0] to = (scc_vertex_set.select { |k , value| value.include?(edge[1]) }).keys[0] next if to == from || !edges[from][to].nil? edges[from][to] = 1 end edges end
dfs_helper(vertex, seen, g)
click to toggle source
Depth First Search Functions
# File lib/graphify/graph.rb, line 108 def dfs_helper(vertex, seen, g) seen << vertex @graph.get_out_edges(vertex).each do |neighbour| next if seen.include?(neighbour) g[vertex][neighbour] = @graph.get_edge_weight(vertex, neighbour) dfs_helper(neighbour, seen, g) end end
djikstras_helper(vertex, seen, current_d, predecessors, g)
click to toggle source
# File lib/graphify/graph.rb, line 130 def djikstras_helper(vertex, seen, current_d, predecessors, g) seen << vertex add_predecessor(predecessors[vertex], vertex, g) @graph.get_out_edges(vertex).each do |node| next if seen.include?(node) || current_d[vertex] + @graph.get_edge_weight(vertex, node) > current_d[node] current_d[node] = current_d[vertex] + @graph.get_edge_weight(vertex, node) predecessors[node] = vertex end current_d.delete(vertex) return if seen.size == predecessors.keys.size djikstras_helper(current_d.key(current_d.values.min), seen, current_d, predecessors, g) end
initialize_djikstras(start)
click to toggle source
Djikstra’s Algorithm and Breadth First Search Functions
# File lib/graphify/graph.rb, line 119 def initialize_djikstras(start) dist = {} predecessors = {} @graph.vertices.each do |vertex| dist[vertex] = vertex == start ? 0 : Float::INFINITY predecessors[vertex] = vertex == start ? start : nil end return dist, predecessors end
initialize_g()
click to toggle source
Initialize the edge set for DFS, Djikstra’s
# File lib/graphify/graph.rb, line 95 def initialize_g num_vertices = @graph.vertices.size return Array.new(num_vertices) { Array.new(num_vertices) } if @storage_type == 'matrix' g = {} (0..num_vertices - 1).each do |num| g[num] = {} end g end
kruskals_edges()
click to toggle source
Kruskal’s and Minimum Spanning Trees
# File lib/graphify/graph.rb, line 228 def kruskals_edges num_vertices = @graph.vertices.size sorted_edges = @graph.edges_with_weights.sort_by { |elem| elem[2] } result = [] tree = [] sorted_edges.each do |edge| break if tree.size == num_vertices next if tree.include?(edge[0]) && tree.include?(edge[1]) tree << edge[0] unless tree.include?(edge[0]) tree << edge[1] unless tree.include?(edge[1]) result << edge end result end
produce_picture_from_list(edges, type_name)
click to toggle source
# File lib/graphify/graph.rb, line 281 def produce_picture_from_list(edges, type_name) picture = GraphViz.new(:G, type: @type) vertices = add_vertices_to_picture(picture) edges.keys.each do |key| edges[key].keys.each do |s_key| picture_edge = picture.add_edges(vertices[key], vertices[s_key]) picture_edge[label: edges[key][s_key].to_s] end end picture.output(png: @name + type_name) end
produce_picture_from_matrix(edges, type_name)
click to toggle source
# File lib/graphify/graph.rb, line 270 def produce_picture_from_matrix(edges, type_name) picture = GraphViz.new(:G, type: @type) vertices = add_vertices_to_picture(picture) (0..vertices.size - 1).each do |from| (0..vertices.size - 1).each do |to| add_matrix_edge_to_picture(from, to, edges, vertices, picture) end end picture.output(png: @name + type_name) end
scc_get_dfs_order(vertex, seen, finished)
click to toggle source
Strongly Connected Components functions
# File lib/graphify/graph.rb, line 158 def scc_get_dfs_order(vertex, seen, finished) seen << vertex @graph.get_out_edges(vertex).each do |neighbour| next if seen.include?(neighbour) || finished.include?(neighbour) scc_get_dfs_order(neighbour, seen, finished) end finished.unshift(vertex) end
scc_total_ordering()
click to toggle source
# File lib/graphify/graph.rb, line 175 def scc_total_ordering finished = [] for i in (0.. @graph.vertices.size - 1) scc_get_dfs_order(i, [], finished) unless finished.include?(i) end finished end
scc_transpose_dfs(vertex, seen, this_set)
click to toggle source
# File lib/graphify/graph.rb, line 167 def scc_transpose_dfs(vertex, seen, this_set) seen << vertex unless seen.include?(vertex) this_set << vertex unless this_set.include?(vertex) @graph.get_in_edges(vertex).each do |neighbour| scc_transpose_dfs(neighbour, seen, this_set) unless seen.include?(neighbour) || this_set.include?(neighbour) end end
scc_vertex_sets_helper()
click to toggle source
# File lib/graphify/graph.rb, line 183 def scc_vertex_sets_helper dfs_sets, seen, counter = {}, [], 0 scc_total_ordering.each do |vertex| next if seen.include?(vertex) dfs_set = [] scc_transpose_dfs(vertex, seen, dfs_set) dfs_sets[counter] = dfs_set counter += 1 end dfs_sets end