1 #ifndef GRAPH_OPTIMIZE_H 2 #define GRAPH_OPTIMIZE_H 3 /* 4 * graph_optimize.h 5 * cufflinks 6 * 7 * Created by Cole Trapnell on 6/1/10. 8 * Copyright 2010 Cole Trapnell. All rights reserved. 9 * 10 */ 11 12 #include <vector> 13 14 #include <boost/graph/depth_first_search.hpp> 15 #include <boost/graph/visitors.hpp> 16 17 #include "bundles.h" 18 #include "scaffold_graph.h" 19 #include "scaffolds.h" 20 21 using namespace std; 22 23 using namespace boost; 24 25 template < typename PredecessorMap, 26 typename PathIDMap > 27 class path_compress_visitor : public default_dfs_visitor 28 { 29 public: path_compress_visitor(PathIDMap pm)30 path_compress_visitor(PathIDMap pm) : curr_path_id(0), path_map(pm) {} 31 32 template < typename Vertex, typename Graph > initialize_vertex(Vertex u,const Graph & g)33 void initialize_vertex(Vertex u, const Graph & g) const 34 { 35 put(predecessor, u, u); 36 put(path_map, u, u); 37 } 38 39 template < typename Vertex, typename Graph > discover_vertex(Vertex u,const Graph & g)40 void discover_vertex(Vertex u, const Graph & g) 41 { 42 //fprintf(stderr, "node %d has indegree %d, outdegree %d\n",u,in_degree(u, g),out_degree(u, g)); 43 if (in_degree(u, g) == 1) 44 { 45 46 Vertex v = get(predecessor, u); 47 48 assert(v != u); 49 50 if (out_degree(v, g) == 1) 51 { 52 // compress into predecessor's path 53 typename PathIDMap::value_type path = get(path_map, v); 54 put(path_map, u, path); 55 //fprintf(stderr, "\told path for node %d = %d\n", u, path); 56 57 return; 58 } 59 } 60 // start a new path 61 curr_path_id++; 62 put(path_map, u, curr_path_id); 63 //fprintf(stderr, "\tnew path for node %d = %d\n", u, curr_path_id); 64 65 } 66 67 template < typename Edge, typename Graph > tree_edge(Edge e,const Graph & g)68 void tree_edge(Edge e, const Graph & g) const 69 { 70 put(predecessor, target(e, g), source(e, g)); 71 } 72 last_path_id()73 size_t last_path_id() const { return curr_path_id; } 74 75 PredecessorMap predecessor; 76 77 size_t curr_path_id; 78 PathIDMap path_map; 79 }; 80 81 void fill_gaps(vector<Scaffold>& scaffolds, int fill_size); 82 83 void compress_fragments(vector<Scaffold>& hits); 84 85 bool collapse_equivalent_transfrags(vector<Scaffold>& scaffolds, 86 uint32_t max_rounds = 0xFFFFFFFF); 87 88 bool collapse_contained_transfrags(vector<Scaffold>& scaffolds, 89 uint32_t max_rounds = 0xFFFFFFFF); 90 91 void compress_overlap_dag_paths(DAG& bundle_dag, 92 vector<Scaffold>& hits); 93 94 #endif 95