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!
add_node!(node)
Alias for: add_node
add_object(object)
Alias for: <<
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