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.
22 int Graph::bfs_init(int s, bool clear_visited)
27 Q_ = std::queue<int>();
30 fill(visited_.begin(), visited_.end(), false);
31 if (visited_[s] == false) {
40 Graph::getReachableTo(int target, bool clear_visited)
43 int const s = bfs_init(target, clear_visited);
48 int const i = Q_.front();
50 if (i != s || 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) < 0)
77 int const i = Q_.front();
79 Format const & format = formats.get(i);
80 if (!only_viewable || !format.viewer().empty() ||
81 format.isChildFormat())
84 vector<int>::const_iterator cit =
85 vertices_[i].out_vertices.begin();
86 vector<int>::const_iterator end =
87 vertices_[i].out_vertices.end();
88 for (; cit != end; ++cit)
89 if (!visited_[*cit]) {
90 visited_[*cit] = true;
99 bool Graph::isReachable(int from, int to)
104 int const s = bfs_init(from);
108 while (!Q_.empty()) {
109 int const i = Q_.front();
114 vector<int>::const_iterator cit =
115 vertices_[i].out_vertices.begin();
116 vector<int>::const_iterator end =
117 vertices_[i].out_vertices.end();
118 for (; cit != end; ++cit) {
119 if (!visited_[*cit]) {
120 visited_[*cit] = true;
130 Graph::EdgePath const
131 Graph::getPath(int from, int t)
137 int const s = bfs_init(from);
141 vector<int> prev_edge(formats.size());
142 vector<int> prev_vertex(formats.size());
145 while (!Q_.empty()) {
146 int const i = Q_.front();
153 vector<int>::const_iterator beg =
154 vertices_[i].out_vertices.begin();
155 vector<int>::const_iterator cit = beg;
156 vector<int>::const_iterator end =
157 vertices_[i].out_vertices.end();
158 for (; cit != end; ++cit)
159 if (!visited_[*cit]) {
163 int const k = cit - beg;
164 prev_edge[j] = vertices_[i].out_edges[k];
172 path.push_back(prev_edge[t]);
175 reverse(path.begin(), path.end());
179 void Graph::init(int size)
181 vertices_ = vector<Vertex>(size);
182 visited_.resize(size);
186 void Graph::addEdge(int s, int t)
188 vertices_[t].in_vertices.push_back(s);
189 vertices_[s].out_vertices.push_back(t);
190 vertices_[s].out_edges.push_back(numedges_++);
193 vector<Graph::Vertex> Graph::vertices_;