3 * This file is part of LyX, the document processor.
4 * Licence details can be found in the file COPYING.
8 * Full author contact details are available in file CREDITS.
23 bool Graph::bfs_init(int s, bool clear_visited)
25 if (s < 0 || s >= vertices_.size())
31 fill(visited_.begin(), visited_.end(), false);
32 if (visited_[s] == false) {
41 Graph::getReachableTo(int target, bool clear_visited)
44 if (!bfs_init(target, clear_visited))
48 int const i = Q_.front();
50 if (i != target || formats.get(target).name() != "lyx") {
54 vector<int>::iterator it = vertices_[i].in_vertices.begin();
55 vector<int>::iterator end = vertices_[i].in_vertices.end();
56 for (; it != end; ++it) {
69 Graph::getReachable(int from, bool only_viewable,
73 if (!bfs_init(from, clear_visited))
77 int const i = Q_.front();
79 Format const & format = formats.get(i);
80 if (!only_viewable || !format.viewer().empty())
82 else if (format.isChildFormat()) {
83 Format const * const parent =
84 formats.getFormat(format.parentFormat());
85 if (parent && !parent->viewer().empty())
89 vector<int>::const_iterator cit =
90 vertices_[i].out_vertices.begin();
91 vector<int>::const_iterator end =
92 vertices_[i].out_vertices.end();
93 for (; cit != end; ++cit)
94 if (!visited_[*cit]) {
95 visited_[*cit] = true;
104 bool Graph::isReachable(int from, int to)
109 if (to < 0 || to >= vertices_.size() || !bfs_init(from))
112 while (!Q_.empty()) {
113 int const current = Q_.front();
118 vector<int>::const_iterator cit =
119 vertices_[current].out_vertices.begin();
120 vector<int>::const_iterator end =
121 vertices_[current].out_vertices.end();
122 for (; cit != end; ++cit) {
123 if (!visited_[*cit]) {
124 visited_[*cit] = true;
134 Graph::EdgePath const Graph::getPath(int from, int to)
140 if (to < 0 || to >= vertices_.size() || !bfs_init(from))
143 vector<int> prev_edge(formats.size());
144 vector<int> prev_vertex(formats.size());
147 while (!Q_.empty()) {
148 int const current = Q_.front();
155 vector<int>::const_iterator const beg =
156 vertices_[current].out_vertices.begin();
157 vector<int>::const_iterator cit = beg;
158 vector<int>::const_iterator end =
159 vertices_[current].out_vertices.end();
160 for (; cit != end; ++cit)
161 if (!visited_[*cit]) {
165 int const k = cit - beg;
166 prev_edge[j] = vertices_[current].out_edges[k];
167 prev_vertex[j] = current;
174 path.push_back(prev_edge[to]);
175 to = prev_vertex[to];
177 reverse(path.begin(), path.end());
182 void Graph::init(int size)
184 vertices_ = vector<Vertex>(size);
185 visited_.resize(size);
190 void Graph::addEdge(int from, int to)
192 vertices_[to].in_vertices.push_back(from);
193 vertices_[from].out_vertices.push_back(to);
194 vertices_[from].out_edges.push_back(numedges_++);
198 vector<Graph::Vertex> Graph::vertices_;