X-Git-Url: https://git.lyx.org/gitweb/?a=blobdiff_plain;f=src%2FGraph.cpp;h=0165bdacc9a4c95d626f21996f83f010c1a52959;hb=3209e6604ef132c8488ad14719b29406899d8b00;hp=8893aecfc9f10717c1beef93bb2aa27c3792b254;hpb=ac6a58071e642c787c0d84027ff31d11972e08f2;p=lyx.git diff --git a/src/Graph.cpp b/src/Graph.cpp index 8893aecfc9..0165bdacc9 100644 --- a/src/Graph.cpp +++ b/src/Graph.cpp @@ -3,7 +3,8 @@ * This file is part of LyX, the document processor. * Licence details can be found in the file COPYING. * - * \author Dekel Tsur + * \author Dekel Tsur (original code) + * \author Richard Kimberly Heck (re-implementation) * * Full author contact details are available in file CREDITS. */ @@ -13,54 +14,63 @@ #include "Graph.h" #include "Format.h" -#include +#include "support/debug.h" +#include "support/lassert.h" using namespace std; namespace lyx { -bool Graph::bfs_init(int s, bool clear_visited) +bool Graph::bfs_init(int s, bool clear_visited, queue & Q) { if (s < 0) return false; - Q_ = queue(); + if (!Q.empty()) + Q = queue(); - if (clear_visited) - fill(visited_.begin(), visited_.end(), false); - if (visited_[s] == false) { - Q_.push(s); - visited_[s] = true; + if (clear_visited) { + vector::iterator it = vertices_.begin(); + vector::iterator en = vertices_.end(); + for (; it != en; ++it) + it->visited = false; + } + if (!vertices_[s].visited) { + Q.push(s); + vertices_[s].visited = true; } return true; } -vector const - Graph::getReachableTo(int target, bool clear_visited) +Graph::EdgePath const + Graph::getReachableTo(int to, bool clear_visited) { - vector result; - if (!bfs_init(target, clear_visited)) + EdgePath result; + queue Q; + if (!bfs_init(to, clear_visited, Q)) return result; // Here's the logic, which is shared by the other routines. - // Q_ holds a list of nodes we have been able to reach (in this - // case, reach backwards). It is initailized to the current node + // Q holds a list of nodes we have been able to reach (in this + // case, reach backwards). It is initialized to the current node // by bfs_init, and then we recurse, adding the nodes we can reach - // from the current node as we go. - while (!Q_.empty()) { - int const current = Q_.front(); - Q_.pop(); - if (current != target || formats.get(target).name() != "lyx") + // from the current node as we go. That makes it a breadth-first + // search. + while (!Q.empty()) { + int const current = Q.front(); + Q.pop(); + if (current != to || theFormats().get(to).name() != "lyx") result.push_back(current); - vector::iterator it = vertices_[current].in_vertices.begin(); - vector::iterator end = vertices_[current].in_vertices.end(); + vector::iterator it = vertices_[current].in_arrows.begin(); + vector::iterator const end = vertices_[current].in_arrows.end(); for (; it != end; ++it) { - if (!visited_[*it]) { - visited_[*it] = true; - Q_.push(*it); + const int cv = (*it)->from; + if (!vertices_[cv].visited) { + vertices_[cv].visited = true; + Q.push(cv); } } } @@ -69,36 +79,38 @@ vector const } -vector const +Graph::EdgePath const Graph::getReachable(int from, bool only_viewable, - bool clear_visited) + bool clear_visited, set excludes) { - vector result; - if (!bfs_init(from, clear_visited)) + EdgePath result; + queue Q; + if (!bfs_init(from, clear_visited, Q)) return result; - while (!Q_.empty()) { - int const current = Q_.front(); - Q_.pop(); - Format const & format = formats.get(current); + while (!Q.empty()) { + int const current = Q.front(); + Q.pop(); + Format const & format = theFormats().get(current); if (!only_viewable || !format.viewer().empty()) result.push_back(current); else if (format.isChildFormat()) { Format const * const parent = - formats.getFormat(format.parentFormat()); + theFormats().getFormat(format.parentFormat()); if (parent && !parent->viewer().empty()) result.push_back(current); } - vector::const_iterator cit = + vector::const_iterator cit = vertices_[current].out_arrows.begin(); - vector::const_iterator end = + vector::const_iterator end = vertices_[current].out_arrows.end(); for (; cit != end; ++cit) { - int const cv = cit->vertex; - if (!visited_[cv]) { - visited_[cv] = true; - Q_.push(cv); + int const cv = (*cit)->to; + if (!vertices_[cv].visited) { + vertices_[cv].visited = true; + if (excludes.find(cv) == excludes.end()) + Q.push(cv); } } } @@ -112,24 +124,25 @@ bool Graph::isReachable(int from, int to) if (from == to) return true; - if (to < 0 || !bfs_init(from)) + queue Q; + if (to < 0 || !bfs_init(from, true, Q)) return false; - while (!Q_.empty()) { - int const current = Q_.front(); - Q_.pop(); + while (!Q.empty()) { + int const current = Q.front(); + Q.pop(); if (current == to) return true; - vector::const_iterator cit = + vector::const_iterator cit = vertices_[current].out_arrows.begin(); - vector::const_iterator end = + vector::const_iterator end = vertices_[current].out_arrows.end(); for (; cit != end; ++cit) { - int const cv = cit->vertex; - if (!visited_[cv]) { - visited_[cv] = true; - Q_.push(cv); + int const cv = (*cit)->to; + if (!vertices_[cv].visited) { + vertices_[cv].visited = true; + Q.push(cv); } } } @@ -140,69 +153,85 @@ bool Graph::isReachable(int from, int to) Graph::EdgePath const Graph::getPath(int from, int to) { - EdgePath path; if (from == to) - return path; - - if (to < 0 || !bfs_init(from)) - return path; + return EdgePath(); - // pair - vector > prev(vertices_.size()); + queue Q; + if (to < 0 || !bfs_init(from, true, Q)) + return EdgePath(); - bool found = false; - while (!Q_.empty()) { - int const current = Q_.front(); - Q_.pop(); - if (current == to) { - found = true; - break; - } + vector pathes; + pathes.resize(vertices_.size()); + while (!Q.empty()) { + int const current = Q.front(); + Q.pop(); - vector::const_iterator const beg = + vector::const_iterator cit = vertices_[current].out_arrows.begin(); - vector::const_iterator cit = beg; - vector::const_iterator end = + vector::const_iterator end = vertices_[current].out_arrows.end(); for (; cit != end; ++cit) { - int const cv = cit->vertex; - if (!visited_[cv]) { - visited_[cv] = true; - Q_.push(cv); - // FIXME This will not do for finding multiple paths. - // Perhaps we need a vector, or a set. - prev[cv] = pair(current, cit->edge); + int const cv = (*cit)->to; + if (!vertices_[cv].visited) { + vertices_[cv].visited = true; + Q.push(cv); + // NOTE If we wanted to collect all the paths, then + // we just need to collect them here and not worry + // about "visited". + EdgePath lastpath = pathes[(*cit)->from]; + lastpath.push_back((*cit)->id); + pathes[cv] = lastpath; + } + if (cv == to) { + return pathes[cv]; } } } - if (!found) - return path; - - while (to != from) { - path.push_back(prev[to].second); - to = prev[to].first; - } - reverse(path.begin(), path.end()); - return path; + // failure + return EdgePath(); } void Graph::init(int size) { vertices_ = vector(size); - visited_.resize(size); + arrows_.clear(); numedges_ = 0; } void Graph::addEdge(int from, int to) { - vertices_[to].in_vertices.push_back(from); - vertices_[from].out_arrows.push_back(OutEdge(to, numedges_++)); + arrows_.push_back(Arrow(from, to, numedges_)); + numedges_++; + Arrow * ar = &(arrows_.back()); + vertices_[to].in_arrows.push_back(ar); + vertices_[from].out_arrows.push_back(ar); } -vector Graph::vertices_; +// At present, we do not need this debugging code, but +// I am going to leave it here in case we need it again. +#if 0 +void Graph::dumpGraph() const +{ + vector::const_iterator it = vertices_.begin(); + vector::const_iterator en = vertices_.end(); + for (; it != en; ++it) { + LYXERR0("Next vertex..."); + LYXERR0("In arrows..."); + std::vector::const_iterator iit = it->in_arrows.begin(); + std::vector::const_iterator ien = it->in_arrows.end(); + for (; iit != ien; ++iit) + LYXERR0("From " << (*iit)->from << " to " << (*iit)->to); + LYXERR0("Out arrows..."); + iit = it->out_arrows.begin(); + ien = it->out_arrows.end(); + for (; iit != ien; ++iit) + LYXERR0("From " << (*iit)->from << " to " << (*iit)->to); + } +} +#endif } // namespace lyx