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