File: path_finders.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 (123 lines) | stat: -rw-r--r-- 3,799 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
#pragma once

#include "assembly_graph/core/directions.hpp"

namespace omnigraph {
template<class Graph>
class UniquePathFinder {
    typedef typename Graph::EdgeId EdgeId;
    typedef typename Graph::VertexId VertexId;

    const Graph& graph_;
public:
    UniquePathFinder(const Graph& graph)
            : graph_(graph) {}

    std::vector<EdgeId> operator()(EdgeId e,
                                   const AbstractDirection<Graph> &direction) const {
        std::vector<EdgeId> answer;
        EdgeId curr = e;
        answer.push_back(curr);
        std::set<EdgeId> was;
        while (direction.CheckUniqueOutgoingEdge(direction.EdgeEnd(curr))) {
            curr = direction.GetUniqueOutgoingEdge(direction.EdgeEnd(curr));
            if (was.count(curr) > 0)
                break;
            was.insert(curr);
            answer.push_back(curr);
        }
        return answer;
    }

    std::vector<EdgeId> UniquePathForward(EdgeId e) const {
        return this->operator()(e, ForwardDirection<Graph>(graph_));
    }

    std::vector<EdgeId> UniquePathBackward(EdgeId e) const {
        auto answer = this->operator()(e, BackwardDirection<Graph>(graph_));
        std::reverse(answer.begin(), answer.end());
        return answer;
    }

};

template<class Graph>
class TrivialPathFinder {
    typedef typename Graph::EdgeId EdgeId;
    typedef typename Graph::VertexId VertexId;

public:
    TrivialPathFinder(const Graph&, size_t = 0) {}

    std::vector<EdgeId> operator()(EdgeId e, const AbstractDirection<Graph> &) const {
        return {e};
    }

};

template<class Graph>
class PlausiblePathFinder {
    typedef typename Graph::EdgeId EdgeId;
    typedef typename Graph::VertexId VertexId;

    //todo remove graph_ field???
    const Graph& graph_;
    const size_t length_bound_;

    class DFS {
    private:
        const Graph &graph_;
        const AbstractDirection<Graph> &direction_;
        const size_t length_bound_;

        std::pair<size_t, EdgeId> find(EdgeId edge, size_t length) {
            length += graph_.length(edge);
            VertexId cross = direction_.EdgeEnd(edge);
            auto result = make_pair(length, edge);
            if (length < length_bound_
                && direction_.CheckUniqueIncomingEdge(cross)) {
                std::vector<EdgeId> outgoing = direction_.OutgoingEdges(cross);
                for (auto it = outgoing.begin(); it != outgoing.end(); ++it) {
                    auto candidate = find(*it, length);
                    if (candidate.first > result.first)
                        result = candidate;
                }
            }
            return result;
        }

        std::vector<EdgeId> RestoreAnswer(EdgeId start, EdgeId end) {
            std::vector<EdgeId> result;
            while (end != start) {
                result.push_back(end);
                end = direction_.GetUniqueIncomingEdge(direction_.EdgeStart(end));
            }
            result.push_back(start);
            return std::vector<EdgeId>(result.rbegin(), result.rend());
        }

    public:
        DFS(const Graph &graph, const AbstractDirection<Graph> &direction,
            size_t length_bound)
                : graph_(graph),
                  direction_(direction),
                  length_bound_(length_bound) {
        }

        std::vector<EdgeId> find(EdgeId edge) {
            return RestoreAnswer(edge, find(edge, 0).second);
        }
    };

public:
    PlausiblePathFinder(const Graph& graph, size_t length_bound)
            : graph_(graph),
              length_bound_(length_bound) {}

    std::vector<EdgeId> operator()(EdgeId e,
                                   const AbstractDirection<Graph> &direction) const {
        return DFS(graph_, direction, length_bound_).find(e);
    }

};
}