module Silicium::Graphs
Constants
- Pair
Public Instance Methods
add_edge!(mst, edge, label)
click to toggle source
# File lib/graph.rb, line 272 def add_edge!(mst, edge, label) mst.add_vertex!(edge[0]) mst.add_vertex!(edge[1]) mst.add_edge!(edge[0], edge[1]) mst.label_edge!(edge[0], edge[1], label) end
add_to_queue(graph, queue, node, visited)
click to toggle source
Adds to queue not visited vertices
# File lib/graph.rb, line 233 def add_to_queue(graph, queue, node, visited) graph.vertices[node].each do |child| unless visited[child] queue.push(child) visited[child] = true end end end
add_to_stack(graph, node, stack, visited)
click to toggle source
# File lib/graph/dfs.rb, line 21 def add_to_stack(graph, node, stack, visited) return if visited[node] visited[node] = true graph.vertices[node].each { |child| stack.push(child) } end
breadth_first_search?(graph, start, goal)
click to toggle source
Implements breadth-first search (BFS)
# File lib/graph.rb, line 219 def breadth_first_search?(graph, start, goal) visited = Hash.new(false) queue = Queue.new queue.push(start) visited[start] = true until queue.empty? do node = queue.pop return true if node == goal add_to_queue(graph, queue, node, visited) end false end
connected?(graph)
click to toggle source
Checks if graph is connected
# File lib/graph.rb, line 243 def connected?(graph) start = graph.vertices.keys[0] goal = graph.vertices.keys[graph.vertex_number - 1] pred = breadth_first_search?(graph, start, goal) graph.reverse! pred = pred and breadth_first_search?(graph, goal, start) graph.reverse! pred end
depth_first_search?(graph, start, goal)
click to toggle source
# File lib/graph/dfs.rb, line 4 def depth_first_search?(graph, start, goal) visited = Hash.new(false) stack = [start] until stack.empty? node = stack.pop return true if goal_node?(graph, node, goal) add_to_stack(graph, node, stack, visited) end false end
dfs_traverse(graph, start)
click to toggle source
# File lib/graph/dfs.rb, line 28 def dfs_traverse(graph, start) visited = Hash.new(false) traversed = [] dfs_traverse_recursive(graph, start, visited, traversed) traversed end
dfs_traverse_recursive(graph, node, visited, traversed)
click to toggle source
# File lib/graph/dfs.rb, line 35 def dfs_traverse_recursive(graph, node, visited, traversed) visited[node] = true traversed.push(node) graph.vertices[node].each { |child| dfs_traverse_recursive(graph, child, visited, traversed) unless visited[child] } end
dfu(graph, vertice, visited)
click to toggle source
Passes graph's vertices and marks them visited
# File lib/graph.rb, line 267 def dfu(graph, vertice, visited) visited[vertice] = true graph.vertices[vertice].each { |item| dfu(graph, item, visited) unless visited[item] } end
dijkstra_algorithm(graph, starting_vertex)
click to toggle source
Implements algorithm of Dijkstra
# File lib/graph.rb, line 303 def dijkstra_algorithm(graph, starting_vertex) if !graph.has_vertex?(starting_vertex) raise GraphError.new("Graph does not contains vertex #{starting_vertex}") end unvisited_vertices = graph.vertices.clone.to_a labels = {} paths = {} initialize_labels_and_paths(graph, labels,paths,starting_vertex) while unvisited_vertices.size > 0 unvisited_vertices.sort { |a, b| compare_labels(a, b, labels) } vertex = unvisited_vertices.first vertex[1].each do |adj| new_label = labels[vertex[0]] + graph.get_edge_label(vertex[0], adj) if change_label?(labels[adj], new_label) labels[adj] = new_label paths[adj] = paths[vertex[0]].clone paths[adj].push adj end end unvisited_vertices.delete_at(0) end {"labels" => labels, "paths" => paths} end
goal_node?(graph, node, goal)
click to toggle source
# File lib/graph/dfs.rb, line 15 def goal_node?(graph, node, goal) raise ArgumentError if graph.vertices[node].nil? node == goal end
graph_to_sets(graph)
click to toggle source
“Split” graph into elements like :[from, to] = label
# File lib/graph.rb, line 283 def graph_to_sets(graph) labels = {} graph.vertices.keys.each do |from| graph.adjacted_with(from).each { |to| labels[Pair.new(from, to)] = graph.get_edge_label(from, to) } end labels.to_set.sort_by { |elem| elem[1] }.to_h end
kruskal_mst(graph)
click to toggle source
Implements algorithm of Kruskal
# File lib/graph/kruskal.rb, line 23 def kruskal_mst(graph) mst = UnorientedGraph.new uf = UnionFind.new(graph) graph_to_sets(graph).each do |edge, label| unless uf.connected?(edge[0], edge[1]) add_edge!(mst, edge, label) uf.union(edge[0], edge[1]) end end mst end
number_of_connected(graph)
click to toggle source
Returns number of connected vertices
# File lib/graph.rb, line 254 def number_of_connected(graph) visited = Hash.new(false) res = 0 graph.vertices.keys.each do |v| unless visited[v] dfu(graph, v, visited) res += 1 end end res end
sum_labels(graph)
click to toggle source
# File lib/graph.rb, line 291 def sum_labels(graph) labels = 0 graph.vertices.keys.each do |from| graph.adjacted_with(from).each { |to| labels += graph.get_edge_label(from, to) } end labels / 2 end
Private Instance Methods
change_label?(label, new_label)
click to toggle source
# File lib/graph.rb, line 343 def change_label?(label, new_label) return true if label == -1 return false if new_label == -1 return new_label < label end
compare_labels(a, b, labels)
click to toggle source
# File lib/graph.rb, line 337 def compare_labels(a, b, labels) return -1 if labels[b[0]] == -1 return 1 if labels[a[0]] == -1 return labels[a[0]] <=> labels[b[0]] end
initialize_labels_and_paths(graph, labels,paths,starting_vertex)
click to toggle source
# File lib/graph.rb, line 329 def initialize_labels_and_paths(graph, labels,paths,starting_vertex) graph.vertices.each_key do |vertex| labels[vertex] = -1 paths[vertex] = [starting_vertex] end labels[starting_vertex] = 0 end