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, queue<int> & Q)
36 vector<Vertex>::iterator it = vertices_.begin();
37 vector<Vertex>::iterator en = vertices_.end();
38 for (; it != en; ++it)
41 if (!vertices_[s].visited) {
43 vertices_[s].visited = true;
50 Graph::getReachableTo(int target, bool clear_visited)
54 if (!bfs_init(target, clear_visited, Q))
57 // Here's the logic, which is shared by the other routines.
58 // Q holds a list of nodes we have been able to reach (in this
59 // case, reach backwards). It is initialized to the current node
60 // by bfs_init, and then we recurse, adding the nodes we can reach
61 // from the current node as we go. That makes it a breadth-first
64 int const current = Q.front();
66 if (current != target || formats.get(target).name() != "lyx")
67 result.push_back(current);
69 vector<Arrow *>::iterator it = vertices_[current].in_arrows.begin();
70 vector<Arrow *>::iterator const end = vertices_[current].in_arrows.end();
71 for (; it != end; ++it) {
72 const int cv = (*it)->from;
73 if (!vertices_[cv].visited) {
74 vertices_[cv].visited = true;
85 Graph::getReachable(int from, bool only_viewable,
86 bool clear_visited, vector<int> excludes)
90 if (!bfs_init(from, clear_visited, Q))
94 int const current = Q.front();
96 Format const & format = formats.get(current);
97 if (!only_viewable || !format.viewer().empty())
98 result.push_back(current);
99 else if (format.isChildFormat()) {
100 Format const * const parent =
101 formats.getFormat(format.parentFormat());
102 if (parent && !parent->viewer().empty())
103 result.push_back(current);
106 vector<Arrow *>::const_iterator cit =
107 vertices_[current].out_arrows.begin();
108 vector<Arrow *>::const_iterator end =
109 vertices_[current].out_arrows.end();
110 for (; cit != end; ++cit) {
111 int const cv = (*cit)->to;
112 if (!vertices_[cv].visited) {
113 vertices_[cv].visited = true;
114 if (find(excludes.begin(), excludes.end(), cv) == excludes.end())
124 Graph::EdgePath const
125 Graph::getReachable(int from, bool only_viewable,
126 bool clear_visited, int exclude)
128 vector<int> excludes;
129 excludes.push_back(exclude);
130 return getReachable(from, only_viewable, clear_visited, excludes);
134 Graph::EdgePath const
135 Graph::getReachable(int from, bool only_viewable,
138 vector<int> excludes;
139 return getReachable(from, only_viewable, clear_visited, excludes);
143 bool Graph::isReachable(int from, int to)
149 if (to < 0 || !bfs_init(from, true, Q))
153 int const current = Q.front();
158 vector<Arrow *>::const_iterator cit =
159 vertices_[current].out_arrows.begin();
160 vector<Arrow *>::const_iterator end =
161 vertices_[current].out_arrows.end();
162 for (; cit != end; ++cit) {
163 int const cv = (*cit)->to;
164 if (!vertices_[cv].visited) {
165 vertices_[cv].visited = true;
175 Graph::EdgePath const Graph::getPath(int from, int to)
181 if (to < 0 || !bfs_init(from, true, Q))
184 vector<EdgePath> pathes;
185 pathes.resize(vertices_.size());
187 int const current = Q.front();
190 vector<Arrow *>::const_iterator cit =
191 vertices_[current].out_arrows.begin();
192 vector<Arrow *>::const_iterator end =
193 vertices_[current].out_arrows.end();
194 for (; cit != end; ++cit) {
195 int const cv = (*cit)->to;
196 if (!vertices_[cv].visited) {
197 vertices_[cv].visited = true;
199 // NOTE If we wanted to collect all the paths, then
200 // we just need to collect them here and not worry
202 EdgePath lastpath = pathes[(*cit)->from];
203 lastpath.push_back((*cit)->id);
204 pathes[cv] = lastpath;
216 void Graph::init(int size)
218 vertices_ = vector<Vertex>(size);
224 void Graph::addEdge(int from, int to)
226 arrows_.push_back(Arrow(from, to, numedges_));
228 Arrow * ar = &(arrows_.back());
229 vertices_[to].in_arrows.push_back(ar);
230 vertices_[from].out_arrows.push_back(ar);
234 // At present, we do not need this debugging code, but
235 // I am going to leave it here in case we need it again.
237 void Graph::dumpGraph() const
239 vector<Vertex>::const_iterator it = vertices_.begin();
240 vector<Vertex>::const_iterator en = vertices_.end();
241 for (; it != en; ++it) {
242 LYXERR0("Next vertex...");
243 LYXERR0("In arrows...");
244 std::vector<Arrow *>::const_iterator iit = it->in_arrows.begin();
245 std::vector<Arrow *>::const_iterator ien = it->in_arrows.end();
246 for (; iit != ien; ++iit)
247 LYXERR0("From " << (*iit)->from << " to " << (*iit)->to);
248 LYXERR0("Out arrows...");
249 iit = it->out_arrows.begin();
250 ien = it->out_arrows.end();
251 for (; iit != ien; ++iit)
252 LYXERR0("From " << (*iit)->from << " to " << (*iit)->to);