File: graph_optimize.h

package info (click to toggle)
cufflinks 1.3.0-2
  • links: PTS, VCS
  • area: non-free
  • in suites: wheezy
  • size: 3,864 kB
  • sloc: cpp: 48,999; ansic: 12,297; sh: 3,381; python: 432; makefile: 209
file content (94 lines) | stat: -rw-r--r-- 2,557 bytes parent folder | download | duplicates (5)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#ifndef GRAPH_OPTIMIZE_H
#define GRAPH_OPTIMIZE_H
/*
 *  graph_optimize.h
 *  cufflinks
 *
 *  Created by Cole Trapnell on 6/1/10.
 *  Copyright 2010 Cole Trapnell. All rights reserved.
 *
 */

#include <vector>

#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/visitors.hpp>

#include "bundles.h"
#include "scaffold_graph.h"
#include "scaffolds.h"

using namespace std;

using namespace boost;

template < typename PredecessorMap, 
           typename PathIDMap > 
class path_compress_visitor : public default_dfs_visitor 
{    
public:
    path_compress_visitor(PathIDMap pm) : curr_path_id(0), path_map(pm) {}
    
    template < typename Vertex, typename Graph >
    void initialize_vertex(Vertex u, const Graph & g) const
    {
        put(predecessor, u, u);
        put(path_map, u, u);
    }
    
    template < typename Vertex, typename Graph >
    void discover_vertex(Vertex u, const Graph & g)
    {
        //fprintf(stderr, "node %d has indegree %d, outdegree %d\n",u,in_degree(u, g),out_degree(u, g)); 
        if (in_degree(u, g) == 1)
        {
            
            Vertex v = get(predecessor, u);
            
            assert(v != u);
            
            if (out_degree(v, g) == 1)
            {
                // compress into predecessor's path 
                typename PathIDMap::value_type path = get(path_map, v);
                put(path_map, u, path);
                //fprintf(stderr, "\told path for node %d = %d\n", u, path);
                
                return;
            }
        }
        // start a new path
        curr_path_id++;
        put(path_map, u, curr_path_id);
        //fprintf(stderr, "\tnew path for node %d = %d\n", u, curr_path_id);
        
    }
    
    template < typename Edge, typename Graph >
    void tree_edge(Edge e, const Graph & g) const
    {
        put(predecessor, target(e, g), source(e, g));
    }
    
    size_t last_path_id() const { return curr_path_id; }
    
    PredecessorMap predecessor;
    
    size_t curr_path_id;
	PathIDMap path_map;
};

void fill_gaps(vector<Scaffold>& scaffolds, int fill_size);

void compress_fragments(vector<Scaffold>& hits);

bool collapse_equivalent_transfrags(vector<Scaffold>& scaffolds, 
                                    uint32_t max_rounds = 0xFFFFFFFF);

bool collapse_contained_transfrags(vector<Scaffold>& scaffolds, 
                                   uint32_t max_rounds = 0xFFFFFFFF);

void compress_overlap_dag_paths(DAG& bundle_dag,
                                vector<Scaffold>& hits);

#endif