class PetriNet::Graph
Attributes
edges[R]
all edges of this graph
net[R]
The PetriNet
this graph belongs to
nodes[R]
all nodes from this graph
Public Class Methods
new(net, options = {})
click to toggle source
# File lib/petri_net/graph/graph.rb, line 18 def initialize(net, options = {}) @net = net @objects = [] @nodes = {} @edges = {} @name = net.name @type = 'Reachability' @unlimited = if options['unlimited'].nil? true else options['unlimited'] end end
Public Instance Methods
<<(object)
click to toggle source
Add an object to the Graph
.
# File lib/petri_net/graph/graph.rb, line 70 def <<(object) case object.class.to_s when 'Array' object.each { |o| self << o } when 'PetriNet::ReachabilityGraph::Edge' add_edge(object) when 'PetriNet::ReachabilityGraph::Node' add_node(object) else raise "(PetriNet::ReachabilityGraph) Unknown object #{object.class}." end self end
Also aliased as: add_object
add_edge(edge)
click to toggle source
# File lib/petri_net/graph/graph.rb, line 47 def add_edge(edge) if edge.validate && (!@edges.include? edge.name) @objects[edge.id] = edge @edges[edge.name] = edge.id edge.graph = self edge.source.outputs << edge.id edge.destination.inputs << edge.id return edge.id end false end
add_node(node)
click to toggle source
# File lib/petri_net/graph/graph.rb, line 32 def add_node(node) if node.validate && (!@objects.include? node) @objects[node.id] = node @nodes[node.name] = node.id node.graph = self return node.id end if @objects.include? node res = (@objects.index node) * -1 return res end false end
Also aliased as: add_node!
best_path(start, node)
click to toggle source
# File lib/petri_net/graph/graph.rb, line 219 def best_path(start, node) paths = get_paths_without_loops(start, node) prob = 0 res_path = nil paths.each do |path| if (path_probability path) >= prob prob = (path_probability path) res_path = path end end [res_path, prob] end
cycles()
click to toggle source
# File lib/petri_net/graph/graph.rb, line 188 def cycles get_rgl.cycles end
generate_gv(named = true)
click to toggle source
# File lib/petri_net/graph/graph.rb, line 118 def generate_gv(named = true) g = GraphViz.new(:G, type: :digraph) @nodes.each_value do |node| label = if named (@net.get_place_from_marking @objects[node].markings).to_s else @objects[node].markings.to_s end gv_node = g.add_nodes(label) gv_node.set do |n| n.label = '*' + label + '*' if @objects[node].start end end @edges.each_value do |edge| label1 = if named (@net.get_place_from_marking @objects[edge].source.markings).to_s else @objects[edge].source.markings.to_s end label2 = if named (@net.get_place_from_marking @objects[edge].destination.markings).to_s else @objects[edge].destination.markings.to_s end gv_edge = g.add_edges(label1, label2) gv_edge.set do |e| e.label = @objects[edge].transition end end @gv = g end
generate_rgl()
click to toggle source
# File lib/petri_net/graph/graph.rb, line 152 def generate_rgl g = RGL::DirectedAdjacencyGraph.new @nodes.each_value do |node| g.add_vertex @objects[node].markings.to_s end @edges.each_value do |edge| g.add_edge @objects[edge].source.markings.to_s, @objects[edge].destination.markings.to_s end @rgl = g end
get_edge(source, dest)
click to toggle source
# File lib/petri_net/graph/graph.rb, line 59 def get_edge(source, dest) res = nil @edges.each_value do |edge| if @objects[edge].source == source && @objects[edge].destination == dest res = @objects[edge] end end res end
get_most_absolute_influence_on_path(start, node, sum = 0.01)
click to toggle source
# File lib/petri_net/graph/graph.rb, line 268 def get_most_absolute_influence_on_path(start, node, sum = 0.01) prob_counter = 0 prob_diff = [] paths = get_paths_without_loops(start, node) paths.each do |path| counter = 0 path.each do |curr_node| prob_before = node_probability start, node next if node == path[-1] edge = get_edge(path[counter + 1], curr_node) save = edge.probability unless edge.nil? edge.probability = edge.probability + sum unless edge.nil? edge.probability = 1 if !edge.nil? && edge.probability > 1 prob_after = node_probability start, node unless edge.nil? edge.probability = save unless edge.nil? prob_diff[prob_counter] = [prob_after - prob_before, [curr_node, path[counter + 1]]] unless edge.nil? prob_counter += 1 unless edge.nil? counter += 1 end end prob_diff.max { |x, y| x[0] <=> y[0] } end
get_most_relative_influence_on_path(start, node, factor = 0.5)
click to toggle source
# File lib/petri_net/graph/graph.rb, line 245 def get_most_relative_influence_on_path(start, node, factor = 0.5) prob_counter = 0 prob_diff = [] paths = get_paths_without_loops(start, node) paths.each do |path| counter = 0 path.each do |curr_node| prob_before = node_probability start, node next if node == path[-1] edge = get_edge(path[counter + 1], curr_node) save = edge.probability unless edge.nil? edge.probability += (1 - edge.probability) * factor unless edge.nil? prob_after = node_probability start, node unless edge.nil? edge.probability = save unless edge.nil? prob_diff[prob_counter] = [prob_after - prob_before, [curr_node, path[counter + 1]]] unless edge.nil? prob_counter += 1 unless edge.nil? counter += 1 end end prob_diff.max { |x, y| x[0] <=> y[0] } end
get_node(node)
click to toggle source
# File lib/petri_net/graph/graph.rb, line 85 def get_node(node) return @objects[node] if node.class.to_s == 'Fixnum' if node.class.to_s == 'Array' return @objects.select { |o| o.class.to_s == 'PetriNet::ReachabilityGraph::Node' && o.markings == node }.first end end
get_nodes()
click to toggle source
# File lib/petri_net/graph/graph.rb, line 96 def get_nodes res = [] @nodes.each_value do |n| res << @objects[n] end res end
get_object(id)
click to toggle source
# File lib/petri_net/graph/graph.rb, line 92 def get_object(id) @objects[id] end
get_paths_without_loops(start, goal)
click to toggle source
# File lib/petri_net/graph/graph.rb, line 292 def get_paths_without_loops(start, goal) get_paths_without_loops_helper(get_node(start), get_node(goal)) end
get_rgl()
click to toggle source
# File lib/petri_net/graph/graph.rb, line 183 def get_rgl generate_rgl if @rgl.nil? @rgl end
infinite?()
click to toggle source
# File lib/petri_net/graph/graph.rb, line 104 def infinite? @nodes.each_value do |node| return true if @objects[node].infinite? end false end
node_probability(start, node)
click to toggle source
# File lib/petri_net/graph/graph.rb, line 210 def node_probability(start, node) paths = get_paths_without_loops(start, node) prob = 0 paths.each do |path| prob += (path_probability path) end prob end
path_probability(path)
click to toggle source
# File lib/petri_net/graph/graph.rb, line 198 def path_probability(path) sanitize_probabilities prob = 1 counter = 0 path.each do |node| edge = get_edge(path[counter + 1], node) prob *= edge.probability unless edge.nil? # last node has no pre-edge counter = counter += 1 end prob end
sanitize_probabilities()
click to toggle source
# File lib/petri_net/graph/graph.rb, line 296 def sanitize_probabilities @nodes.each_value do |node| prob = 1.0 @objects[node].outputs.each do |edge| prob += @objects[edge].probability unless @objects[edge].probability.nil? end @objects[node].outputs.each do |edge| @objects[edge].probability = prob / @objects[node].outputs.size if @objects[edge].probability.nil? end end end
shortest_path(start, destination)
click to toggle source
# File lib/petri_net/graph/graph.rb, line 192 def shortest_path(start, destination) g = get_rgl weights = ->(_edge) { 1 } g.dijkstra_shortest_path(weights, start.to_s, destination.to_s) end
to_gv(output = 'png', filename = '')
click to toggle source
# File lib/petri_net/graph/graph.rb, line 111 def to_gv(output = 'png', filename = '') g = generate_gv filename = "#{@name}_graph.png" if filename.empty? g.output(png: filename) if output == 'png' g.output end
to_s()
click to toggle source
# File lib/petri_net/graph/graph.rb, line 163 def to_s str = "#{@type} Graph [#{@name}]\n" str += "----------------------------\n" str += "Description: #{@description}\n" str += "Filename: #{@filename}\n" str += "\n" str += "Nodes\n" str += "----------------------------\n" @nodes.each_value { |p| str += @objects[p].to_s + "\n" } str += "\n" str += "Edges\n" str += "----------------------------\n" @edges.each_value { |t| str += @objects[t].to_s + "\n" } str += "\n" str end
worst_path(start, node)
click to toggle source
# File lib/petri_net/graph/graph.rb, line 232 def worst_path(start, node) paths = get_paths_without_loops(start, node) prob = 1 res_path = nil paths.each do |path| if (path_probability path) <= prob prob = (path_probability path) res_path = path end end [res_path, prob] end
Private Instance Methods
get_paths_without_loops_helper(start, goal, reverse_paths = [], reverse_path = [])
click to toggle source
# File lib/petri_net/graph/graph.rb, line 310 def get_paths_without_loops_helper(start, goal, reverse_paths = [], reverse_path = []) if goal == start reverse_path << goal reverse_paths << reverse_path return nil end return nil if reverse_path.include? goal path = [] goal.inputs.each do |input| get_paths_without_loops_helper(start, @objects[input].source, reverse_paths, reverse_path.clone << goal) end reverse_paths end