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