module Silicium::Graphs
Constants
- Pair
Public Instance Methods
add_to_queue(graph, queue, node, visited)
click to toggle source
# File lib/graph.rb, line 196 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
breadth_first_search?(graph, start, goal)
click to toggle source
# File lib/graph.rb, line 181 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 if node == goal return true end add_to_queue(graph, queue, node, visited) end false end
connected?(graph)
click to toggle source
# File lib/graph.rb, line 205 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
dfu(graph, vertice, visited)
click to toggle source
# File lib/graph.rb, line 227 def dfu(graph, vertice, visited) visited[vertice] = true graph.vertices[vertice].each do |item| unless visited[item] dfu(graph, item, visited) end end end
dijkstra_algorythm(graph, starting_vertex)
click to toggle source
# File lib/graph.rb, line 236 def dijkstra_algorythm(graph, starting_vertex) # end
number_of_connected(graph)
click to toggle source
# File lib/graph.rb, line 215 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