1 package org.broadinstitute.hellbender.tools.walkers.haplotypecaller.graphs; 2 3 import org.apache.commons.lang3.ArrayUtils; 4 import org.broadinstitute.hellbender.utils.Utils; 5 6 import java.util.Collection; 7 import java.util.LinkedList; 8 import java.util.Set; 9 10 /** 11 * Merges the incoming vertices of a vertex V of a graph 12 * 13 * Looks at the vertices that are incoming to V (i.e., have an outgoing edge connecting to V). If 14 * they all have the same sequence, merges them into the sequence of V, and updates the graph 15 * as appropriate 16 */ 17 public final class SharedSequenceMerger { SharedSequenceMerger()18 private SharedSequenceMerger() { } 19 20 /** 21 * Attempt to merge the incoming vertices of v 22 * 23 * @param graph the graph containing the vertex v 24 * @param v the vertex whose incoming vertices we want to merge 25 * @return true if some useful merging was done, false otherwise 26 */ merge(final SeqGraph graph, final SeqVertex v)27 public static boolean merge(final SeqGraph graph, final SeqVertex v) { 28 Utils.nonNull(graph, "graph cannot be null"); 29 Utils.validateArg(graph.vertexSet().contains(v), () -> "graph doesn't contain vertex " + v); 30 31 final Set<SeqVertex> prevs = graph.incomingVerticesOf(v); 32 if ( ! canMerge(graph, v, prevs) ) { 33 return false; 34 } else { 35 final Collection<BaseEdge> edgesToRemove = new LinkedList<>(); 36 final byte[] prevSeq = prevs.iterator().next().getSequence(); 37 final SeqVertex newV = new SeqVertex(ArrayUtils.addAll(prevSeq, v.getSequence())); 38 graph.addVertex(newV); 39 40 for ( final SeqVertex prev : prevs ) { 41 for ( final BaseEdge prevIn : graph.incomingEdgesOf(prev) ) { 42 graph.addEdge(graph.getEdgeSource(prevIn), newV, prevIn.copy()); 43 edgesToRemove.add(prevIn); 44 } 45 } 46 47 for ( final BaseEdge e : graph.outgoingEdgesOf(v) ) { 48 graph.addEdge(newV, graph.getEdgeTarget(e), e.copy()); 49 } 50 51 graph.removeAllVertices(prevs); 52 graph.removeVertex(v); 53 graph.removeAllEdges(edgesToRemove); 54 55 return true; 56 } 57 } 58 59 /** 60 * Can we safely merge the incoming vertices of v 61 * 62 * @param graph the graph containing v and incomingVertices 63 * @param v the vertex we want to merge into 64 * @param incomingVertices the incoming vertices of v 65 * @return true if we can safely merge incomingVertices 66 */ canMerge(final SeqGraph graph, final SeqVertex v, final Collection<SeqVertex> incomingVertices)67 private static boolean canMerge(final SeqGraph graph, final SeqVertex v, final Collection<SeqVertex> incomingVertices) { 68 if ( incomingVertices.isEmpty() ) { 69 return false; 70 } 71 72 final SeqVertex first = incomingVertices.iterator().next(); 73 for ( final SeqVertex prev : incomingVertices) { 74 if ( ! prev.seqEquals(first) ) 75 // cannot merge if our sequence isn't the same as the first sequence 76 { 77 return false; 78 } 79 final Collection<SeqVertex> prevOuts = graph.outgoingVerticesOf(prev); 80 if ( prevOuts.size() != 1 ) 81 // prev -> v must be the only edge from prev 82 { 83 return false; 84 } 85 if ( prevOuts.iterator().next() != v ) 86 // don't allow cyles 87 { 88 return false; 89 } 90 if ( graph.inDegreeOf(prev) == 0 ) 91 // cannot merge when any of the incoming nodes are sources 92 { 93 return false; 94 } 95 } 96 97 return true; 98 } 99 100 }