Class: DirectedGraph

Inherits:
Object
  • Object
show all
Defined in:
lib/graphr/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.



41
42
43
44
45
46
 
# File 'lib/graphr/directed_graph.rb', line 41

def initialize
  @link_map = HashOfHash.new {Array.new} # [from][to] -> array of links
  @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

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



39
40
41
 
# File 'lib/graphr/directed_graph.rb', line 39

def links
  @links
end

Instance Method Details

#acyclic? ⇒ Boolean

Returns:

  • (Boolean) 


181
182
183
 
# File 'lib/graphr/directed_graph.rb', line 181

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.



84
85
86
87
88
89
90
 
# File 'lib/graphr/directed_graph.rb', line 84

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
  add_to_links(link)
  link
end

#add_link_nodes(from, to) ⇒ Object 



92
93
94
95
96
 
# File 'lib/graphr/directed_graph.rb', line 92

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

#add_node(node) ⇒ Object 



52
53
54
55
56
 
# File 'lib/graphr/directed_graph.rb', line 52

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

#children(node) ⇒ Object 



78
79
80
 
# File 'lib/graphr/directed_graph.rb', line 78

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

#cyclic? ⇒ Boolean

Returns:

  • (Boolean) 


175
176
177
178
179
 
# File 'lib/graphr/directed_graph.rb', line 175

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 



131
132
133
134
135
136
 
# File 'lib/graphr/directed_graph.rb', line 131

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 



113
114
115
116
117
118
 
# File 'lib/graphr/directed_graph.rb', line 113

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) 


66
67
68
 
# File 'lib/graphr/directed_graph.rb', line 66

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

#internal_node?(node) ⇒ Boolean

Returns:

  • (Boolean) 


159
160
161
 
# File 'lib/graphr/directed_graph.rb', line 159

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

#internal_nodes ⇒ Object 



163
164
165
 
# File 'lib/graphr/directed_graph.rb', line 163

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

#leaf?(node) ⇒ Boolean

Returns:

  • (Boolean) 


62
63
64
 
# File 'lib/graphr/directed_graph.rb', line 62

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

#leaf_nodes ⇒ Object Also known as: leafs 



154
155
156
 
# File 'lib/graphr/directed_graph.rb', line 154

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



99
100
101
 
# File 'lib/graphr/directed_graph.rb', line 99

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

#links_from(node) ⇒ Object 



74
75
76
 
# File 'lib/graphr/directed_graph.rb', line 74

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

#links_from_to(from, to) ⇒ Object 



70
71
72
 
# File 'lib/graphr/directed_graph.rb', line 70

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

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

Returns:

  • (Boolean) 


103
104
105
 
# File 'lib/graphr/directed_graph.rb', line 103

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

#nodes ⇒ Object 



48
49
50
 
# File 'lib/graphr/directed_graph.rb', line 48

def nodes
  @is_root.keys
end

#num_vertices ⇒ Object Also known as: num_nodes 



251
252
253
 
# File 'lib/graphr/directed_graph.rb', line 251

def num_vertices
  @is_root.size
end

#recurse_cyclic?(node, visited) ⇒ Boolean

Returns:

  • (Boolean) 


167
168
169
170
171
172
173
 
# File 'lib/graphr/directed_graph.rb', line 167

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 



139
140
141
142
143
144
145
146
147
 
# File 'lib/graphr/directed_graph.rb', line 139

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 



121
122
123
124
125
126
127
128
129
 
# File 'lib/graphr/directed_graph.rb', line 121

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 



290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
 
# File 'lib/graphr/directed_graph.rb', line 290

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) 


58
59
60
 
# File 'lib/graphr/directed_graph.rb', line 58

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

#root_nodes ⇒ Object Also known as: roots 



149
150
151
 
# File 'lib/graphr/directed_graph.rb', line 149

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",




273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
 
# File 'lib/graphr/directed_graph.rb', line 273

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 



204
205
206
207
208
209
210
 
# File 'lib/graphr/directed_graph.rb', line 204

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 



212
213
214
215
 
# File 'lib/graphr/directed_graph.rb', line 212

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 



185
186
187
188
189
190
191
192
 
# File 'lib/graphr/directed_graph.rb', line 185

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!



219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
 
# File 'lib/graphr/directed_graph.rb', line 219

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 



194
195
196
197
198
199
200
201
202
 
# File 'lib/graphr/directed_graph.rb', line 194

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