GraphAlgorithms_Paths.inl

Go to the documentation of this file.

/*******************************************************************************
 * The software programs comprising "CGRA-ME" and the documentation provided
 * with them are copyright by its authors and the University of Toronto. Only
 * non-commercial, not-for-profit use of this software is permitted without ex-
 * plicit permission. This software is provided "as is" with no warranties or
 * guarantees of support. See the LICENCE for more details. You should have re-
 * ceived a copy of the full licence along with this software. If not, see
 * <http://cgra-me.ece.utoronto.ca/license/>.
 ******************************************************************************/
 
template<typename VertexDataMap, typename Visitor = DoNothingGraphVisitor<VertexID>, typename SourceList = std::vector<VertexID>>
TracebackResult singleTraceback(
    const SourceList& sources,
    const VertexID& sink,
    const VertexDataMap& vertex_data,
    Visitor&& visitor = {}
) const {
    using std::end;
 
    auto nodes_in_path = makeVertexSet();
    std::vector<VertexID> path;
    bool success = true;
 
    bool done = false;
    bool left_source = false;
    auto traceback_curr = sink;
    while (success && not done) {
        success = false;
        visitor.onExamine(traceback_curr);
        path.push_back(traceback_curr);
        if (left_source) {
            nodes_in_path.insert(traceback_curr);  // properly handle when sink \in sources
        }
        if (sources.find(traceback_curr) != end(sources) && left_source) {
            success = true;
            done = true;
        } else {
            const auto& data_search = vertex_data.find(traceback_curr);
            if (data_search != end(vertex_data)) {
                auto& found_data = data_search->second;
                for (auto& fanin : found_data.fanin) {
                    if (not visitor.shouldIgnore(fanin) && nodes_in_path.find(fanin) == end(nodes_in_path)) {
                        traceback_curr = fanin;
                        success = true;
                        break;
                    }
                }
                if (not success && not found_data.fanin.empty()) {
                    traceback_curr = found_data.fanin.front();
                    success = true;
                }
                if (success && nodes_in_path.find(traceback_curr) != end(nodes_in_path)) {
                    success = false;
                }
            }
        }
        left_source = true;
    }
 
    std::reverse(begin(path), end(path));
 
    return {path, success};
}
 
 
template<typename Graph, typename IsTarget, typename AcceptPath = AlwaysTrue,
    typename Visitor = DoNothingGraphVisitor<VertexID>, typename InitialList = std::vector<VertexID>>
PathList findNShortestPaths(
    std::ptrdiff_t max_paths,
    Graph&& graph,
    const InitialList& initial_list,
    IsTarget&& is_target,
    Visitor&& visitor = {},
    AcceptPath&& acceptPath = {}
) const {
    struct VertexData {
        int expansion_count = 0;
        bool operator==(const VertexData& rhs) const { return this->expansion_count == rhs.expansion_count; }
    };
 
    auto vdata = makeVertexMap<VertexData>();
 
    PathList result;
 
    // the "wavefront" of paths
    std::set<std::pair<std::ptrdiff_t, VertexPath>> paths_to_explore;
    // any paths skipped because of max-expansion.
    // Used to re-seed the wavefront if a path is not accepted.
    std::set<std::pair<std::ptrdiff_t, VertexPath>> paths_skipped;
 
    int skipped_paths = 0;
 
    const auto cost_and_add_path = [&](const auto& base_path, const auto& new_vertex) {
        auto new_path = base_path;
        new_path.push_back(new_vertex);
        auto new_path_cost = new_path.size();
        paths_to_explore.emplace(new_path_cost, std::move(new_path));
    };
 
    // do the first wave of expansion, so we never have size-1 paths
    for (const auto& vertex : initial_list) {
        if (visitor.shouldIgnore(vertex)) {
            visitor.onSkippedEdge(vertex, vertex); continue; }
 
        visitor.onExamine(vertex);
        for (const auto& fanout : graph.fanout(vertex)) {
            if (visitor.shouldIgnore(fanout) || visitor.shouldIgnoreEdge(vertex,fanout)) {
                visitor.onSkippedEdge(vertex, fanout); continue; }
 
            visitor.onExamineEdge(vertex,fanout);
            cost_and_add_path(VertexPath{vertex}, fanout);
        }
    }
 
    while (!paths_to_explore.empty() && ((std::ptrdiff_t)result.size() + skipped_paths) != max_paths) {
        // get shortest path & remove it
        auto cost_and_path_mutable = std::move(*paths_to_explore.begin());
        const auto& p = cost_and_path_mutable.second; // all access will be const
        paths_to_explore.erase(begin(paths_to_explore));
 
        const auto& tip = p.back();
 
        if (visitor.shouldIgnore(tip)) {
            visitor.onSkipped(tip);
            continue;
        }
 
        if (vdata[tip].expansion_count == max_paths) {
            visitor.onSkipped(tip);
            // save for later, in case a path is not accepted
            paths_skipped.insert(std::move(cost_and_path_mutable));
            continue;
        }
 
        visitor.onExamine(tip);
 
        // increase expansion number of tip
        vdata[tip].expansion_count += 1;
 
        // if we still want to expand the target, then add paths with fanout to explore queue
        for (const auto& fanout : graph.fanout(tip)) {
            if (
                   not visitor.shouldIgnore(fanout)
                && not visitor.shouldIgnoreEdge(tip,fanout)
                && p.front() != p.back() // don't expand loops
                && find(std::next(begin(p)), end(p), fanout) == end(p) // no repeats, except the first
            ) {
                cost_and_add_path(p, fanout);
 
                visitor.onExamineEdge(tip, fanout);
            } else {
                visitor.onSkippedEdge(tip, fanout);
            }
        }
 
        // if tip is target, add to result set
        if (is_target(tip)) {
            if (acceptPath(p)) {
                result.emplace_back(std::move(cost_and_path_mutable.second));
            } else {
                max_paths += 1; // make sure search continues
                skipped_paths += 1; // remember we skipped one
                // reconsider any skipped paths
                std::move(paths_skipped.begin(), paths_skipped.end(),
                    std::inserter(paths_to_explore, paths_to_explore.end()));
                paths_skipped.clear();
            }
        }
    }
 
    return result;
}
 
