File: path_utils.hpp

package info (click to toggle)
spades 3.13.1+dfsg-2
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, sid
  • size: 22,172 kB
  • sloc: cpp: 136,213; ansic: 48,218; python: 16,809; perl: 4,252; sh: 2,115; java: 890; makefile: 507; pascal: 348; xml: 303
file content (132 lines) | stat: -rw-r--r-- 5,050 bytes parent folder | download | duplicates (4)
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
//***************************************************************************
//* Copyright (c) 2015 Saint Petersburg State University
//* Copyright (c) 2011-2014 Saint Petersburg Academic University
//* All Rights Reserved
//* See file LICENSE for details.
//***************************************************************************

/*
 * path_utils.hpp
 *
 */

#pragma once

#include "sequence/sequence.hpp"
#include "path_processor.hpp"
#include "mapping_path.hpp"
#include "assembly_graph/dijkstra/dijkstra_algorithm.hpp"

namespace debruijn_graph {


    template<class Graph>
    vector<typename Graph::EdgeId> GetCommonPathsEnd(
            const Graph &g,
            typename Graph::EdgeId e1,
            typename Graph::EdgeId e2,
            size_t min_dist,
            size_t max_dist,
            typename omnigraph::DijkstraHelper<Graph>::BoundedDijkstra &dijkstra) {

        typedef typename Graph::EdgeId EdgeId;
        typedef typename Graph::VertexId VertexId;

        vector<EdgeId> res;
        VERIFY (min_dist >= g.length(e1));
        VERIFY (max_dist >= g.length(e1));
        size_t dist = max_dist - g.length(e1);
        VertexId cur_vertex = g.EdgeStart(e2);
        if (!dijkstra.DistanceCounted(cur_vertex))
            return res;
        size_t cur_dist;
        if ((cur_dist = dijkstra.GetDistance(cur_vertex)) > dist)
            return res;
        size_t suffix_len = 0;
        while (cur_dist > 0) {
            EdgeId prev_edge;
            bool found = false;
            for (auto edge: g.IncomingEdges(cur_vertex)) {
                if ((dijkstra.DistanceCounted(g.EdgeStart(edge))) && (
                        suffix_len + g.length(edge) + dijkstra.GetDistance(g.EdgeStart(edge)) <= dist)) {
                    if (found) {
                        std::reverse(res.begin(), res.end());
                        return res;
                    } else {
                        found = true;
                        prev_edge = edge;
                    }
                }
            }
            if (!found)
                return res;
            else {
                suffix_len += g.length(prev_edge);
                VERIFY(cur_dist >= g.length(prev_edge));
                cur_dist -= g.length(prev_edge);
                cur_vertex = g.EdgeStart(prev_edge);
                res.push_back(prev_edge);
            }
        }
        std::reverse(res.begin(), res.end());
        return res;
    }

    template<class Graph>
    vector<vector<typename Graph::EdgeId> > GetAllPathsBetweenEdges(
            const Graph &g,
            typename Graph::EdgeId &e1,
            typename Graph::EdgeId &e2, size_t min_dist,
            size_t max_dist) {
        omnigraph::PathStorageCallback<Graph> callback(g);
        ProcessPaths(g,
                     min_dist,
                     max_dist,
                     g.EdgeEnd(e1), g.EdgeStart(e2),
                     callback);
        auto paths = callback.paths();
        return paths;
    }

    template<class graph_pack>
    size_t GetAllPathsQuantity(const graph_pack &origin_gp,
                               const typename graph_pack::graph_t::EdgeId &e1,
                               const typename graph_pack::graph_t::EdgeId &e2, double d, double is_var) {
        omnigraph::PathStorageCallback<typename graph_pack::graph_t> callback(origin_gp.g);
        omnigraph::PathProcessor<typename graph_pack::graph_t>
                path_processor(origin_gp.g,
                               (size_t) d - origin_gp.g.length(e1) - size_t(is_var),
                               (size_t) d - origin_gp.g.length(e1) + size_t(is_var),
                               origin_gp.g.EdgeEnd(e1),
                               origin_gp.g.EdgeStart(e2),
                               callback);
        path_processor.Process();
        auto paths = callback.paths();
        TRACE(e1.ind_id() << " " << e2.int_id() << " " << paths.size());
        return paths.size();
    }

    template<class Graph>
    Sequence MergeSequences(const Graph &g,
                            const vector<typename Graph::EdgeId> &continuous_path) {
        vector<Sequence> path_sequences;
        if (continuous_path.size() == 0)
            return Sequence();
        path_sequences.push_back(g.EdgeNucls(continuous_path[0]));
        for (size_t i = 1; i < continuous_path.size(); ++i) {
            VERIFY(g.EdgeEnd(continuous_path[i - 1]) == g.EdgeStart(continuous_path[i]));
            path_sequences.push_back(g.EdgeNucls(continuous_path[i]));
        }
        return MergeOverlappingSequences(path_sequences, g.k(), /*no need to check again*/false);
    }

    template<class Graph>
    Sequence PathSequence(const Graph &g, const omnigraph::Path<typename Graph::EdgeId> &path) {
        Sequence path_sequence = MergeSequences(g, path.sequence());
        size_t start = path.start_pos();
        size_t end = path_sequence.size() - g.length(path[path.size() - 1]) + path.end_pos();
        return path_sequence.Subseq(start, end);
    }


}