1 /*
2 * matching_merge.cpp
3 * cufflinks
4 *
5 * Created by Cole Trapnell on 6/1/10.
6 * Copyright 2010 Cole Trapnell. All rights reserved.
7 *
8 */
9
10 #include "matching_merge.h"
11
12 using namespace std;
13 using namespace boost;
14
find_path(const DAG & bundle_dag,const adjacency_list<> & TC,const DAGNode & source,const DAGNode & target,vector<DAGNode> & path)15 void find_path(const DAG& bundle_dag,
16 const adjacency_list<>& TC,
17 const DAGNode& source,
18 const DAGNode& target,
19 vector<DAGNode>& path)
20 {
21 if (source == target)
22 return;
23 bool done = false;
24 DAGNode curr = source;
25 while(!done)
26 {
27 graph_traits<DAG>::adjacency_iterator i, iend;
28 for (tie(i,iend) = adjacent_vertices(curr, bundle_dag); i != iend; ++i)
29 {
30 DAGNode I = *i;
31 pair<adjacency_list<>::edge_descriptor, bool> p;
32 p = edge(I, target, TC);
33 if (p.second)
34 {
35 path.push_back(*i);
36 curr = *i;
37 break;
38 }
39 if (*i == target)
40 {
41 path.push_back(*i);
42 done = true;
43 break;
44 }
45 }
46 }
47 }
48
extend_chains_to_paths(const DAG & bundle_dag,vector<vector<DAGNode>> & chains,adjacency_list<> & TC,DAGNode source,DAGNode sink,vector<vector<DAGNode>> & paths)49 void extend_chains_to_paths(const DAG& bundle_dag,
50 vector<vector<DAGNode> >& chains,
51 adjacency_list<>& TC,
52 DAGNode source,
53 DAGNode sink,
54 vector<vector<DAGNode> >& paths)
55 {
56 //Extend each chain to a path
57 for(size_t c = 0; c < chains.size(); ++c)
58 {
59 vector<DAGNode>& chain = chains[c];
60 assert (!chain.empty());
61 reverse(chain.begin(), chain.end());
62 vector<DAGNode> path;
63 find_path(bundle_dag, TC, source, chain[0], path);
64 for (size_t n = 1; n < chain.size(); ++n)
65 {
66 assert (path.back() == chain[n - 1]);
67 DAGNode last = chain[n-1];
68 DAGNode next = chain[n];
69 find_path(bundle_dag, TC, last, next, path);
70 }
71 find_path(bundle_dag, TC, chain.back(), sink, path);
72 assert (path.back() == sink);
73 path.pop_back();
74 paths.push_back(path);
75 }
76 }
77
make_scaffolds_from_paths(DAG & bundle_dag,const vector<vector<DAGNode>> & paths,vector<Scaffold> & scaffolds)78 void make_scaffolds_from_paths(DAG& bundle_dag,
79 const vector<vector<DAGNode> >& paths,
80 vector<Scaffold>& scaffolds)
81 {
82 HitsForNodeMap hits_for_node = get(vertex_name, bundle_dag);
83 for (size_t p = 0; p < paths.size(); ++p)
84 {
85 const vector<DAGNode>& path = paths[p];
86
87 vector<Scaffold> path_alignments;
88 for (size_t m = 0; m < path.size(); ++m)
89 {
90 //fprintf(stderr, "%d ", scaff_id);
91 path_alignments.push_back(*(hits_for_node[path[m]]));
92 }
93 //fprintf(stderr,"\n");
94 //fprintf(stderr, "\tMerging path %d into scaffold\n", p);
95 Scaffold s(path_alignments);
96
97 //fprintf(stderr, "PATH %d\n-------------------------------------\n",s.get_id());
98 scaffolds.push_back(s);
99 }
100 sort(scaffolds.begin(), scaffolds.end(), scaff_lt);
101 }
102
103
104