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::clearPaths()
50 vector<Vertex>::iterator it = vertices_.begin();
51 vector<Vertex>::iterator en = vertices_.end();
52 for (; it != en; ++it)
58 Graph::getReachableTo(int target, bool clear_visited)
60 Mutex::Locker lock(&mutex_);
63 if (!bfs_init(target, clear_visited))
66 // Here's the logic, which is shared by the other routines.
67 // Q_ holds a list of nodes we have been able to reach (in this
68 // case, reach backwards). It is initialized to the current node
69 // by bfs_init, and then we recurse, adding the nodes we can reach
70 // from the current node as we go. That makes it a breadth-first
73 int const current = Q_.front();
75 if (current != target || formats.get(target).name() != "lyx")
76 result.push_back(current);
78 vector<Arrow *>::iterator it = vertices_[current].in_arrows.begin();
79 vector<Arrow *>::iterator const end = vertices_[current].in_arrows.end();
80 for (; it != end; ++it) {
81 const int cv = (*it)->from;
82 if (!vertices_[cv].visited) {
83 vertices_[cv].visited = true;
94 Graph::getReachable(int from, bool only_viewable,
97 Mutex::Locker lock(&mutex_);
100 if (!bfs_init(from, clear_visited))
103 while (!Q_.empty()) {
104 int const current = Q_.front();
106 Format const & format = formats.get(current);
107 if (!only_viewable || !format.viewer().empty())
108 result.push_back(current);
109 else if (format.isChildFormat()) {
110 Format const * const parent =
111 formats.getFormat(format.parentFormat());
112 if (parent && !parent->viewer().empty())
113 result.push_back(current);
116 vector<Arrow *>::const_iterator cit =
117 vertices_[current].out_arrows.begin();
118 vector<Arrow *>::const_iterator end =
119 vertices_[current].out_arrows.end();
120 for (; cit != end; ++cit) {
121 int const cv = (*cit)->to;
122 if (!vertices_[cv].visited) {
123 vertices_[cv].visited = true;
133 bool Graph::isReachable(int from, int to)
135 Mutex::Locker lock(&mutex_);
140 if (to < 0 || !bfs_init(from))
143 while (!Q_.empty()) {
144 int const current = Q_.front();
149 vector<Arrow *>::const_iterator cit =
150 vertices_[current].out_arrows.begin();
151 vector<Arrow *>::const_iterator end =
152 vertices_[current].out_arrows.end();
153 for (; cit != end; ++cit) {
154 int const cv = (*cit)->to;
155 if (!vertices_[cv].visited) {
156 vertices_[cv].visited = true;
166 Graph::EdgePath const Graph::getPath(int from, int to)
168 Mutex::Locker lock(&mutex_);
170 static const EdgePath path;
174 if (to < 0 || !bfs_init(from))
178 while (!Q_.empty()) {
179 int const current = Q_.front();
182 vector<Arrow *>::const_iterator cit =
183 vertices_[current].out_arrows.begin();
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 // NOTE If we wanted to collect all the paths, then
192 // we just need to collect them here and not worry
194 EdgePath lastpath = vertices_[(*cit)->from].path;
195 lastpath.push_back((*cit)->id);
196 vertices_[cv].path = lastpath;
199 return vertices_[cv].path;
208 void Graph::init(int size)
210 Mutex::Locker lock(&mutex_);
212 vertices_ = vector<Vertex>(size);
218 void Graph::addEdge(int from, int to)
220 Mutex::Locker lock(&mutex_);
222 arrows_.push_back(Arrow(from, to, numedges_));
224 Arrow * ar = &(arrows_.back());
225 vertices_[to].in_arrows.push_back(ar);
226 vertices_[from].out_arrows.push_back(ar);
230 // At present, we do not need this debugging code, but
231 // I am going to leave it here in case we need it again.
233 void Graph::dumpGraph() const
235 vector<Vertex>::const_iterator it = vertices_.begin();
236 vector<Vertex>::const_iterator en = vertices_.end();
237 for (; it != en; ++it) {
238 LYXERR0("Next vertex...");
239 LYXERR0("In arrows...");
240 std::vector<Arrow *>::const_iterator iit = it->in_arrows.begin();
241 std::vector<Arrow *>::const_iterator ien = it->in_arrows.end();
242 for (; iit != ien; ++iit)
243 LYXERR0("From " << (*iit)->from << " to " << (*iit)->to);
244 LYXERR0("Out arrows...");
245 iit = it->out_arrows.begin();
246 ien = it->out_arrows.end();
247 for (; iit != ien; ++iit)
248 LYXERR0("From " << (*iit)->from << " to " << (*iit)->to);