Class: DirectedGraph

Inherits:
Object
  • Object
show all
Defined in:
lib/fsm-0.0.0/graph/directed_graph.rb

Direct Known Subclasses

BackLinkedDirectedGraph

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ DirectedGraph

Returns a new instance of DirectedGraph.



47
48
49
50
51
52
53
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 47

def initialize
  @link_map = HashOfHash.new {Array.new} # [from][to] -> array of links
  @link_map = Hash.new{|h,from| h[from] = Hash.new{|h2,to| h2[to] = []}}
  @links = Array.new # All links in one array
  @is_root = Hash.new # true iff root node
  @is_leaf = Hash.new # true iff leaf node
end

Instance Attribute Details

#is_leaf ⇒ Object (readonly)

Returns the value of attribute is_leaf.



45
46
47
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 45

def is_leaf
  @is_leaf
end

#is_root ⇒ Object (readonly)

Returns the value of attribute is_root.



44
45
46
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 44

def is_root
  @is_root
end

#link_map ⇒ Object (readonly)

Returns the value of attribute link_map.



43
44
45
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 43

def link_map
  @link_map
end

#links ⇒ Object (readonly)

This is a memory expensive variant that manages several additional information data structures to cut down on processing when the graph has been built.



42
43
44
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 42

def links
  @links
end

Instance Method Details

#acyclic? ⇒ Boolean

Returns:

  • (Boolean) 


189
190
191
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 189

def acyclic?
  not cyclic?
end

#add_link(from, to, informationOnLink = nil) ⇒ Object

(Forced) add link will always add link even if there are already links between the nodes.



91
92
93
94
95
96
97
98
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 91

def add_link(from, to, informationOnLink = nil)
  add_link_nodes(from, to)
  link = GraphLink.new(from, to, informationOnLink)
  links_from_to(from, to).push link
  #@link_map[from][to].push link
  add_to_links(link)
  link
end

#add_link_nodes(from, to) ⇒ Object 



100
101
102
103
104
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 100

def add_link_nodes(from, to)
  add_node(from)
  add_node(to)
  @is_leaf[from] = @is_root[to] = false
end

#add_node(node) ⇒ Object 



59
60
61
62
63
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 59

def add_node(node)
  unless include_node?(node)
    @is_root[node] = @is_leaf[node] = true
  end
end

#children(node) ⇒ Object 



85
86
87
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 85

def children(node)
  @link_map[node].keys.select {|k| @link_map[node][k].length > 0}
end

#cyclic? ⇒ Boolean

Returns:

  • (Boolean) 


183
184
185
186
187
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 183

def cyclic?
  visited = Hash.new
  root_nodes.each {|root| return true if recurse_cyclic?(root, visited)}
  false
end

#each_reachable_node_once_breadth_first(node, inclusive = true, &block) ⇒ Object 



139
140
141
142
143
144
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 139

def each_reachable_node_once_breadth_first(node, inclusive = true, &block)
  block.call(node) if inclusive
  children(node).each do |c|
    recurse_each_reachable_breadth_first_visited(c, Hash.new, &block)
  end
end

#each_reachable_node_once_depth_first(node, inclusive = true, &block) ⇒ Object Also known as: each_reachable_node 



121
122
123
124
125
126
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 121

def each_reachable_node_once_depth_first(node, inclusive = true, &block)
  children(node).each do |c|
    recurse_each_reachable_depth_first_visited(c, Hash.new, &block)
  end
  block.call(node) if inclusive
end

#include_node?(node) ⇒ Boolean

Returns:

  • (Boolean) 


73
74
75
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 73

def include_node?(node)
  @is_root.has_key?(node)
end

#internal_node?(node) ⇒ Boolean

Returns:

  • (Boolean) 


167
168
169
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 167

def internal_node?(node)
  !root?(node) and !leaf?(node) 
end

#internal_nodes ⇒ Object 



171
172
173
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 171

def internal_nodes
  nodes.reject {|n| root?(n) or leaf?(n)}
end

#leaf?(node) ⇒ Boolean

Returns:

  • (Boolean) 


69
70
71
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 69

def leaf?(node)
  @is_leaf[node]
end

#leaf_nodes ⇒ Object Also known as: leafs 



162
163
164
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 162

def leaf_nodes
  @is_leaf.reject {|key,val| val == false}.keys
end

#link_nodes(from, to, info = nil) ⇒ Object

Add link if not already linked



107
108
109
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 107

def link_nodes(from, to, info = nil)
  links_from_to?(from, to) ? nil : add_link(from, to, info)
end

#links_from(node) ⇒ Object 



81
82
83
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 81

def links_from(node)
  @link_map[node].map {|to, links| links}.flatten
end

#links_from_to(from, to) ⇒ Object 



77
78
79
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 77

def links_from_to(from, to)
  @link_map[from][to]
end

#links_from_to?(from, to) ⇒ Boolean Also known as: linked?

Returns:

  • (Boolean) 


111
112
113
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 111

def links_from_to?(from, to)
  not links_from_to(from, to).empty?
end

#nodes ⇒ Object 



55
56
57
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 55

def nodes
  @is_root.keys
end

#num_vertices ⇒ Object Also known as: num_nodes 



259
260
261
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 259

def num_vertices
  @is_root.size
end

#recurse_cyclic?(node, visited) ⇒ Boolean

Returns:

  • (Boolean) 


175
176
177
178
179
180
181
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 175

def recurse_cyclic?(node, visited)
  visited[node] = true
  children(node).each do |c|
    return true if visited[c] || recurse_cyclic?(c, visited)
  end
  false
end

#recurse_each_reachable_breadth_first_visited(node, visited, &block) ⇒ Object 



147
148
149
150
151
152
153
154
155
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 147

