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 Kimberly Heck (re-implementation)
9 * Full author contact details are available in file CREDITS.
17 #include "support/debug.h"
18 #include "support/lassert.h"
25 bool Graph::bfs_init(int s, bool clear_visited, queue<int> & Q)
34 vector<Vertex>::iterator it = vertices_.begin();
35 vector<Vertex>::iterator en = vertices_.end();
36 for (; it != en; ++it)
39 if (!vertices_[s].visited) {
41 vertices_[s].visited = true;
48 Graph::getReachableTo(int to, bool clear_visited)
52 if (!bfs_init(to, clear_visited, Q))
55 // Here's the logic, which is shared by the other routines.
56 // Q holds a list of nodes we have been able to reach (in this
57 // case, reach backwards). It is initialized to the current node
58 // by bfs_init, and then we recurse, adding the nodes we can reach
59 // from the current node as we go. That makes it a breadth-first
62 int const current = Q.front();
64 if (current != to || theFormats().get(to).name() != "lyx")
65 result.push_back(current);
67 vector<Arrow *>::iterator it = vertices_[current].in_arrows.begin();
68 vector<Arrow *>::iterator const end = vertices_[current].in_arrows.end();
69 for (; it != end; ++it) {
70 const int cv = (*it)->from;
71 if (!vertices_[cv].visited) {
72 vertices_[cv].visited = true;
83 Graph::getReachable(int from, bool only_viewable,
84 bool clear_visited, set<int> excludes)
88 if (!bfs_init(from, clear_visited, Q))
92 int const current = Q.front();
94 Format const & format = theFormats().get(current);
95 if (!only_viewable || !format.viewer().empty())
96 result.push_back(current);
97 else if (format.isChildFormat()) {
98 Format const * const parent =
99 theFormats().getFormat(format.parentFormat());
100 if (parent && !parent->viewer().empty())
101 result.push_back(current);
104 vector<Arrow *>::const_iterator cit =
105 vertices_[current].out_arrows.begin();
106 vector<Arrow *>::const_iterator end =
107 vertices_[current].out_arrows.end();
108 for (; cit != end; ++cit) {
109 int const cv = (*cit)->to;
110 if (!vertices_[cv].visited) {
111 vertices_[cv].visited = true;
112 if (excludes.find(cv) == excludes.end())
122 bool Graph::isReachable(int from, int to)
128 if (to < 0 || !bfs_init(from, true, Q))
132 int const current = Q.front();
137 vector<Arrow *>::const_iterator cit =
138 vertices_[current].out_arrows.begin();
139 vector<Arrow *>::const_iterator end =
140 vertices_[current].out_arrows.end();
141 for (; cit != end; ++cit) {
142 int const cv = (*cit)->to;
143 if (!vertices_[cv].visited) {
144 vertices_[cv].visited = true;
154 Graph::EdgePath const Graph::getPath(int from, int to)
160 if (to < 0 || !bfs_init(from, true, Q))
163 vector<EdgePath> pathes;
164 pathes.resize(vertices_.size());
166 int const current = Q.front();
169 vector<Arrow *>::const_iterator cit =
170 vertices_[current].out_arrows.begin();
171 vector<Arrow *>::const_iterator end =
172 vertices_[current].out_arrows.end();
173 for (; cit != end; ++cit) {
174 int const cv = (*cit)->to;
175 if (!vertices_[cv].visited) {
176 vertices_[cv].visited = true;
178 // NOTE If we wanted to collect all the paths, then
179 // we just need to collect them here and not worry
181 EdgePath lastpath = pathes[(*cit)->from];
182 lastpath.push_back((*cit)->id);
183 pathes[cv] = lastpath;
195 void Graph::init(int size)
197 vertices_ = vector<Vertex>(size);
203 void Graph::addEdge(int from, int to)
205 arrows_.push_back(Arrow(from, to, numedges_));
207 Arrow * ar = &(arrows_.back());
208 vertices_[to].in_arrows.push_back(ar);
209 vertices_[from].out_arrows.push_back(ar);
213 // At present, we do not need this debugging code, but
214 // I am going to leave it here in case we need it again.
216 void Graph::dumpGraph() const
218 vector<Vertex>::const_iterator it = vertices_.begin();
219 vector<Vertex>::const_iterator en = vertices_.end();
220 for (; it != en; ++it) {
221 LYXERR0("Next vertex...");
222 LYXERR0("In arrows...");
223 std::vector<Arrow *>::const_iterator iit = it->in_arrows.begin();
224 std::vector<Arrow *>::const_iterator ien = it->in_arrows.end();
225 for (; iit != ien; ++iit)
226 LYXERR0("From " << (*iit)->from << " to " << (*iit)->to);
227 LYXERR0("Out arrows...");
228 iit = it->out_arrows.begin();
229 ien = it->out_arrows.end();
230 for (; iit != ien; ++iit)
231 LYXERR0("From " << (*iit)->from << " to " << (*iit)->to);