X-Git-Url: https://git.lyx.org/gitweb/?a=blobdiff_plain;ds=sidebyside;f=src%2FGraph.cpp;h=0573cd2162bdcba8bbf80083305ef9e818da98aa;hb=28be7d552f62cc02fa86d7f79201d089bfb2d7b5;hp=344fa6300eff624158412c92405a8b36522413cf;hpb=66a9bdb2915894c7440eaf44db90ce9171118fd7;p=lyx.git diff --git a/src/Graph.cpp b/src/Graph.cpp index 344fa6300e..0573cd2162 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 Heck (re-implementation) * * Full author contact details are available in file CREDITS. */ @@ -13,6 +14,9 @@ #include "Graph.h" #include "Format.h" +#include "support/debug.h" +#include "support/lassert.h" + #include using namespace std; @@ -20,12 +24,13 @@ 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) { vector::iterator it = vertices_.begin(); @@ -34,37 +39,40 @@ bool Graph::bfs_init(int s, bool clear_visited) it->visited = false; } if (!vertices_[s].visited) { - Q_.push(s); + Q.push(s); vertices_[s].visited = true; } return true; } -vector const +Graph::EdgePath const Graph::getReachableTo(int target, bool clear_visited) { - vector result; - if (!bfs_init(target, clear_visited)) + EdgePath result; + queue Q; + if (!bfs_init(target, 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 != target || theFormats().get(target).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 (!vertices_[*it].visited) { - vertices_[*it].visited = true; - Q_.push(*it); + const int cv = (*it)->from; + if (!vertices_[cv].visited) { + vertices_[cv].visited = true; + Q.push(cv); } } } @@ -73,36 +81,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; + int const cv = (*cit)->to; if (!vertices_[cv].visited) { vertices_[cv].visited = true; - Q_.push(cv); + if (excludes.find(cv) == excludes.end()) + Q.push(cv); } } } @@ -116,24 +126,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; + int const cv = (*cit)->to; if (!vertices_[cv].visited) { vertices_[cv].visited = true; - Q_.push(cv); + Q.push(cv); } } } @@ -144,67 +155,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(); + 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; + int const cv = (*cit)->to; if (!vertices_[cv].visited) { vertices_[cv].visited = true; - Q_.push(cv); - // FIXME This will not do for finding multiple paths. - // Perhaps we need a vector, or a set. We'll also want - // to add this info, even if the node is visited, so - // outside this conditional. - prev[cv] = pair(current, cit->edge); + 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) { - found = true; - break; + 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); + 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); +} + + +// 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