Class: BackLinkedDirectedGraph

Inherits:
DirectedGraph show all
Defined in:
lib/rpdf2txt-rockit/directed_graph.rb

Overview

Directed graph with fast traversal from children to parents (back)

Direct Known Subclasses

Parse::StateGraph

Instance Attribute Summary

Attributes inherited from DirectedGraph

#links

Instance Method Summary collapse

Methods inherited from DirectedGraph

#acyclic?, #add_link_nodes, #add_node, #children, #cyclic?, #each_reachable_node_once_breadth_first, #each_reachable_node_once_depth_first, #include_node?, #internal_node?, #internal_nodes, #leaf?, #leaf_nodes, #link_nodes, #links_from, #links_from_to, #links_from_to?, #nodes, #recurse_cyclic?, #recurse_each_reachable_breadth_first_visited, #recurse_each_reachable_depth_first_visited, #root?, #root_nodes, #to_dot, #to_postscript_file, #transition, #transitive_closure_floyd_warshal, #traverse

Constructor Details

#initialize(*args) ⇒ BackLinkedDirectedGraph

Returns a new instance of BackLinkedDirectedGraph.



291
292
293
294
295
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 291

def initialize(*args)
  super
  @back_link_map = HashOfHash.new {Array.new} # [to][from] -> array of links
  @incoming_links_info = DefaultInitHash.new {Array.new}
end

Instance Method Details



297
298
299
300
301
302
303
304
305
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 297

def add_link(from, to, informationOnLink = nil)
  link = super
  links_to_from(to, from).push link
  if informationOnLink and 
	!@incoming_links_info[to].include?(informationOnLink)
    @incoming_links_info[to].push informationOnLink
  end
  link
end

#back_transition(node, backLinkInfo) ⇒ Object 



311
312
313
314
315
316
317
318
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 311

def back_transition(node, backLinkInfo)
  link = links_to(node).detect {|l| l.info == backLinkInfo}
  begin
    link.from
  rescue Exception
    raise GraphTraversalException.new(node, links_to(node), backLinkInfo)
  end
end

#back_traverse(state, alongLinksWithInfo = []) ⇒ Object 



320
321
322
323
324
325
326
327
328
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 320

def back_traverse(state, alongLinksWithInfo = [])
  len = alongLinksWithInfo.length
  alongLinksWithInfo = alongLinksWithInfo.clone
  while len > 0
    state = back_transition(state, alongLinksWithInfo.pop)
    len -= 1
  end
  state
end

#incoming_links_info(node) ⇒ Object 



307
308
309
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 307

def incoming_links_info(node)
  @incoming_links_info[node]
end

#links_to(node) ⇒ Object 



330
331
332
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 330

def links_to(node)
  @back_link_map[node].map {|from, links| links}.flatten
end