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