X-Git-Url: https://git.lyx.org/gitweb/?a=blobdiff_plain;f=src%2FGraph.cpp;h=d30e3d4999fffd31211f2d510b9ba0c96fb6fe38;hb=f37a1b8aeaf8f3a3a66a22bf0b396f7d1ceca2ff;hp=cf5c8559c3b2948b26a6d2c9273d215990fca156;hpb=dfbbb87e0b2fcc2b711bd50c8205dd21a6df1732;p=lyx.git diff --git a/src/Graph.cpp b/src/Graph.cpp index cf5c8559c3..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; @@ -27,16 +31,29 @@ bool Graph::bfs_init(int s, bool clear_visited) 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) { @@ -44,18 +61,25 @@ vector const 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 current = Q_.front(); Q_.pop(); if (current != target || formats.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 (!visited_[*it]) { - visited_[*it] = true; - Q_.push(*it); + const int cv = (*it)->from; + if (!vertices_[cv].visited) { + vertices_[cv].visited = true; + Q_.push(cv); } } } @@ -85,14 +109,14 @@ vector const 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; + int const cv = (*cit)->to; + if (!vertices_[cv].visited) { + vertices_[cv].visited = true; Q_.push(cv); } } @@ -116,14 +140,14 @@ bool Graph::isReachable(int from, int to) 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; + int const cv = (*cit)->to; + if (!vertices_[cv].visited) { + vertices_[cv].visited = true; Q_.push(cv); } } @@ -142,61 +166,86 @@ Graph::EdgePath const Graph::getPath(int from, int to) 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 = + vector::const_iterator const beg = vertices_[current].out_arrows.begin(); - vector::const_iterator cit = beg; - vector::const_iterator end = + vector::const_iterator cit = beg; + vector::const_iterator end = vertices_[current].out_arrows.end(); for (; cit != end; ++cit) { - int const cv = cit->vertex; - if (!visited_[cv]) { - visited_[cv] = true; + int const cv = (*cit)->to; + if (!vertices_[cv].visited) { + vertices_[cv].visited = true; Q_.push(cv); - prev_edge[cv] = cit->edge; - prev_vertex[cv] = current; + (*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_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_; - - } // namespace lyx