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 const beg =
182 vertices_[current].out_arrows.begin();
183 vector<Arrow *>::const_iterator cit = beg;
184 vector<Arrow *>::const_iterator end =
185 vertices_[current].out_arrows.end();
186 for (; cit != end; ++cit) {
187 int const cv = (*cit)->to;
188 if (!vertices_[cv].visited) {
189 vertices_[cv].visited = true;
191 (*cit)->marked = true;
202 getMarkedPath(from, to, path);
207 // We assume we have marked the graph, as in getPath(). We also
208 // assume that we have done so in such a way as to guarantee a
209 // marked path from "from" to "to".
210 // We then start at "to" and find the arrow leading to it that
211 // has been marked. We add that to the path we are constructing,
212 // step back on that arrow, and continue the process (i.e., recurse).
213 void Graph::getMarkedPath(int from, int to, EdgePath & path) {
215 reverse(path.begin(), path.end());
218 // find marked in_arrow
219 vector<Arrow *>::const_iterator it = vertices_[to].in_arrows.begin();
220 vector<Arrow *>::const_iterator en = vertices_[to].in_arrows.end();
221 for (; it != en; ++it)
225 LASSERT(false, /* */);
228 path.push_back((*it)->id);
229 getMarkedPath(from, (*it)->from, path);
233 void Graph::init(int size)
235 vertices_ = vector<Vertex>(size);
241 void Graph::addEdge(int from, int to)
243 arrows_.push_back(Arrow(from, to, numedges_));
245 Arrow * ar = &(arrows_.back());
246 vertices_[to].in_arrows.push_back(ar);
247 vertices_[from].out_arrows.push_back(ar);