Class: Bio::Velvet::Graph

Inherits:
Object
  • Object
show all
Defined in:
lib/assembly/depth_first_search.rb,
lib/assembly/oriented_node_trail.rb

Direct Known Subclasses

FinishM::HybridGraph

Defined Under Namespace

Classes: Node, NodedRead, OrientedNodeTrail

Instance Method Summary collapse

Instance Method Details

#depth_first_search(oriented_node) ⇒ Object

Do a depth first search starting at this oriented node, yielding an OrientedNodeTrail at each new node encountered. The new node is the last node in the yielded trail. The result of the yield tells whether this method whether to abandon searching further from this point (false) or keep going (true).



13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
# File 'lib/assembly/depth_first_search.rb', line 13

def depth_first_search(oriented_node)
  log = Bio::Log::LoggerPlus['finishm']
  discovered_oriented_nodes = Set.new

  # Traverse through the graph, yielding at each new node
  current_path = Bio::Velvet::Graph::OrientedNodeTrail.new
  current_path.add_oriented_node oriented_node

  stack = DS::Stack.new
  stack.push current_path

  # While there is more on the stack
  while current_path = stack.pop
    log.debug "Perhaps #{current_path.last}?" if log.debug?
    if discovered_oriented_nodes.include?(path_to_searchable(current_path))
      # Already seen this node, do nothing with it
      log.debug "Skipping #{current_path.last} since that has already been seen" if log.debug?
      next
    else
      log.debug "That's a new node, #{current_path.last}" if log.debug?
      # Found a new node for the user to play with
      discovered_oriented_nodes << path_to_searchable(current_path)

      continue = yield current_path

      # prep for next time if required.
      if continue
        # Sort node IDs to simplify testing
        next_nodes = current_path.neighbours_of_last_node(self).sort{|n1, n2|
          -(n1.node.node_id <=> n2.node.node_id)
        }
        next_nodes.each do |n|
          path = current_path.copy
          path.add_oriented_node n
          stack.push path
        end
      end
    end
  end
end

#neighbours_of(node, first_side) ⇒ Object

Return an Array of OrientedNode objects corresponding to all the nodes that are next in the graph.



7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
# File 'lib/assembly/oriented_node_trail.rb', line 7

def neighbours_of(node, first_side)
  neighbour_nodes = nil
  if first_side == OrientedNodeTrail::START_IS_FIRST
    neighbour_nodes = neighbours_off_end(node)
  else
    neighbour_nodes = neighbours_into_start(node)
  end

  neighbours_with_orientation = []
  neighbour_nodes.each do |neighbour|
    arcs = get_arcs_by_node node, neighbour

    # This if statement entered if two nodes are connected twice,
    # in both directions. Remove one direction as it shouldn't be here
    if arcs.length > 1
      if first_side == OrientedNodeTrail::START_IS_FIRST
        arcs = arcs.select do |arc|
          (arc.begin_node_id == node.node_id and arc.begin_node_direction) or
          (arc.end_node_id == node.node_id and !arc.end_node_direction)
        end
      else
        arcs = arcs.select do |arc|
          (arc.end_node_id == node.node_id and arc.end_node_direction) or
          (arc.begin_node_id == node.node_id and !arc.begin_node_direction)
        end
      end
    end

    # Sometimes, but rarely, two nodes will be joined more than once, for whatever reason
    arcs.each do |arc|
      oriented = OrientedNodeTrail::OrientedNode.new
      oriented.node = neighbour
      if arc.begin_node_id == arc.end_node_id
        # A node connecting to itself. Happens rarely.
        if first_side == OrientedNodeTrail::START_IS_FIRST
          if arc.begin_node_direction and arc.end_node_direction
            oriented.first_side = OrientedNodeTrail::START_IS_FIRST
          elsif arc.begin_node_direction and !arc.end_node_direction
            oriented.first_side = OrientedNodeTrail::END_IS_FIRST
          elsif !arc.begin_node_direction and arc.end_node_direction
            raise "I don't think this is supposed to be possible. Programming error?"
          elsif !arc.begin_node_direction and !arc.end_node_direction
            oriented.first_side = OrientedNodeTrail::START_IS_FIRST
          else
            raise "programming error"
          end
        else
          # coming from the end of the original node
          if arc.begin_node_direction and arc.end_node_direction
            oriented.first_side = OrientedNodeTrail::END_IS_FIRST
          elsif arc.begin_node_direction and !arc.end_node_direction
            raise "I don't think this is supposed to be possible. Programming error?"
          elsif !arc.begin_node_direction and arc.end_node_direction
            oriented.first_side = OrientedNodeTrail::START_IS_FIRST
          elsif !arc.begin_node_direction and !arc.end_node_direction
            oriented.first_side = OrientedNodeTrail::END_IS_FIRST
          else
            raise "programming error"
          end
        end

      elsif arc.begin_node_id == neighbour.node_id
        # connected to a different node, the 1st in the arc's pair
        if arc.begin_node_direction
          oriented.first_side = OrientedNodeTrail::END_IS_FIRST
        else
          oriented.first_side = OrientedNodeTrail::START_IS_FIRST
        end
      elsif arc.end_node_id == neighbour.node_id
        # connected to a different node, the 2nd in the arc's pair
        if arc.end_node_direction
          oriented.first_side = OrientedNodeTrail::START_IS_FIRST
        else
          oriented.first_side = OrientedNodeTrail::END_IS_FIRST
        end
      end

      neighbours_with_orientation.push oriented
    end
  end

  return neighbours_with_orientation
end

#neighbours_of_node_id(node_id, first_side) ⇒ Object

Like #neighbours_of, except takes a velvet node id rather than a node object



92
93
94
 
# File 'lib/assembly/oriented_node_trail.rb', line 92

def neighbours_of_node_id(node_id, first_side)
  neighbours_of(@nodes[node_id], first_side)
end