Class: Graph

Inherits:
Object
  • Object
show all
Defined in:
lib/graphify/graph.rb

Instance Method Summary collapse

Constructor Details

#initialize(args) ⇒ Graph

Returns a new instance of Graph.



6
7
8
9
10
11
12
13
14
15
 
# File 'lib/graphify/graph.rb', line 6

def initialize(args)
  @graph =  if args[:storage_type] == 'matrix'
              GraphMatrix.new(args)
            elsif args[:storage_type] == 'list'
              GraphList.new(args)
            end
  @type = args[:type] == 'directed' ? :digraph : :graph
  @name = args[:name]
  @storage_type = args[:storage_type]
end

Instance Method Details

#dfs_tree(vertex) ⇒ Object 



24
25
26
27
28
 
# File 'lib/graphify/graph.rb', line 24

def dfs_tree(vertex)
  g = initialize_g
  dfs_helper(vertex, [], g)
  g
end

#dfs_tree_picture(vertex) ⇒ Object 



34
35
36
37
38
39
40
41
 
# File 'lib/graphify/graph.rb', line 34

def dfs_tree_picture(vertex)
  tree = dfs_tree(vertex)
  if @storage_type == 'matrix'
    produce_picture_from_matrix(tree, '_dfs_tree.png')
  elsif @storage_type == 'list'
    produce_picture_from_list(tree, '_dfs_tree.png')
  end
end

#edges ⇒ Object 



30
31
32
 
# File 'lib/graphify/graph.rb', line 30

def edges
  @graph.edges_with_weights
end

#mst_edges ⇒ Object 



85
86
87
 
# File 'lib/graphify/graph.rb', line 85

def mst_edges
  kruskals_edges
end

#mst_picture ⇒ Object 



78
79
80
81
82
83
 
# File 'lib/graphify/graph.rb', line 78

def mst_picture
  g = GraphViz.new(:G, type: @type)
  picture_vertices = add_vertices_to_picture(g)
  add_mst_edges(picture_vertices, g)
  g.output(png: @name + '_minimum_spanning_tree.png')
end

#picture ⇒ Object 



17
18
19
20
21
22
 
# File 'lib/graphify/graph.rb', line 17

def picture
  g = GraphViz.new(:G, type: @type)
  vertices = add_vertices_to_picture(g)
  add_edges_to_picture(vertices, g)
  g.output(png: @name + '.png')
end

#scc_edge_set ⇒ Object 



63
64
65
 
# File 'lib/graphify/graph.rb', line 63

def scc_edge_set
  construct_scc_edges(scc_vertex_sets)
end

#scc_picture ⇒ Object 



67
68
69
70
71
72
 
# File 'lib/graphify/graph.rb', line 67

def scc_picture
  g = GraphViz.new(:G, type: @type)
  picture_vertices = add_scc_vertices(scc_vertex_sets, g)
  add_scc_edges(picture_vertices, scc_edge_set, g)
  g.output(png: @name + '_strongly_connected_components.png')
end

#scc_vertex_sets ⇒ Object 



59
60
61
 
# File 'lib/graphify/graph.rb', line 59

def scc_vertex_sets
  scc_vertex_sets_helper
end

#shortest_path_tree(vertex) ⇒ Object 



43
44
45
46
47
48
 
# File 'lib/graphify/graph.rb', line 43

def shortest_path_tree(vertex)
  g = initialize_g
  distances, predecessors = initialize_djikstras(vertex)
  djikstras_helper(vertex, [], distances, predecessors, g)
  g
end

#shortest_path_tree_picture(vertex) ⇒ Object 



50
51
52
53
54
55
56
57
 
# File 'lib/graphify/graph.rb', line 50

def shortest_path_tree_picture(vertex)
  tree = shortest_path_tree(vertex)
  if @storage_type == 'matrix'
    produce_picture_from_matrix(tree, '_shortest_path_tree.png')
  elsif @storage_type == 'list'
    produce_picture_from_list(tree, '_shortest_path_tree.png')
  end
end

#topological_sort ⇒ Object 



74
75
76
 
# File 'lib/graphify/graph.rb', line 74

def topological_sort
  scc_total_ordering
end