Class: BackLinkedDirectedGraph

Inherits:
DirectedGraph show all
Defined in:
lib/graphr/directed_graph.rb

Overview

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

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, #num_vertices, #recurse_cyclic?, #recurse_each_reachable_breadth_first_visited, #recurse_each_reachable_depth_first_visited, #recurse_strongly_connected_components, #root?, #root_nodes, #strongly_connected_components, #to_dot, #to_postscript_file, #transition, #transitive_closure_floyd_warshal, #traverse

Constructor Details

#initialize(*args) ⇒ BackLinkedDirectedGraph

Returns a new instance of BackLinkedDirectedGraph.



363
364
365
366
367
 
# File 'lib/graphr/directed_graph.rb', line 363

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



369
370
371
372
373
374
375
376
377
 
# File 'lib/graphr/directed_graph.rb', line 369

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 



383
384
385
386
387
388
389
390
 
# File 'lib/graphr/directed_graph.rb', line 383

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 



392
393
394
395
396
397
398
399
400
 
# File 'lib/graphr/directed_graph.rb', line 392

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 



379
380
381
 
# File 'lib/graphr/directed_graph.rb', line 379

def incoming_links_info(node)
  @incoming_links_info[node]
end

#links_to(node) ⇒ Object 



402
403
404
 
# File 'lib/graphr/directed_graph.rb', line 402

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