Class: DirectedGraph

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



44
45
46
47
48
49
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 44

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.



42
43
44
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 42

def links
  @links
end

Instance Method Details

#acyclic? ⇒ Boolean

Returns:

  • (Boolean) 


184
185
186
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 184

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.



87
88
89
90
91
92
93
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 87

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 



95
96
97
98
99
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 95

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

#add_node(node) ⇒ Object 



55
56
57
58
59
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 55

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

#children(node) ⇒ Object 



81
82
83
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 81

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

#cyclic? ⇒ Boolean

Returns:

  • (Boolean) 


178
179
180
181
182
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 178

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 



134
135
136
137
138
139
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 134

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 



116
117
118
119
120
121
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 116

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) 


69
70
71
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 69

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

#internal_node?(node) ⇒ Boolean

Returns:

  • (Boolean) 


162
163
164
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 162

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

#internal_nodes ⇒ Object 



166
167
168
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 166

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

#leaf?(node) ⇒ Boolean

Returns:

  • (Boolean) 


65
66
67
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 65

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

#leaf_nodes ⇒ Object Also known as: leafs 



157
158
159
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 157

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



102
103
104
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 102

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

#links_from(node) ⇒ Object 



77
78
79
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 77

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

#links_from_to(from, to) ⇒ Object 



73
74
75
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 73

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

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

Returns:

  • (Boolean) 


106
107
108
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 106

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

#nodes ⇒ Object 



51
52
53
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 51

def nodes
  @is_root.keys
end

#recurse_cyclic?(node, visited) ⇒ Boolean

Returns:

  • (Boolean) 


170
171
172
173
174
175
176
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 170

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 



142
143
144
145
146
147
148
149
150
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 142

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 



124
125
126
127
128
129
130
131
132
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 124

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

#root?(node) ⇒ Boolean

Returns:

  • (Boolean) 


61
62
63
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 61

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

#root_nodes ⇒ Object Also known as: roots 



152
153
154
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 152

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

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



207
208
209
210
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 207

def to_dot(nodeShaper = nil, nodeLabeler = nil, linkLabeler = nil)
  f = DotGraphFormatter.new(nodeShaper, nodeLabeler, linkLabeler) 
  f.format(nodes, links)
end

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



212
213
214
215
 
# File 'lib/rpdf2txt-rockit/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 



188
189
190
191
192
193
194
195
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 188

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/rpdf2txt-rockit/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 



197
198
199
200
201
202
203
204
205
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 197

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