template<typename Graph, typename IsTarget, typename Visitor = DoNothingGraphVisitor<VertexID>, typename InitialList = std::vector<VertexID>>
PathList findNShortestSimplePaths(
    std::ptrdiff_t max_paths,
    Graph&& graph,
    const InitialList& initial_list,
    IsTarget&& is_target,
    Visitor&& visitor
) const {
    auto initial_path = findNShortestPaths(1, graph, initial_list, is_target, visitor).at(0);
    std::set<std::pair<int,VertexPath>> potential_paths {};
 
    PathList result;
    if (max_paths == 0) { return result; }
    result.push_back(initial_path);
    for (int k = 1; k != max_paths; ++k) {
        const auto& prev_path = result.back();
 
        for (int i = 0; i < (std::ptrdiff_t)prev_path.size() - 1; ++i) {
            const auto pp_spurNode = std::next(prev_path.begin(), i);
 
            struct V : ForwardingVisitor<Visitor> {
                using Base = ForwardingVisitor<Visitor>;
                VertexSet<> vertices_to_ignore = {};
                EdgeSet edges_to_ignore = {};
 
                V(typename Base::VisitorPtr fwd) : Base(fwd) { }
 
                bool shouldIgnore(const VertexID& v) {
                    return Base::shouldIgnore(v)
                        || vertices_to_ignore.find(v) != end(vertices_to_ignore);
                }
                bool shouldIgnoreEdge(const VertexID& v1, const VertexID& v2) {
                    return Base::shouldIgnoreEdge(v1,v2)
                        || edges_to_ignore.find(std::make_pair(v1, v2)) != end(edges_to_ignore);
                }
            } v (&visitor);
 
            for (const auto& p : result) {
                if (std::mismatch(
                        prev_path.begin(), std::next(pp_spurNode),
                        p.begin(), p.end()
                    ).first == std::next(pp_spurNode)
                ) {
                    v.edges_to_ignore.emplace(p.at(i), p.at(i+1));
                }
            }
            for (auto it = prev_path.begin(); it != pp_spurNode; ++it) {
                v.vertices_to_ignore.insert(*it);
            }
 
            const auto spurpath_search = findNShortestPaths(1, graph, {*pp_spurNode}, is_target, v);
            if (spurpath_search.size() == 0) {
                continue;
            }
            const auto& spur_path = spurpath_search.at(0);
 
            VertexPath totalPath;
            std::copy(prev_path.begin(), pp_spurNode, std::back_inserter(totalPath));
            std::copy(spur_path.begin(), spur_path.end(), std::back_inserter(totalPath));
 
            potential_paths.emplace(totalPath.size(), totalPath);
        }
 
        if (potential_paths.empty()) {
            break;
        }
 
        auto best_path_it = potential_paths.begin();
        result.push_back(best_path_it->second);
        potential_paths.erase(best_path_it);
    }
 
 
    return result;
}