Class: PetriNet::Graph

Inherits:
Base
  • Object
show all
Defined in:
lib/petri_net/graph.rb,
lib/petri_net/graph/graph.rb

Direct Known Subclasses

ReachabilityGraph

Defined Under Namespace

Classes: Edge, Node

Instance Attribute Summary collapse

Attributes inherited from Base

#logger

Instance Method Summary collapse

Methods inherited from Base

#next_object_id, #reset

Constructor Details

#initialize(net, options = Hash.new) ⇒ Graph

Returns a new instance of Graph.



17
18
19
20
21
22
23
24
25
26
27
28
29
 
# 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

Instance Attribute Details

#edges ⇒ Object (readonly)

all edges of this graph



15
16
17
 
# File 'lib/petri_net/graph/graph.rb', line 15

def edges
  @edges
end

#net ⇒ Object (readonly)

The PetriNet this graph belongs to



11
12
13
 
# File 'lib/petri_net/graph/graph.rb', line 11

def net
  @net
end

#nodes ⇒ Object (readonly)

all nodes from this graph



13
14
15
 
# File 'lib/petri_net/graph/graph.rb', line 13

def nodes
  @nodes
end

Instance Method Details

#<<(object) ⇒ Object Also known as: add_object

Add an object to the Graph.



69
70
71
72
73
74
75
76
77
78
79
80
81
 
# 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

#add_edge(edge) ⇒ Object 



46
47
48
49
50
51
52
53
54
55
56
 
# 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) ⇒ Object Also known as: add_node! 



31
32
33
34
35
36
37
38
39
40
41
42
43
 
# 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

#best_path(start, node) ⇒ Object 



209
210
211
212
213
214
215
216
217
218
219
220
 
# 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 ⇒ Object 



177
178
179
 
# File 'lib/petri_net/graph/graph.rb', line 177

def cycles
    get_rgl.cycles
end

#generate_gv ⇒ Object 



121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
 
# 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 ⇒ Object 



139
140
141
142
143
144
145
146
147
148
 
# 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) ⇒ Object 



58
59
60
61
62
63
64
65
66
 
# 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) ⇒ Object 



84
85
86
87
88
89
90
91
 
# 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 ⇒ Object 



97
98
99
100
101
102
103
 
# 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) ⇒ Object 



93
94
95
 
# File 'lib/petri_net/graph/graph.rb', line 93

def get_object(id)
    @objects[id]
end

#get_paths_without_loops(start, goal) ⇒ Object 



235
236
237
 
# 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 ⇒ Object 



170
171
172
173
174
175
 
# File 'lib/petri_net/graph/graph.rb', line 170

def get_rgl
    if @rgl.nil?
        generate_rgl
    end
    @rgl
end

#infinite? ⇒ Boolean

Returns:

  • (Boolean) 


105
106
107
108
109
110
 
# 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) ⇒ Object 



200
201
202
203
204
205
206
207
 
# 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) ⇒ Object 



188
189
190
191
192
193
194
195
196
197
198
 
# 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 ⇒ Object 



239
240
241
242
243
244
245
246
247
248
249
 
# 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) ⇒ Object 



181
182
183
184
185
 
# 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 = '') ⇒ Object 



112
113
114
115
116
117
118
119
 
# 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 ⇒ Object 



150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
 
# 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) ⇒ Object 



222
223
224
225
226
227
228
229
230
231
232
233
 
# 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