Class: BackLinkedDirectedGraph

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

Overview

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

Instance Attribute Summary

Attributes inherited from DirectedGraph

#is_leaf, #is_root, #link_map, #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.



371
372
373
374
375
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 371

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



377
378
379
380
381
382
383
384
385
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 377

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 



391
392
393
394
395
396
397
398
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 391

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 



400
401
402
403
404
405
406
407
408
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 400

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 



387
388
389
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 387

def incoming_links_info(node)
  @incoming_links_info[node]
end

#links_to(node) ⇒ Object 



410
411
412
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 410

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