class Graphunk::DirectedGraph
Public Instance Methods
add_edge(first_vertex, second_vertex)
click to toggle source
# File lib/graphunk/directed_graph.rb, line 3 def add_edge(first_vertex, second_vertex) if edge_exists?(first_vertex, second_vertex) raise ArgumentError, "This edge already exists" elsif vertex_exists?(first_vertex) && vertex_exists?(second_vertex) @representation[first_vertex] << second_vertex else raise ArgumentError, "One of the vertices referenced does not exist in the graph" end end
dfs()
click to toggle source
# File lib/graphunk/directed_graph.rb, line 79 def dfs discovered = [] time = 0 output = {} vertices.each { |vertex| output[vertex] = {} } dfs_helper = lambda do |u| #only u can do u, so do it! discovered << u time += 1 output[u][:start] = time neighbors_of_vertex(u).each do |neighbor| dfs_helper.call neighbor unless discovered.include?(neighbor) end time += 1 output[u][:finish] = time end vertices.each do |vertex| dfs_helper.call vertex unless discovered.include?(vertex) end output end
edge_exists?(first_vertex, second_vertex)
click to toggle source
# File lib/graphunk/directed_graph.rb, line 29 def edge_exists?(first_vertex, second_vertex) edges.include?([first_vertex, second_vertex]) end
neighbors_of_vertex(name)
click to toggle source
# File lib/graphunk/directed_graph.rb, line 21 def neighbors_of_vertex(name) if vertex_exists?(name) @representation[name] else raise ArgumentError, "That vertex does not exist in the graph" end end
reachable_by_two_path(start)
click to toggle source
# File lib/graphunk/directed_graph.rb, line 55 def reachable_by_two_path(start) if vertex_exists?(start) reached_vertices = @representation[start] reached_vertices.each do |vertex| reached_vertices += @representation[vertex] end reached_vertices.uniq else raise ArgumentError, "That vertex does not exist in the graph" end end
remove_edge(first_vertex, second_vertex)
click to toggle source
# File lib/graphunk/directed_graph.rb, line 13 def remove_edge(first_vertex, second_vertex) if edge_exists?(first_vertex, second_vertex) @representation[first_vertex].delete(second_vertex) else raise ArgumentError, "That edge does not exist in the graph" end end
square()
click to toggle source
# File lib/graphunk/directed_graph.rb, line 67 def square graph = self.clone vertices.each do |vertex| (reachable_by_two_path(vertex) - [vertex]).each do |reachable| graph.add_edge(vertex, reachable) unless edge_exists?(vertex, reachable) end end graph end
topological_sort()
click to toggle source
# File lib/graphunk/directed_graph.rb, line 105 def topological_sort dfs.sort_by { |vertex, times| times[:finish] }.map(&:first).reverse end
transitive?()
click to toggle source
# File lib/graphunk/directed_graph.rb, line 109 def transitive? transitive = true vertices.each do |vertex| reachable_by_two_edges(vertex).each do |reachable| transitive = false unless neighbors_of_vertex(vertex).include?(reachable) end end transitive end
transpose()
click to toggle source
# File lib/graphunk/directed_graph.rb, line 33 def transpose graph = DirectedGraph.new vertices.each do |vertex| graph.add_vertex(vertex) end edges.each do |edge| graph.add_edge(edge.last, edge.first) end graph end
transpose!()
click to toggle source
# File lib/graphunk/directed_graph.rb, line 44 def transpose! reversed_edges = [] edges.each do |edge| remove_edge(edge.first, edge.last) reversed_edges << [edge.last, edge.first] end reversed_edges.each do |edge| add_edge(edge.first, edge.last) end end
Private Instance Methods
reachable_by_two_edges(start)
click to toggle source
# File lib/graphunk/directed_graph.rb, line 121 def reachable_by_two_edges(start) reachable_by_two = [] reachable_by_one = neighbors_of_vertex(start) reachable_by_one.each do |v| neighbors_of_vertex(v).each do |u| reachable_by_two << u end end reachable_by_two end