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 = Hash.new)
click to toggle source
# File lib/petri_net/graph/graph.rb, line 17 def initialize(net, options = Hash.new) @net = net @objects = Array.new @nodes = Hash.new @edges = Hash.new @name = net.name @type = "Reachability" if options['unlimited'].nil? @unlimited = true else @unlimited = 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 69 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 46 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 return false end
add_node(node)
click to toggle source
# File lib/petri_net/graph/graph.rb, line 31 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 return false end
Also aliased as: add_node!
best_path(start, node)
click to toggle source
# File lib/petri_net/graph/graph.rb, line 209 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 177 def cycles get_rgl.cycles end
generate_gv()
click to toggle source
# File lib/petri_net/graph/graph.rb, line 121 def generate_gv g = GraphViz.new( :G, :type => :digraph ) @nodes.each_value do |node| gv_node = g.add_nodes( @objects[node].markings.to_s ) gv_node.set do |n| n.label = '*' + @objects[node].markings.to_s + '*' if @objects[node].start end end @edges.each_value do |edge| gv_edge = g.add_edges( @objects[edge].source.markings.to_s, @objects[edge].destination.markings.to_s ) 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 139 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 58 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_node(node)
click to toggle source
# File lib/petri_net/graph/graph.rb, line 84 def get_node(node) if node.class.to_s == "Fixnum" return @objects[node] end 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 97 def get_nodes res = Array.new @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 93 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 235 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 170 def get_rgl if @rgl.nil? generate_rgl end @rgl end
infinite?()
click to toggle source
# File lib/petri_net/graph/graph.rb, line 105 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 200 def node_probability(start, node) paths = get_paths_without_loops(start, node) prob = 0 paths.each do |path| prob = prob + (path_probability path) end prob end
path_probability(path)
click to toggle source
# File lib/petri_net/graph/graph.rb, line 188 def path_probability(path) sanitize_probabilities prob = 1 counter = 0 path.each do |node| edge = get_edge(path[counter+1], node) prob = 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 239 def sanitize_probabilities @nodes.each_value do |node| prob = 1.0 @objects[node].outputs.each do |edge| prob = 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 181 def shortest_path(start, destination) g = get_rgl weights = lambda { |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 112 def to_gv(output = 'png', filename = '') g = generate_gv if filename.empty? filename = "#{@name}_graph.png" end g.output( :png => filename ) if output == 'png' g.output end
to_s()
click to toggle source
# File lib/petri_net/graph/graph.rb, line 150 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" return str end
worst_path(start, node)
click to toggle source
# File lib/petri_net/graph/graph.rb, line 222 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 = Array.new, reverse_path = Array.new)
click to toggle source
# File lib/petri_net/graph/graph.rb, line 253 def get_paths_without_loops_helper(start, goal, reverse_paths = Array.new, reverse_path = Array.new) if goal == start reverse_path << goal reverse_paths << reverse_path return nil end if reverse_path.include? goal return nil end path = Array.new goal.inputs.each do |input| get_paths_without_loops_helper(start, @objects[input].source, reverse_paths, reverse_path.clone << goal) end reverse_paths end