X-Git-Url: https://git.lyx.org/gitweb/?a=blobdiff_plain;f=src%2FGraph.cpp;h=d30e3d4999fffd31211f2d510b9ba0c96fb6fe38;hb=ce2e071cdfde88864c1524818d66cbae52273502;hp=78e9f27954b82e5fd1deb39dd670537bd32d8f84;hpb=31d932df897c49b85fd91f4f662c799ec944d92a;p=lyx.git diff --git a/src/Graph.cpp b/src/Graph.cpp index 78e9f27954..d30e3d4999 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; @@ -22,41 +26,60 @@ namespace lyx { bool Graph::bfs_init(int s, bool clear_visited) { - if (s < 0 || s >= vertices_.size()) + if (s < 0) return false; Q_ = queue(); - if (clear_visited) - fill(visited_.begin(), visited_.end(), false); - if (visited_[s] == false) { + 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); - visited_[s] = true; + 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::getReachableTo(int target, bool clear_visited) { vector result; if (!bfs_init(target, clear_visited)) 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 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 i = Q_.front(); + int const current = Q_.front(); Q_.pop(); - if (i != target || formats.get(target).name() != "lyx") { - result.push_back(i); - } + if (current != target || formats.get(target).name() != "lyx") + result.push_back(current); - vector::iterator it = vertices_[i].in_vertices.begin(); - vector::iterator end = vertices_[i].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); } } } @@ -66,35 +89,37 @@ Graph::getReachableTo(int target, bool clear_visited) vector const -Graph::getReachable(int from, bool only_viewable, - bool clear_visited) + Graph::getReachable(int from, bool only_viewable, + bool clear_visited) { vector result; if (!bfs_init(from, clear_visited)) return result; while (!Q_.empty()) { - int const i = Q_.front(); + int const current = Q_.front(); Q_.pop(); - Format const & format = formats.get(i); + Format const & format = formats.get(current); if (!only_viewable || !format.viewer().empty()) - result.push_back(i); + result.push_back(current); else if (format.isChildFormat()) { Format const * const parent = formats.getFormat(format.parentFormat()); if (parent && !parent->viewer().empty()) - result.push_back(i); + result.push_back(current); } - vector::const_iterator cit = - vertices_[i].out_vertices.begin(); - vector::const_iterator end = - vertices_[i].out_vertices.end(); - for (; cit != end; ++cit) - if (!visited_[*cit]) { - visited_[*cit] = true; - Q_.push(*cit); + vector::const_iterator cit = + vertices_[current].out_arrows.begin(); + 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); } + } } return result; @@ -106,7 +131,7 @@ bool Graph::isReachable(int from, int to) if (from == to) return true; - if (to < 0 || to >= vertices_.size() || !bfs_init(from)) + if (to < 0 || !bfs_init(from)) return false; while (!Q_.empty()) { @@ -115,14 +140,15 @@ bool Graph::isReachable(int from, int to) if (current == to) return true; - vector::const_iterator cit = - vertices_[current].out_vertices.begin(); - vector::const_iterator end = - vertices_[current].out_vertices.end(); + vector::const_iterator cit = + vertices_[current].out_arrows.begin(); + vector::const_iterator end = + vertices_[current].out_arrows.end(); for (; cit != end; ++cit) { - if (!visited_[*cit]) { - visited_[*cit] = true; - Q_.push(*cit); + int const cv = (*cit)->to; + if (!vertices_[cv].visited) { + vertices_[cv].visited = true; + Q_.push(cv); } } } @@ -137,65 +163,89 @@ Graph::EdgePath const Graph::getPath(int from, int to) if (from == to) return path; - if (to < 0 || to >= vertices_.size() || !bfs_init(from)) + if (to < 0 || !bfs_init(from)) return path; - vector prev_edge(formats.size()); - vector prev_vertex(formats.size()); - + // 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(); - if (current == to) { - found = true; - break; - } - vector::const_iterator const beg = - vertices_[current].out_vertices.begin(); - vector::const_iterator cit = beg; - vector::const_iterator end = - vertices_[current].out_vertices.end(); - for (; cit != end; ++cit) - if (!visited_[*cit]) { - int const j = *cit; - visited_[j] = true; - Q_.push(j); - int const k = cit - beg; - prev_edge[j] = vertices_[current].out_edges[k]; - prev_vertex[j] = current; + vector::const_iterator const beg = + 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; + } + if (cv == to) { + found = true; + break; } + } } if (!found) return path; - while (to != from) { - path.push_back(prev_edge[to]); - to = prev_vertex[to]; - } - reverse(path.begin(), path.end()); + getMarkedPath(from, to, path); return path; } +// 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); - visited_.resize(size); + arrows_.clear(); numedges_ = 0; } void Graph::addEdge(int from, int to) { - vertices_[to].in_vertices.push_back(from); - vertices_[from].out_vertices.push_back(to); - vertices_[from].out_edges.push_back(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_; - - } // namespace lyx