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.
21 int Graph::bfs_init(int s, bool clear_visited)
26 Q_ = std::queue<int>();
29 fill(visited_.begin(), visited_.end(), false);
30 if (visited_[s] == false) {
39 Graph::getReachableTo(int target, bool clear_visited)
42 int const s = bfs_init(target, clear_visited);
47 int const i = Q_.front();
49 if (i != s || formats.get(target).name() != "lyx") {
53 vector<int>::iterator it = vertices_[i].in_vertices.begin();
54 vector<int>::iterator end = vertices_[i].in_vertices.end();
55 for (; it != end; ++it) {
68 Graph::getReachable(int from, bool only_viewable,
72 if (bfs_init(from, clear_visited) < 0)
76 int const i = Q_.front();
78 Format const & format = formats.get(i);
79 if (format.name() == "lyx")
81 if (!only_viewable || !format.viewer().empty() ||
82 format.isChildFormat())
85 vector<int>::const_iterator cit =
86 vertices_[i].out_vertices.begin();
87 vector<int>::const_iterator end =
88 vertices_[i].out_vertices.end();
89 for (; cit != end; ++cit)
90 if (!visited_[*cit]) {
91 visited_[*cit] = true;
100 bool Graph::isReachable(int from, int to)
105 int const s = bfs_init(from);
109 while (!Q_.empty()) {
110 int const i = Q_.front();
115 vector<int>::const_iterator cit =
116 vertices_[i].out_vertices.begin();
117 vector<int>::const_iterator end =
118 vertices_[i].out_vertices.end();
119 for (; cit != end; ++cit) {
120 if (!visited_[*cit]) {
121 visited_[*cit] = true;
131 Graph::EdgePath const
132 Graph::getPath(int from, int t)
138 int const s = bfs_init(from);
142 vector<int> prev_edge(formats.size());
143 vector<int> prev_vertex(formats.size());
146 while (!Q_.empty()) {
147 int const i = Q_.front();
154 vector<int>::const_iterator beg =
155 vertices_[i].out_vertices.begin();
156 vector<int>::const_iterator cit = beg;
157 vector<int>::const_iterator end =
158 vertices_[i].out_vertices.end();
159 for (; cit != end; ++cit)
160 if (!visited_[*cit]) {
164 int const k = cit - beg;
165 prev_edge[j] = vertices_[i].out_edges[k];
173 path.push_back(prev_edge[t]);
176 reverse(path.begin(), path.end());
180 void Graph::init(int size)
182 vertices_ = vector<Vertex>(size);
183 visited_.resize(size);
187 void Graph::addEdge(int s, int t)
189 vertices_[t].in_vertices.push_back(s);
190 vertices_[s].out_vertices.push_back(t);
191 vertices_[s].out_edges.push_back(numedges_++);
194 vector<Graph::Vertex> Graph::vertices_;