def recurse_each_reachable_breadth_first_visited(node, visited, &block)    
  visited[node] = true
  block.call(node)
  children(node).each do |c|
    unless visited[c]
	recurse_each_reachable_breadth_first_visited(c, visited, &block)
    end
  end
end

#recurse_each_reachable_depth_first_visited(node, visited, &block) ⇒ Object 



129
130
131
132
133
134
135
136
137
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 129

def recurse_each_reachable_depth_first_visited(node, visited, &block)    
  visited[node] = true
  children(node).each do |c|
    unless visited[c]
	recurse_each_reachable_depth_first_visited(c, visited, &block)
    end
  end
  block.call(node)
end

#recurse_strongly_connected_components(node, order_cell, order_hash, node_stack, components) ⇒ Object 



298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 298

def recurse_strongly_connected_components(node, order_cell, order_hash, node_stack, components)
  order = (order_cell[0] += 1)
  reachable_minimum_order = order
  order_hash[node] = order
  stack_length = node_stack.length
  node_stack << node

  links_from(node).each {|link|
    nextnode = link.to
    nextorder = order_hash[nextnode]
    if nextorder != -1
      if nextorder < reachable_minimum_order
        reachable_minimum_order = nextorder
      end
    else
      sub_minimum_order = recurse_strongly_connected_components(nextnode, order_cell, order_hash, node_stack, components)
      if sub_minimum_order < reachable_minimum_order
        reachable_minimum_order = sub_minimum_order
      end
    end
  }

  if order == reachable_minimum_order
    scc = node_stack[stack_length .. -1]
    node_stack[stack_length .. -1] = []
    components << scc
    scc.each {|n|
      order_hash[n] = num_vertices
    }
  end
  return reachable_minimum_order;
end

#root?(node) ⇒ Boolean

Returns:

  • (Boolean) 


65
66
67
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 65

def root?(node)
  @is_root[node]
end

#root_nodes ⇒ Object Also known as: roots 



157
158
159
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 157

def root_nodes
  @is_root.reject {|key,val| val == false}.keys
end

#strongly_connected_components ⇒ Object

strongly_connected_components uses the algorithm described in following paper. @Article 

author =       "R. E. Tarjan",
key =          "Tarjan",
title =        "Depth First Search and Linear Graph Algorithms",
journal =      "SIAM Journal on Computing",
volume =       "1",
number =       "2",
pages =        "146--160",
month =        jun,
year =         "1972",
CODEN =        "SMJCAT",
ISSN =         "0097-5397 (print), 1095-7111 (electronic)",
bibdate =      "Thu Jan 23 09:56:44 1997",
bibsource =    "Parallel/Multi.bib, Misc/Reverse.eng.bib",




281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 281

def strongly_connected_components
  order_cell = [0]
  order_hash = {}
  node_stack = []
  components = []

  order_hash.default = -1

  nodes.each {|node|
    if order_hash[node] == -1
      recurse_strongly_connected_components(node, order_cell, order_hash, node_stack, components)
    end
  }

  components
end

#to_dot(nodeShaper = nil, nodeLabeler = nil, linkLabeler = nil) ⇒ Object 



212
213
214
215
216
217
218
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 212

def to_dot(nodeShaper = nil, nodeLabeler = nil, linkLabeler = nil)
  dgp = DotGraphPrinter.new(links, nodes)
  dgp.node_shaper = nodeShaper if nodeShaper
  dgp.node_labeler = nodeLabeler if nodeLabeler
  dgp.link_labeler = linkLabeler if linkLabeler
  dgp
end

#to_postscript_file(filename, nodeShaper = nil, nodeLabeler = nil, linkLabeler = nil) ⇒ Object 



220
221
222
223
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 220

def to_postscript_file(filename, nodeShaper = nil, nodeLabeler = nil, 
	 linkLabeler = nil)
  to_dot(nodeShaper, nodeLabeler, linkLabeler).write_to_file(filename)
end

#transition(state, linkInfo) ⇒ Object 



193
194
195
196
197
198
199
200
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 193

def transition(state, linkInfo)
  link = links_from(state).detect {|l| l.info == linkInfo}
  begin
    link.to
  rescue Exception
    raise GraphTraversalException.new(state, links_from(state), linkInfo)
  end
end

#transitive_closure_floyd_warshal ⇒ Object Also known as: transitive_closure

Floyd-Warshal algorithm which should be O(n^3) where n is the number of nodes. We can probably work a bit on the constant factors!



227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 227

def transitive_closure_floyd_warshal
  vertices = nodes
  tcg = DirectedGraph.new
  num_nodes = vertices.length

  # Direct links
  for k in (0...num_nodes)
    for s in (0...num_nodes)
	vk, vs = vertices[k], vertices[s]	
	if vk == vs
 tcg.link_nodes(vk,vs)
	elsif linked?(vk, vs)
 tcg.link_nodes(vk,vs)
	end
    end
  end

  # Indirect links
  for i in (0...num_nodes)
    for j in (0...num_nodes)
	for k in (0...num_nodes)
 vi, vj, vk = vertices[i], vertices[j], vertices[k]
 if not tcg.linked?(vi,vj)
   tcg.link_nodes(vi, vj) if linked?(vi,vk) and linked?(vk,vj)
 end
	end
    end
  end
  tcg
end

#traverse(fromState, alongLinksWithInfo = []) ⇒ Object 



202
203
204
205
206
207
208
209
210
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 202

def traverse(fromState, alongLinksWithInfo = [])
  state, len = fromState, alongLinksWithInfo.length
  alongLinksWithInfo = alongLinksWithInfo.clone
  while len > 0
    state = transition(state, alongLinksWithInfo.shift)
    len -= 1
  end
  state
end