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 || theFormats().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, set<int> excludes)
90 if (!bfs_init(from, clear_visited, Q))
94 int const current = Q.front();
96 Format const & format = theFormats().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 theFormats().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 (excludes.find(cv) == excludes.end())
124 bool Graph::isReachable(int from, int to)
130 if (to < 0 || !bfs_init(from, true, Q))
134 int const current = Q.front();
139 vector<Arrow *>::const_iterator cit =
140 vertices_[current].out_arrows.begin();
141 vector<Arrow *>::const_iterator end =
142 vertices_[current].out_arrows.end();
143 for (; cit != end; ++cit) {
144 int const cv = (*cit)->to;
145 if (!vertices_[cv].visited) {
146 vertices_[cv].visited = true;
156 Graph::EdgePath const Graph::getPath(int from, int to)
162 if (to < 0 || !bfs_init(from, true, Q))
165 vector<EdgePath> pathes;
166 pathes.resize(vertices_.size());
168 int const current = Q.front();
171 vector<Arrow *>::const_iterator cit =
172 vertices_[current].out_arrows.begin();
173 vector<Arrow *>::const_iterator end =
174 vertices_[current].out_arrows.end();
175 for (; cit != end; ++cit) {
176 int const cv = (*cit)->to;
177 if (!vertices_[cv].visited) {
178 vertices_[cv].visited = true;
180 // NOTE If we wanted to collect all the paths, then
181 // we just need to collect them here and not worry
183 EdgePath lastpath = pathes[(*cit)->from];
184 lastpath.push_back((*cit)->id);
185 pathes[cv] = lastpath;
197 void Graph::init(int size)
199 vertices_ = vector<Vertex>(size);
205 void Graph::addEdge(int from, int to)
207 arrows_.push_back(Arrow(from, to, numedges_));
209 Arrow * ar = &(arrows_.back());
210 vertices_[to].in_arrows.push_back(ar);
211 vertices_[from].out_arrows.push_back(ar);
215 // At present, we do not need this debugging code, but
216 // I am going to leave it here in case we need it again.
218 void Graph::dumpGraph() const
220 vector<Vertex>::const_iterator it = vertices_.begin();
221 vector<Vertex>::const_iterator en = vertices_.end();
222 for (; it != en; ++it) {
223 LYXERR0("Next vertex...");
224 LYXERR0("In arrows...");
225 std::vector<Arrow *>::const_iterator iit = it->in_arrows.begin();
226 std::vector<Arrow *>::const_iterator ien = it->in_arrows.end();
227 for (; iit != ien; ++iit)
228 LYXERR0("From " << (*iit)->from << " to " << (*iit)->to);
229 LYXERR0("Out arrows...");
230 iit = it->out_arrows.begin();
231 ien = it->out_arrows.end();
232 for (; iit != ien; ++iit)
233 LYXERR0("From " << (*iit)->from << " to " << (*iit)->to);