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)
61 if (!bfs_init(target, clear_visited))
64 // Here's the logic, which is shared by the other routines.
65 // Q_ holds a list of nodes we have been able to reach (in this
66 // case, reach backwards). It is initialized to the current node
67 // by bfs_init, and then we recurse, adding the nodes we can reach
68 // from the current node as we go. That makes it a breadth-first
71 int const current = Q_.front();
73 if (current != target || formats.get(target).name() != "lyx")
74 result.push_back(current);
76 vector<Arrow *>::iterator it = vertices_[current].in_arrows.begin();
77 vector<Arrow *>::iterator const end = vertices_[current].in_arrows.end();
78 for (; it != end; ++it) {
79 const int cv = (*it)->from;
80 if (!vertices_[cv].visited) {
81 vertices_[cv].visited = true;
92 Graph::getReachable(int from, bool only_viewable,
96 if (!bfs_init(from, clear_visited))
100 int const current = Q_.front();
102 Format const & format = formats.get(current);
103 if (!only_viewable || !format.viewer().empty())
104 result.push_back(current);
105 else if (format.isChildFormat()) {
106 Format const * const parent =
107 formats.getFormat(format.parentFormat());
108 if (parent && !parent->viewer().empty())
109 result.push_back(current);
112 vector<Arrow *>::const_iterator cit =
113 vertices_[current].out_arrows.begin();
114 vector<Arrow *>::const_iterator end =
115 vertices_[current].out_arrows.end();
116 for (; cit != end; ++cit) {
117 int const cv = (*cit)->to;
118 if (!vertices_[cv].visited) {
119 vertices_[cv].visited = true;
129 bool Graph::isReachable(int from, int to)
134 if (to < 0 || !bfs_init(from))
137 while (!Q_.empty()) {
138 int const current = Q_.front();
143 vector<Arrow *>::const_iterator cit =
144 vertices_[current].out_arrows.begin();
145 vector<Arrow *>::const_iterator end =
146 vertices_[current].out_arrows.end();
147 for (; cit != end; ++cit) {
148 int const cv = (*cit)->to;
149 if (!vertices_[cv].visited) {
150 vertices_[cv].visited = true;
160 Graph::EdgePath const Graph::getPath(int from, int to)
162 static const EdgePath path;
166 if (to < 0 || !bfs_init(from))
170 while (!Q_.empty()) {
171 int const current = Q_.front();
174 vector<Arrow *>::const_iterator cit =
175 vertices_[current].out_arrows.begin();
176 vector<Arrow *>::const_iterator end =
177 vertices_[current].out_arrows.end();
178 for (; cit != end; ++cit) {
179 int const cv = (*cit)->to;
180 if (!vertices_[cv].visited) {
181 vertices_[cv].visited = true;
183 // NOTE If we wanted to collect all the paths, then
184 // we just need to collect them here and not worry
186 EdgePath lastpath = vertices_[(*cit)->from].path;
187 lastpath.push_back((*cit)->id);
188 vertices_[cv].path = lastpath;
191 return vertices_[cv].path;
200 void Graph::init(int size)
202 vertices_ = vector<Vertex>(size);
208 void Graph::addEdge(int from, int to)
210 arrows_.push_back(Arrow(from, to, numedges_));
212 Arrow * ar = &(arrows_.back());
213 vertices_[to].in_arrows.push_back(ar);
214 vertices_[from].out_arrows.push_back(ar);
218 // At present, we do not need this debugging code, but
219 // I am going to leave it here in case we need it again.
221 void Graph::dumpGraph() const
223 vector<Vertex>::const_iterator it = vertices_.begin();
224 vector<Vertex>::const_iterator en = vertices_.end();
225 for (; it != en; ++it) {
226 LYXERR0("Next vertex...");
227 LYXERR0("In arrows...");
228 std::vector<Arrow *>::const_iterator iit = it->in_arrows.begin();
229 std::vector<Arrow *>::const_iterator ien = it->in_arrows.end();
230 for (; iit != ien; ++iit)
231 LYXERR0("From " << (*iit)->from << " to " << (*iit)->to);
232 LYXERR0("Out arrows...");
233 iit = it->out_arrows.begin();
234 ien = it->out_arrows.end();
235 for (; iit != ien; ++iit)
236 LYXERR0("From " << (*iit)->from << " to " << (*iit)->to);