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,
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;
123 bool Graph::isReachable(int from, int to)
129 if (to < 0 || !bfs_init(from, true, Q))
133 int const current = Q.front();
138 vector<Arrow *>::const_iterator cit =
139 vertices_[current].out_arrows.begin();
140 vector<Arrow *>::const_iterator end =
141 vertices_[current].out_arrows.end();
142 for (; cit != end; ++cit) {
143 int const cv = (*cit)->to;
144 if (!vertices_[cv].visited) {
145 vertices_[cv].visited = true;
155 Graph::EdgePath const Graph::getPath(int from, int to)
161 if (to < 0 || !bfs_init(from, true, Q))
164 vector<EdgePath> pathes;
165 pathes.resize(vertices_.size());
167 int const current = Q.front();
170 vector<Arrow *>::const_iterator cit =
171 vertices_[current].out_arrows.begin();
172 vector<Arrow *>::const_iterator end =
173 vertices_[current].out_arrows.end();
174 for (; cit != end; ++cit) {
175 int const cv = (*cit)->to;
176 if (!vertices_[cv].visited) {
177 vertices_[cv].visited = true;
179 // NOTE If we wanted to collect all the paths, then
180 // we just need to collect them here and not worry
182 EdgePath lastpath = pathes[(*cit)->from];
183 lastpath.push_back((*cit)->id);
184 pathes[cv] = lastpath;
196 void Graph::init(int size)
198 vertices_ = vector<Vertex>(size);
204 void Graph::addEdge(int from, int to)
206 arrows_.push_back(Arrow(from, to, numedges_));
208 Arrow * ar = &(arrows_.back());
209 vertices_[to].in_arrows.push_back(ar);
210 vertices_[from].out_arrows.push_back(ar);
214 // At present, we do not need this debugging code, but
215 // I am going to leave it here in case we need it again.
217 void Graph::dumpGraph() const
219 vector<Vertex>::const_iterator it = vertices_.begin();
220 vector<Vertex>::const_iterator en = vertices_.end();
221 for (; it != en; ++it) {
222 LYXERR0("Next vertex...");
223 LYXERR0("In arrows...");
224 std::vector<Arrow *>::const_iterator iit = it->in_arrows.begin();
225 std::vector<Arrow *>::const_iterator ien = it->in_arrows.end();
226 for (; iit != ien; ++iit)
227 LYXERR0("From " << (*iit)->from << " to " << (*iit)->to);
228 LYXERR0("Out arrows...");
229 iit = it->out_arrows.begin();
230 ien = it->out_arrows.end();
231 for (; iit != ien; ++iit)
232 LYXERR0("From " << (*iit)->from << " to " << (*iit)->to);