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.
26 int Graph::bfs_init(int s, bool clear_visited)
31 Q_ = std::queue<int>();
34 fill(visited_.begin(), visited_.end(), false);
35 if (visited_[s] == false) {
44 Graph::getReachableTo(int target, bool clear_visited)
47 int const s = bfs_init(target, clear_visited);
52 int const i = Q_.front();
54 if (i != s || formats.get(target).name() != "lyx") {
58 vector<int>::iterator it = vertices_[i].in_vertices.begin();
59 vector<int>::iterator end = vertices_[i].in_vertices.end();
60 for (; it != end; ++it) {
73 Graph::getReachable(int from, bool only_viewable,
77 if (bfs_init(from, clear_visited) < 0)
81 int const i = Q_.front();
83 Format const & format = formats.get(i);
84 if (!only_viewable || !format.viewer().empty())
86 else if (format.isChildFormat()) {
87 Format const * const parent =
88 formats.getFormat(format.parentFormat());
89 if (parent && !parent->viewer().empty())
93 vector<int>::const_iterator cit =
94 vertices_[i].out_vertices.begin();
95 vector<int>::const_iterator end =
96 vertices_[i].out_vertices.end();
97 for (; cit != end; ++cit)
98 if (!visited_[*cit]) {
99 visited_[*cit] = true;
108 bool Graph::isReachable(int from, int to)
113 int const s = bfs_init(from);
117 while (!Q_.empty()) {
118 int const i = Q_.front();
123 vector<int>::const_iterator cit =
124 vertices_[i].out_vertices.begin();
125 vector<int>::const_iterator end =
126 vertices_[i].out_vertices.end();
127 for (; cit != end; ++cit) {
128 if (!visited_[*cit]) {
129 visited_[*cit] = true;
139 Graph::EdgePath const
140 Graph::getPath(int from, int t)
146 int const s = bfs_init(from);
150 vector<int> prev_edge(formats.size());
151 vector<int> prev_vertex(formats.size());
154 while (!Q_.empty()) {
155 int const i = Q_.front();
162 vector<int>::const_iterator beg =
163 vertices_[i].out_vertices.begin();
164 vector<int>::const_iterator cit = beg;
165 vector<int>::const_iterator end =
166 vertices_[i].out_vertices.end();
167 for (; cit != end; ++cit)
168 if (!visited_[*cit]) {
172 int const k = cit - beg;
173 prev_edge[j] = vertices_[i].out_edges[k];
181 path.push_back(prev_edge[t]);
184 reverse(path.begin(), path.end());
188 void Graph::init(int size)
190 vertices_ = vector<Vertex>(size);
191 visited_.resize(size);
195 void Graph::addEdge(int s, int t)
197 vertices_[t].in_vertices.push_back(s);
198 vertices_[s].out_vertices.push_back(t);
199 vertices_[s].out_edges.push_back(numedges_++);
202 vector<Graph::Vertex> Graph::vertices_;