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 }