X-Git-Url: https://git.lyx.org/gitweb/?a=blobdiff_plain;f=src%2FGraph.cpp;h=0165bdacc9a4c95d626f21996f83f010c1a52959;hb=4e50da3e655b9f8d26f7d5e439d72b219d32279d;hp=d30e3d4999fffd31211f2d510b9ba0c96fb6fe38;hpb=af0c9adc389feda32304aeeb3777cc218b6ee4c3;p=lyx.git diff --git a/src/Graph.cpp b/src/Graph.cpp index d30e3d4999..0165bdacc9 100644 --- a/src/Graph.cpp +++ b/src/Graph.cpp @@ -4,7 +4,7 @@ * Licence details can be found in the file COPYING. * * \author Dekel Tsur (original code) - * \author Richard Heck (re-implementation) + * \author Richard Kimberly Heck (re-implementation) * * Full author contact details are available in file CREDITS. */ @@ -17,19 +17,18 @@ #include "support/debug.h" #include "support/lassert.h" -#include - 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(); @@ -38,39 +37,31 @@ 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; } -void Graph::clearMarks() -{ - Arrows::iterator it = arrows_.begin(); - Arrows::iterator const en = arrows_.end(); - for (; it != en; ++it) - it->marked = false; -} - - -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 + // 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. That makes it a breadth-first // search. - while (!Q_.empty()) { - int const current = Q_.front(); - Q_.pop(); - if (current != target || formats.get(target).name() != "lyx") + 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_arrows.begin(); @@ -79,7 +70,7 @@ vector const const int cv = (*it)->from; if (!vertices_[cv].visited) { vertices_[cv].visited = true; - Q_.push(cv); + Q.push(cv); } } } @@ -88,23 +79,24 @@ 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); } @@ -117,7 +109,8 @@ vector const 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); } } } @@ -131,12 +124,13 @@ 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; @@ -148,7 +142,7 @@ bool Graph::isReachable(int from, int to) int const cv = (*cit)->to; if (!vertices_[cv].visited) { vertices_[cv].visited = true; - Q_.push(cv); + Q.push(cv); } } } @@ -159,77 +153,45 @@ 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; - - // In effect, the way this works is that we construct a sub-graph - // by starting at "from" and following the arrows outward. Instead - // of actually constructing a sub-graph, though, we "mark" the - // arrows we traverse as we go. Once we hit "to", we abort the - // marking process and then call getMarkedPath() to reconstruct - // the marked path. - bool found = false; - clearMarks(); - while (!Q_.empty()) { - int const current = Q_.front(); - Q_.pop(); - - vector::const_iterator const beg = + return EdgePath(); + + queue Q; + if (to < 0 || !bfs_init(from, true, Q)) + return EdgePath(); + + vector pathes; + pathes.resize(vertices_.size()); + while (!Q.empty()) { + int const current = Q.front(); + Q.pop(); + + vector::const_iterator cit = vertices_[current].out_arrows.begin(); - vector::const_iterator cit = beg; vector::const_iterator end = vertices_[current].out_arrows.end(); for (; cit != end; ++cit) { int const cv = (*cit)->to; if (!vertices_[cv].visited) { vertices_[cv].visited = true; - Q_.push(cv); - (*cit)->marked = 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) { - found = true; - break; + return pathes[cv]; } } } - if (!found) - return path; - - getMarkedPath(from, to, path); - return path; + // failure + return EdgePath(); } -// We assume we have marked the graph, as in getPath(). We also -// assume that we have done so in such a way as to guarantee a -// marked path from "from" to "to". -// We then start at "to" and find the arrow leading to it that -// has been marked. We add that to the path we are constructing, -// step back on that arrow, and continue the process (i.e., recurse). -void Graph::getMarkedPath(int from, int to, EdgePath & path) { - if (from == to) { - reverse(path.begin(), path.end()); - return; - } - // find marked in_arrow - vector::const_iterator it = vertices_[to].in_arrows.begin(); - vector::const_iterator en = vertices_[to].in_arrows.end(); - for (; it != en; ++it) - if ((*it)->marked) - break; - if (it == en) { - LASSERT(false, /* */); - return; - } - path.push_back((*it)->id); - getMarkedPath(from, (*it)->from, path); -} - - void Graph::init(int size) { vertices_ = vector(size); @@ -248,4 +210,28 @@ void Graph::addEdge(int from, int to) } +// 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