3 * This file is part of LyX, the document processor.
4 * Licence details can be found in the file COPYING.
6 * \author Dekel Tsur (original code)
7 * \author Richard Heck (re-implementation)
9 * Full author contact details are available in file CREDITS.
17 #include "support/debug.h"
18 #include "support/lassert.h"
27 bool Graph::bfs_init(int s, bool clear_visited)
35 vector<Vertex>::iterator it = vertices_.begin();
36 vector<Vertex>::iterator en = vertices_.end();
37 for (; it != en; ++it)
40 if (!vertices_[s].visited) {
42 vertices_[s].visited = true;
48 void Graph::clearMarks()
50 Arrows::iterator it = arrows_.begin();
51 Arrows::iterator const en = arrows_.end();
52 for (; it != en; ++it)
58 Graph::getReachableTo(int target, bool clear_visited)
61 if (!bfs_init(target, clear_visited))
64 // Here's the logic, which is shared by the other routines.
65 // Q_ holds a list of nodes we have been able to reach (in this
66 // case, reach backwards). It is initialized to the current node
67 // by bfs_init, and then we recurse, adding the nodes we can reach
68 // from the current node as we go. That makes it a breadth-first
71 int const current = Q_.front();
73 if (current != target || formats.get(target).name() != "lyx")
74 result.push_back(current);
76 vector<Arrow *>::iterator it = vertices_[current].in_arrows.begin();
77 vector<Arrow *>::iterator const end = vertices_[current].in_arrows.end();
78 for (; it != end; ++it) {
79 const int cv = (*it)->from;
80 if (!vertices_[cv].visited) {
81 vertices_[cv].visited = true;
92 Graph::getReachable(int from, bool only_viewable,
96 if (!bfs_init(from, clear_visited))
100 int const current = Q_.front();
102 Format const & format = formats.get(current);
103 if (!only_viewable || !format.viewer().empty())
104 result.push_back(current);
105 else if (format.isChildFormat()) {
106 Format const * const parent =
107 formats.getFormat(format.parentFormat());
108 if (parent && !parent->viewer().empty())
109 result.push_back(current);
112 vector<Arrow *>::const_iterator cit =
113 vertices_[current].out_arrows.begin();
114 vector<Arrow *>::const_iterator end =
115 vertices_[current].out_arrows.end();
116 for (; cit != end; ++cit) {
117 int const cv = (*cit)->to;
118 if (!vertices_[cv].visited) {
119 vertices_[cv].visited = true;
129 bool Graph::isReachable(int from, int to)
134 if (to < 0 || !bfs_init(from))
137 while (!Q_.empty()) {
138 int const current = Q_.front();
143 vector<Arrow *>::const_iterator cit =
144 vertices_[current].out_arrows.begin();
145 vector<Arrow *>::const_iterator end =
146 vertices_[current].out_arrows.end();
147 for (; cit != end; ++cit) {
148 int const cv = (*cit)->to;
149 if (!vertices_[cv].visited) {
150 vertices_[cv].visited = true;
160 Graph::EdgePath const Graph::getPath(int from, int to)
166 if (to < 0 || !bfs_init(from))
169 // In effect, the way this works is that we construct a sub-graph
170 // by starting at "from" and following the arrows outward. Instead
171 // of actually constructing a sub-graph, though, we "mark" the
172 // arrows we traverse as we go. Once we hit "to", we abort the
173 // marking process and then call getMarkedPath() to reconstruct
177 while (!Q_.empty()) {
178 int const current = Q_.front();
181 vector<Arrow *>::const_iterator cit =
182 vertices_[current].out_arrows.begin();
183 vector<Arrow *>::const_iterator end =
184 vertices_[current].out_arrows.end();
185 for (; cit != end; ++cit) {
186 int const cv = (*cit)->to;
187 if (!vertices_[cv].visited) {
188 vertices_[cv].visited = true;
190 (*cit)->marked = true;
201 getMarkedPath(from, to, path);
206 // We assume we have marked the graph, as in getPath(). We also
207 // assume that we have done so in such a way as to guarantee a
208 // marked path from "from" to "to".
209 // We then start at "to" and find the arrow leading to it that
210 // has been marked. We add that to the path we are constructing,
211 // step back on that arrow, and continue the process (i.e., recurse).
212 void Graph::getMarkedPath(int from, int to, EdgePath & path) {
214 reverse(path.begin(), path.end());
217 // find marked in_arrow
218 vector<Arrow *>::const_iterator it = vertices_[to].in_arrows.begin();
219 vector<Arrow *>::const_iterator const en = vertices_[to].in_arrows.end();
220 for (; it != en; ++it)
224 // debug code to try to figure out what's up.
225 LYXERR0("Failed to find marked arrow.\n"
226 "From: " << from << ", To: " << to);
228 LASSERT(false, /* */);
231 path.push_back((*it)->id);
232 getMarkedPath(from, (*it)->from, path);
236 void Graph::init(int size)
238 vertices_ = vector<Vertex>(size);
244 void Graph::addEdge(int from, int to)
246 arrows_.push_back(Arrow(from, to, numedges_));
248 Arrow * ar = &(arrows_.back());
249 vertices_[to].in_arrows.push_back(ar);
250 vertices_[from].out_arrows.push_back(ar);
254 void Graph::dumpGraph() const
256 vector<Vertex>::const_iterator it = vertices_.begin();
257 vector<Vertex>::const_iterator en = vertices_.end();
258 for (; it != en; ++it) {
259 LYXERR0("Next vertex...");
260 LYXERR0("In arrows...");
261 std::vector<Arrow *>::const_iterator iit = it->in_arrows.begin();
262 std::vector<Arrow *>::const_iterator ien = it->in_arrows.end();
263 for (; iit != ien; ++iit)
264 LYXERR0("From " << (*iit)->from << " to " << (*iit)->to
265 << ". Marked: " << (*iit)->marked);
266 LYXERR0("Out arrows...");
267 iit = it->out_arrows.begin();
268 ien = it->out_arrows.end();
269 for (; iit != ien; ++iit)
270 LYXERR0("From " << (*iit)->from << " to " << (*iit)->to
271 << ". Marked: " << (*iit)->marked);