Module: Silicium::Graphs

Included in:
GraphVisualizer, OrientedGraph
Defined in:
lib/graph.rb,
lib/graph/dfs.rb,
lib/graph/scc.rb,
lib/graph/kruskal.rb,
lib/topological_sort.rb

Defined Under Namespace

Classes: Graph, GraphError, Node, OrientedGraph, Pair, TopologicalSortClass, UnionFind, UnorientedGraph

Instance Method Summary collapse

Instance Method Details

#add_edge!(mst, edge, label) ⇒ Object 



272
273
274
275
276
277
 
# 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) ⇒ Object

Adds to queue not visited vertices



233
234
235
236
237
238
239
240
 
# 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) ⇒ Object 



21
22
23
24
25
26
 
# 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) ⇒ Boolean

Implements breadth-first search (BFS)

Returns:

  • (Boolean) 


219
220
221
222
223
224
225
226
227
228
229
230
 
# 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) ⇒ Boolean

Checks if graph is connected

Returns:

  • (Boolean) 


243
244
245
246
247
248
249
250
251
 
# 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) ⇒ Boolean

Returns:

  • (Boolean) 


4
5
6
7
8
9
10
11
12
13
 
# 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) ⇒ Object 



28
29
30
31
32
33
 
# 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) ⇒ Object 



35
36
37
38
39
 
# 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) ⇒ Object

Passes graph’s vertices and marks them visited



267
268
269
270
 
# 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) ⇒ Object

Implements algorithm of Dijkstra



303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
 
# 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) ⇒ Boolean

Returns:

  • (Boolean)

Raises:

  • (ArgumentError) 


15
16
17
18
19
 
# 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) ⇒ Object

“Split” graph into elements like :[from, to] = label



283
284
285
286
287
288
289
 
# 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) ⇒ Object

Implements algorithm of Kruskal



23
24
25
26
27
28
29
30
31
32
33
 
# 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) ⇒ Object

Returns number of connected vertices



254
255
256
257
258
259
260
261
262
263
264
 
# 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) ⇒ Object 



291
292
293
294
295
296
297
 
# 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