# A Directed Multigraph. API: # @g = Graph.new; a = "a"; r = "="; b = "b"; c = "c" # @g.a_r_b!(a, r, b); @g.a_r_b(a, r, c) # @g.a_r_b?(a, r, c) => true # @g.a_r_?(a, r) => ["b", "c"] ## @g.what_r_b?(r, b) => ["a"] # @g.shortest_path(a, r, c) => ["a = b", "b = c"] # @g.remove_edge(b, r, c) # @g.save; @g2 = Graph.new # @g2.load; @g2.a_r_b?(a, r, c) => false # @g2.a_r_b?(a, r, b) => true require 'yaml' $filename = File.expand_path(File.dirname(__FILE__)) + "/graph.yaml" class Graph attr_accessor :vertex_hash def initialize(_load = true) @vertex_hash = Hash.new if _load then load_message = load end puts load_message unless load_message == nil or load_message =~ /^Error/ or load_message =~ /not found./ end # is a related to b? Returns true if yes, false if no. def a_r_b?(a, r, b, visited = Array.new) if r.class == String r = [r] end ar = @vertex_hash.fetch(a, Array.new) ar.each { |edge| label = edge.fetch("label", nil) if label == nil then next end if label =~ %r{#{"("}#{r.join('|')}#{")"}} source = edge.fetch("source", nil) if source == nil then next end visited.push(source) target = edge.fetch("target", nil) if target == nil then next end if target == b return true end if visited.include?(target) then next end if a_r_b?(target, r, b, visited) return true end end } return false end # a is related to b def a_r_b!(a, r, b) edge = { "source" => a, "label" => r, "target" => b } edges = @vertex_hash.fetch(a, Array.new) edges.push(edge) unless edges.include?(edge) @vertex_hash.store(a, edges) edges2 = @vertex_hash.fetch(b, Array.new) @vertex_hash.store(b, edges2) return true end alias a_r_b a_r_b! # Returns an array containing the adjacent vertices of a, the adjacent # vertices of each of these adjacent vertices, etc. # # "adjacent vertices" means those vertices connected to a through an edge # with the same relation (or label) as the relation supplied as a parameter. # # In other words, returns an array of all the vertices in the graph # that are adjacent to a, and the vertices that are related to a by # transitivity. # # So if a = b and b = c, a_r_?(a, "=") returns [b, c]. def a_r_?(a, r, visited = Array.new, acc = Array.new) if r.class == String r = [ r ] end ar = @vertex_hash.fetch(a, Array.new) #--- Look for /a/ in keys #if false # disable looking for /a/ in keys #puts "1.[graph.a_r_?] ar==#{ar.inspect}" ar2 = Array.new if ar.empty? ar = @vertex_hash.fetch(a) { |el| @vertex_hash.each_key { |key| #puts "[graph.a_r_?] key==#{key}; el==#{el}" if el =~ /\?$/ then el.sub!(/\?$/, '') end # delete final '?' if key =~ /#{el}/ then ar2.push(key) end } if ar2.empty? then ar = Array.new end } end if not ar2.empty? ar = Array.new ar2.each { |el| ar.concat(@vertex_hash.fetch(el, Array.new)) } end #puts "2. [graph.a_r_?] ar==#{ar.inspect}" #end # disable looking for /a/ in keys #--- ar.each { |edge| label = edge.fetch("label", nil) if label == nil then next end if label =~ %r{#{"("}#{r.join('|')}#{")"}} #puts "label==#{label}" source = edge.fetch("source", nil) if source == nil then next end visited.push(source) target = edge.fetch("target", nil) if target == nil then next end if source == target then acc.push(target); next end if visited.include?(target) then next end acc.push(target) arr = a_r_?(target, r, visited, acc) arr.each { |t| if visited.include?(t) then next end acc.push(t) visited.push(t) } end } return acc.uniq end def what_r_b?(r, b, visited = Array.new, acc = Array.new) if r.class == String r = [ r ] end b_array = self.a_r_?(b, "is") b_array.push(b) @vertex_hash.each_key { |key| ar = vertex_hash.fetch(key, Array.new) ar.each { |edge| label = edge.fetch("label", nil) if label == nil then next end if label =~ %r{#{"("}#{r.join('|')}#{")"}} #puts "label==#{label}" target = edge.fetch("target", nil) if target == nil then next end found = false b_array.each {|elem| if target == elem then found = true; break; end } if not found then next end #if target != b then next end source = edge.fetch("source", nil) if source == nil then next end if source == target then acc.push(target); next end acc.push(source) end } } return acc.uniq end alias what_r_b what_r_b? # Returns an array. The elements of the array are "vertex relation vertex", # along the shortest path from a to b. # For example: @g = Graph.new # @g.a_r_b!("a", "is", "b"); @g.a_r_b!("b", "is", "c") # @g.shortest_path("a", "is", "c") => ["a is b", "b is c"] def shortest_path(a, r, b) if r.class == String if a == b return ["#{a} #{r} #{b}"] end r = [r] end arr = dijkstras_algorithm(a, r) #puts "#{arr.inspect}" # arr is an array of two hashes: # [{"a"=>0, "b"=>1, "c"=>2}, {"b"=>["a", "is"], "c"=>["b", "is"]}] h = arr[0] return [] unless h.include? b # is there a path between a and b? h2 = arr[1] b_arr = h2[b] # get the array of the vertex and edge label connected to b v = b_arr[0] # get the vertex from the array label = b_arr[1] to_return = Array.new to_return << "#{v} #{label} #{b}" loopcount = 0 # for safety while v != a do loopcount += 1; return "Loopcount exceeded!" unless loopcount < 1000 aa = h2[v] ss = aa[0] ll = aa[1] x = ss to_return << "#{x} #{ll} #{v}" v = x end return to_return.reverse end # Based on Shawn Patrick Garbett's gratr library: # # Finds the distances from a given vertex s in a weighted digraph # to the rest of the vertices, provided all the weights of arcs # are non-negative. # # Returns an array. The first element is a hash with a key being # a vertex and the value being the distance. A missing vertex from the hash # is an infinite distance. # # The second element of the returned array is a hash containing all the # paths leading from the supplied vertex parameter (s). # # O(n*log(n) + m) complexity def dijkstras_algorithm(s, r = "is") if r.class == String r = [r] end q = @vertex_hash.keys distance = { s => 0 }; path = {} while not q.empty? v = (q & distance.keys).inject(nil) {|a,k| (!a.nil?) && (distance[a] < distance[k]) ? a : k } if v == nil then break end q.delete(v) adjArray = adjacent(v,r) adjVerticesArray = Array.new labelArray = Array.new adjArray.each { |array| adjVerticesArray << array[0] labelArray << array[1] } count = 0 (q & adjVerticesArray).each do |u| label = labelArray[count] count += 1 #c = cost(v,u,weight) c = 1 # default weight if distance[u].nil? or distance[u] > (c+distance[v]) distance[u] = c + distance[v] path[u] = [v,label] end end end [distance, path] end # Returns an array of the edges labeled r that are adjacent to a. def adjacent(a, r = "is") if r.class == String r = [r] end edges = @vertex_hash.fetch(a, Array.new) if edges.empty? then return [] end arr = Array.new edges.each { |edge| target = edge.fetch("target", nil) if target == nil then next end label = edge.fetch("label", nil) if label == nil then next end #if label == r then arr << target end if label =~ %r{#{"("}#{r.join('|')}#{")"}} arr << [target, label] end } #puts "graph.rb, adjacent: arr==#{arr.inspect}" arr end # Removes the edge a is b. def remove_edge(a, r, b) e = { "source" => a, "label" => r, "target" => b } @vertex_hash.each_pair { |key, edges| edge_to_delete = {} edges.each { |edge| if e == edge edge_to_delete = edge # can we modify the array while enumerating it? end } if edge_to_delete.empty? then next end edges.delete(edge_to_delete) { Array.new } @vertex_hash[key] = edges } return true end alias remove_edge! remove_edge def to_s #return @vertex_hash.inspect r = "" @vertex_hash.each_pair { |vertex, edges| edges.each { |h| r << h.fetch("source", "") << " " r << h.fetch("label", "") << " " r << h.fetch("target", "") << "\n" } } r end # Save the graph. def save(file = $filename) if file == nil or file.empty? then file = $filename end begin File.open(file, "w") { |f| YAML.dump(@vertex_hash, f) } return "#{file} saved." rescue => error return "Error saving #{file}: #{error}" end end # Load the graph from a saved file. def load(file = $filename) if file == nil or file.empty? then file = $filename end begin if File.exist?(file) @vertex_hash = YAML.load_file(file) return "#{file} loaded." end return "#{file} not found." rescue => error return "Error loading #{file}: #{error}" end end end # class